×

A fast direct solver for structured linear systems by recursive skeletonization. (English) Zbl 1259.65062

Summary: We present a fast direct solver for structured linear systems based on multilevel matrix compression. Using the recently developed interpolative decomposition of a low-rank matrix in a recursive manner, we embed an approximation of the original matrix into a larger but highly structured sparse one that allows fast factorization and application of the inverse. The algorithm extends the Martinsson-Rokhlin (cf. [P. G. Martinsson and V. Rokhlin, J. Comput. Phys. 205, No. 1, 1–23 (2005; Zbl 1078.65112)]) method developed for 2D boundary integral equations and proceeds in two phases: a precomputation phase, consisting of matrix compression and factorization, followed by a solution phase to apply the matrix inverse. For boundary integral equations which are not too oscillatory, e.g., based on the Green functions for the Laplace or low-frequency Helmholtz equations, both phases typically have complexity \(\mathcal{O} (N)\) in two dimensions, where \(N\) is the number of discretization points. In our current implementation, the corresponding costs in three dimensions are \(\mathcal{O} (N^{3/2})\) and \(\mathcal{O} (N \log N)\) for precomputation and solution, respectively. Extensive numerical experiments show a speedup of \(\sim 100\) for the solution phase over modern fast multipole methods; however, the cost of precomputation remains high. Thus, the solver is particularly suited to problems where large numbers of iterations would be required. Such is the case with ill-conditioned linear systems or when the same system is to be solved with multiple right-hand sides. Our algorithm is implemented in Fortran and freely available.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
65N38 Boundary element methods for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65F22 Ill-posedness and regularization problems in numerical linear algebra

Citations:

Zbl 1078.65112
PDFBibTeX XMLCite
Full Text: DOI arXiv