Incomplete cross approximation in the mosaic-skeleton method (Q1581115)

The mosaic-skeleton method is based on the observation that in very large matrices often large blocks can be approximated by the sum of a few rank one matrices (skeletons). This is true in particular if the matrices arise from the discretization of integral equations. Such approximations can be useful, e.g. in matrix-vector multiplications. A mosaic partitioning of a matrix \(A\) is essentially a decomposition of the nonzero part of \(A\) in disjoint blocks. A mosaic rank can be associated to this. The author is interested in approximating a given matrix by matrices with a mosaic partitioning with low mosaic rank. He describes a method to perform this, based on the idea that the rows and columns of the matrix can be related to meshes (a natural assumption if the matrix arises from a discretization). He also presents examples that suggest that the time needed for his algorithm grows nearly linearly with the size of the matrix, for a fixed accuracy in the approximation.