An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices

Yuanzhe Xi, Ruipeng Li, Yousef Saad

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

This paper describes a multilevel preconditioning technique for solving sparse symmetric linear systems of equations. This "Multilevel Schur Low-Rank" (MSLR) preconditioner first builds a tree structure T based on a hierarchical decomposition of the matrix and then computes an approximate inverse of the original matrix level by level. Unlike classical direct solvers, the construction of the MSLR preconditioner follows a top-down traversal of T and exploits a low-rank property that is satisfied by the difference between the inverses of the local Schur complements and specific blocks of the original matrix. A few steps of the generalized Lanczos tridiagonalization procedure are applied to capture most of this difference. Numerical results are reported to illustrate the efficiency and robustness of the MSLR preconditioner with both two- and three-dimensional discretized PDE problems and with publicly available test problems.

Original languageEnglish (US)
Pages (from-to)235-259
Number of pages25
JournalSIAM Journal on Matrix Analysis and Applications
Volume37
Issue number1
DOIs
StatePublished - 2016

Bibliographical note

Funding Information:
Received by the editors May 18, 2015; accepted for publication (in revised form) by L. Giraud December 10, 2015; published electronically March 3, 2016. This work was supported by the NSF under grants DMS-1216366 and DMS-1521573 and by the Minnesota Supercomputing Institute. The U.S. Government retains a nonexclusive, royalty-free license to publish or reproduce the published form of this contribution, or allow others to do so, for U.S. Government purposes. Copyright is owned by SIAM to the extent not limited by these rights. http://www.siam.org/journals/simax/37-1/M102183.html ?Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455-0154 (yxi@cs.umn.edu, saad@cs.umn.edu). ?Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA 94551 (li50@llnl.gov). This autho?s work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract DE-AC52-07NA27344 (LLNL-JRNL-680317).

Keywords

  • Domain decomposition
  • Incomplete factorization
  • Krylov subspace methods
  • Low-rank approximation
  • Multilevel preconditioner
  • Nested Dissection ordering
  • Schur complements

Fingerprint Dive into the research topics of 'An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices'. Together they form a unique fingerprint.

Cite this