Incomplete cross approximation in the mosaic-skeleton method

The mosaic-skeleton method was bred in a simple observation that rather lar ge blocks in very large matrices coming from integral formulations can be a pproximated accurately by a sum of just few rank-one matrices (skeletons). 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 (functional skeletons). Since the effect of app roximations is like that of having small-rank matrices, we find it pertinen t to say about mosaic ranks of a matrix which turn out to be pretty small f or many nonsingular matrices. On the first stage, the method builds up an appropriate mosaic partitioning using the concept of a tree of clusters and some extra information rather than the matrix entries (related to the mesh). On the second stage, it appr oximates every allowed block by skeletons using the entries of Some rather small cross which is chosen by an adaptive procedure. We focus chiefly on s ome aspects of practical implementation and numerical examples on which the approximation time was found to grow almost Linearly in the matrix size.