On the Compression of Low Rank Matrices (Q5318307)

The authors describe a procedure for the decomposition and compression of low-rank matrices. Such matrices arise for instance in computational physics in potential theory, in fluid dynamics, in numerical simulations of electromagnetic phenomena. The decomposition of a matrix \(A\) of rank \(k\) is constructed in the form \(A=U\circ B\circ V^*\), where \(B\) is a sub-matrix of \(A\) and \(U\), \(V\) are well-conditioned matrices each containing an identity sub-matrix. Like the singular value decomposition (SVD), the proposed algorithm belongs to a class of algebraic schemes. The advantage of the new factorisation is that the bases used for the construction of \(A\) consists of \(k\) rows and \(k\) columns of \(A\) while with the SVD each element of the bases of the decomposition is a linear combination of all rows (or columns) of the matrix \(A\). Thus matrix-vector multiplications are considerably less expensive than with the SDV. The costs for the construction of the factorisation is comparable with the QR factorisation. Disadvantages of the new decomposition compared to the SVD are the loss of accuracy and the nonuniqueness of the factorisation. The new approach is applied to the construction of an accelerated direct solver for integral equations of potential theory. This application demonstrates that the decomposition is much easier to manipulate. The performance of the proposed algorithm is investigated on a second kind integral equation obtained by discretizing an exterior Dirichlet boundary value problem using the double layer potential.