“Compress and eliminate” solver for symmetric positive definite sparse matrices

Daria A. Sushnikova, Ivan V. Oseledets

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

We propose a new approximate factorization for solving linear systems with symmetric positive definite sparse matrices. In a nutshell the algorithm applies hierarchically block Gaussian elimination and additionally compresses the fill-in. The systems that have efficient compression of the fill-in mostly arise from discretization of partial differential equations. We show that the resulting factorization can be used as an efficient preconditioner and compare the proposed approach with the state-of-art direct and iterative solvers.

Original languageEnglish (US)
Pages (from-to)A1742-A1762
JournalSIAM Journal on Scientific Computing
Volume40
Issue number3
DOIs
StatePublished - 2018

Bibliographical note

Funding Information:
∗Submitted to the journal’s Methods and Algorithms for Scientific Computing section March 30, 2016; accepted for publication (in revised form) February 16, 2018; published electronically June 14, 2018. http://www.siam.org/journals/sisc/40-3/M106848.html Funding: The work was supported by Russian Foundation of Basic Research grant 17-01-00854. †Skolkovo Institute of Science and Technology, Moscow, Russia (darya-sushnikova@yandex.ru). ‡Skolkovo Institute of Science and Technology, Moscow, Russia, 143025 and Institute of Numerical Mathematics Russian Academy of Sciences, Moscow, Russia, 119333 (i.oseledets@skolkovotech.ru).

Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.

Keywords

  • Direct solver
  • Hierarchical matrix
  • Sparse matrix
  • Symmetric positive definite matrix

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of '“Compress and eliminate” solver for symmetric positive definite sparse matrices'. Together they form a unique fingerprint.

Cite this