Divide and conquer low-rank preconditioners for symmetric matrices

Ruipeng Li, Yousef Saad

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

This paper presents a preconditioning method based on an approximate inverse of the original matrix, computed recursively from a multilevel low-rank (MLR) expansion approach. The basic idea is to recursively divide the problem in two and apply a low-rank approximation to a matrix obtained from the Sherman-Morrison formula. The low-rank expansion is computed by a few steps of the Lanczos bidiagonalization procedure. The MLR preconditioner has been motivated by its potential for exploiting different levels of parallelism on modern high-performance platforms, though this feature is not yet tested in this paper. Numerical experiments indicate that, when combined with Krylov subspace accelerators, this preconditioner can be efficient and robust for solving symmetric sparse linear systems.

Original languageEnglish (US)
Pages (from-to)A2069-A2095
JournalSIAM Journal on Scientific Computing
Volume35
Issue number4
DOIs
StatePublished - Nov 7 2013

Keywords

  • Domain decomposition
  • Incomplete LU factorization
  • Krylov subspace method
  • Low-rank approximation
  • Parallel preconditioner
  • Recursive multilevel preconditioner
  • Sherman-Morrison formula
  • Singular value decomposition

Fingerprint Dive into the research topics of 'Divide and conquer low-rank preconditioners for symmetric matrices'. Together they form a unique fingerprint.

Cite this