Theory and Applications of Mosaic-Skeleton Method

Eugene Tyrtyshnikov
Institute of Numerical Mathematics, Russian Academy of Sciences,
Gubkina 8, Moscow 117333, Russia

Abstract

The mosaic-skeleton method was bred in a simple observation that rather large blocks in very large matrices coming from integral formulations can be approximated accurately by a sum of just few skeletons (some say dyads or rank-one matrices). These blocks might correspond to a region where the kernel is smooth enough, and anyway it can be a region where the kernel is approximated by a short sum of separable functions (in other words, functional skeletons). The mosaic-skeleton approximations are easy to result in fast approximate matrix-vector multiplication algorithms close by nature to those of multipole, interpolation, and wavelet-based approaches. All the said techniques involve some hierarcy of interface regions and function approximants. What the mosaic-skeleton method differs in from others is a matrix analysis view on largely the same problem. Such a view can be very useful due to the generality of matrix theory approaches. Since the effect of approximations is like that of having small-rank matrices, we find it pertinent to say about mosaic ranks of a matrix which turn to be pretty small for many nonsingular matrices.

We cover a wide class of applications. In particular, following Brandt, we propose to call f(x,y) an asymptotically smooth function if there exist c,d > 0 and a real number g such that

| partialp f(x,y) | < c : dp : p! : |x-y|g-p,
where partialp is any p-order derivative in y. Then, for nxn matrices An = [f(xi(n), yj(n)] with quasiuniform meshes {xni } and {y(n)j } in a bounded m-dimensional domain, we prove that the approximate mosaic ranks might grow only logarithmically in n. The results obtained lead immediately to O(n log n) matrix-vector multiplication algorithms. Using a special technique for harmonic kernels, we can sharpen the estimates. A likely technique can be used for oscillatory (and hence not asymptotically smooth) kernels.

General matrix approximation algorithms were applied to integral equations of lots of applications from the classical potential flow or electrostatic problems to thermal analysis for stratified media and electromagnetic scattering problems. Selected numerical results will be presented.