Communications in Mathematical Sciences

Volume 18 (2020)

Number 1

Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations

Pages: 91 – 108

DOI: https://dx.doi.org/10.4310/CMS.2020.v18.n1.a4

Authors

Jordi Feliu-Fabà (Institute for Computational and Mathematical Engineering, Stanford University, Stanford, California, U.S.A.)

Kenneth L. Ho (Center for Computational Mathematics, Flatiron Institute, New York, N.Y., U.S.A.)

Lexing Ying (Department of Mathematics and Institute for Computational and Mathematical Engineering, Stanford University, Stanford, California, U.S.A.)

Abstract

The hierarchical interpolative factorization for elliptic partial differential equations is a fast algorithm for approximate sparse matrix inversion in linear or quasilinear time. Its accuracy can degrade, however, when applied to strongly ill-conditioned problems. Here, we propose a simple modification that can significantly improve the accuracy at no additional asymptotic cost: applying a block Jacobi preconditioner before each level of skeletonization. This dramatically limits the impact of the underlying system conditioning and enables the construction of robust and highly efficient preconditioners even at quite modest compression tolerances. Numerical examples demonstrate the performance of the new approach.

Keywords

recursive preconditioning, hierarchical interpolative factorization

2010 Mathematics Subject Classification

65F05, 65F08, 65N22

Full Text (PDF format)

The work of J.F. is partially supported by “la Caixa” Fellowship, LCF/BQ/AA16/11580045, sponsored by “la Caixa” Banking Foundation.

The work of L.Y. is partially supported by U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Scientific Discovery through Advanced Computing (SciDAC) program and the National Science Foundation under award DMS-1818449.

Received 14 March 2019

Accepted 3 September 2019

Published 1 April 2020