The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems

DOI10.1137/15M1034477zbMATH Open1365.65068arXiv1508.01835OpenAlexW2962927345MaRDI QIDQ5738177

Author name not available (Why is that?)

Publication date: 31 May 2017

Published in: (Search for Journal in Brave)

Abstract: Although some preconditioners are available for solving dense linear systems, there are still many matrices for which preconditioners are lacking, in particular in cases where the size of the matrix $N$ becomes very large. There remains hence a great need to develop general purpose preconditioners whose cost scales well with the matrix size $N$. In this paper, we propose a preconditioner with broad applicability and with cost $mathcalO(N)$ for dense matrices, when the matrix is given by a smooth kernel. Extending the method using the same framework to general $mathcal{H}^2$-matrices is relatively straightforward. These preconditioners have a controlled accuracy (machine accuracy can be achieved if needed) and scale linearly with $N$. They are based on an approximate direct solve of the system. The linear scaling of the algorithm is achieved by means of two key ideas. First, the $mathcal{H}^2$-structure of the dense matrix is exploited to obtain an extended sparse system of equations. Second, fill-ins arising when performing the elimination are compressed as low-rank matrices if they correspond to well-separated interactions. This ensures that the sparsity pattern of the extended sparse matrix is preserved throughout the elimination, hence resulting in a very efficient algorithm with $mathcalO(Nlog(1/varepsilon{)}^2)$ computational cost and $mathcalO(Nlog1/varepsilon)$ memory requirement, for an error tolerance $0<varepsilon<1$. The solver is inexact, although the error can be controlled and made as small as needed. These solvers are related to ILU in the sense that the fill-in is controlled. However, in ILU, most of the fill-in is simply discarded whereas here it is approximated using low-rank blocks, with a prescribed tolerance. Numerical examples are discussed to demonstrate the linear scaling of the method and to illustrate its effectiveness as a preconditioner.

Full work available at URL: https://arxiv.org/abs/1508.01835

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5738177)