A max-plus approach to incomplete Cholesky factorization preconditioners

James Hook, Jennifer Scott, Francoise Tisseur, Jonathan Hogg

Research output: Contribution to journalArticle

Abstract

We present a new method for constructing incomplete Cholesky factorization
preconditioners for use in solving large sparse symmetric positive-definite
linear systems. This method uses max-plus algebra to predict the positions of
the largest entries in the Cholesky factor and then uses these positions as the
sparsity pattern for the preconditioner.
Our method builds on the max-plus incomplete LU factorization preconditioner
recently proposed in J. Hook and F. Tisseur, Incomplete LU preconditioner based on max-plus approximation of {LU} factorization, MIMS Eprint 2016.47, Manchester, 2016 but applied to symmetric positive-definite matrices, which comprise an important special case for the method and its application.

An attractive feature of our approach is that the sparsity pattern of each column
of the preconditioner can be computed in parallel. Numerical comparisons are
made with other incomplete Cholesky factorization preconditioners using problems from a range of practical applications.

We demonstrate that the new preconditioner can outperform traditional
level-based preconditioners and offer a parallel alternative to a serial
limited-memory based approach.
Original languageEnglish
Pages (from-to)A1987-A2004
Number of pages18
JournalSIAM Journal on Scientific Computing
Volume40
Issue number4
Early online date3 Jul 2018
DOIs
Publication statusPublished - 2 Aug 2018

Fingerprint

Cholesky factorisation
Factorization
Preconditioner
Sparsity
Algebra
Linear systems
Max-plus Algebra
Incomplete LU Factorization
Data storage equipment
LU Factorization
Cholesky
Symmetric Positive Definite Matrix
Numerical Comparisons
Positive definite
Linear Systems
Predict
Alternatives
Approximation

Keywords

  • Hungarian scaling
  • Incomplete factorizations
  • Max-plus algebra
  • Preconditioners
  • Sparse symmetric linear systems
  • Sparsity pattern

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Cite this

A max-plus approach to incomplete Cholesky factorization preconditioners. / Hook, James; Scott, Jennifer; Tisseur, Francoise; Hogg, Jonathan .

In: SIAM Journal on Scientific Computing, Vol. 40, No. 4, 02.08.2018, p. A1987-A2004.

Research output: Contribution to journalArticle

Hook, James ; Scott, Jennifer ; Tisseur, Francoise ; Hogg, Jonathan . / A max-plus approach to incomplete Cholesky factorization preconditioners. In: SIAM Journal on Scientific Computing. 2018 ; Vol. 40, No. 4. pp. A1987-A2004.
@article{747a11c50ab946c0aefd5d39e7ab0a13,
title = "A max-plus approach to incomplete Cholesky factorization preconditioners",
abstract = "We present a new method for constructing incomplete Cholesky factorizationpreconditioners for use in solving large sparse symmetric positive-definitelinear systems. This method uses max-plus algebra to predict the positions ofthe largest entries in the Cholesky factor and then uses these positions as thesparsity pattern for the preconditioner.Our method builds on the max-plus incomplete LU factorization preconditionerrecently proposed in J. Hook and F. Tisseur, Incomplete LU preconditioner based on max-plus approximation of {LU} factorization, MIMS Eprint 2016.47, Manchester, 2016 but applied to symmetric positive-definite matrices, which comprise an important special case for the method and its application.An attractive feature of our approach is that the sparsity pattern of each columnof the preconditioner can be computed in parallel. Numerical comparisons aremade with other incomplete Cholesky factorization preconditioners using problems from a range of practical applications.We demonstrate that the new preconditioner can outperform traditionallevel-based preconditioners and offer a parallel alternative to a seriallimited-memory based approach.",
keywords = "Hungarian scaling, Incomplete factorizations, Max-plus algebra, Preconditioners, Sparse symmetric linear systems, Sparsity pattern",
author = "James Hook and Jennifer Scott and Francoise Tisseur and Jonathan Hogg",
year = "2018",
month = "8",
day = "2",
doi = "10.1137/16M1107735",
language = "English",
volume = "40",
pages = "A1987--A2004",
journal = "SIAM Journal on Scientific Computing",
issn = "1064-8275",
publisher = "SIAM",
number = "4",

}

TY - JOUR

T1 - A max-plus approach to incomplete Cholesky factorization preconditioners

AU - Hook, James

AU - Scott, Jennifer

AU - Tisseur, Francoise

AU - Hogg, Jonathan

PY - 2018/8/2

Y1 - 2018/8/2

N2 - We present a new method for constructing incomplete Cholesky factorizationpreconditioners for use in solving large sparse symmetric positive-definitelinear systems. This method uses max-plus algebra to predict the positions ofthe largest entries in the Cholesky factor and then uses these positions as thesparsity pattern for the preconditioner.Our method builds on the max-plus incomplete LU factorization preconditionerrecently proposed in J. Hook and F. Tisseur, Incomplete LU preconditioner based on max-plus approximation of {LU} factorization, MIMS Eprint 2016.47, Manchester, 2016 but applied to symmetric positive-definite matrices, which comprise an important special case for the method and its application.An attractive feature of our approach is that the sparsity pattern of each columnof the preconditioner can be computed in parallel. Numerical comparisons aremade with other incomplete Cholesky factorization preconditioners using problems from a range of practical applications.We demonstrate that the new preconditioner can outperform traditionallevel-based preconditioners and offer a parallel alternative to a seriallimited-memory based approach.

AB - We present a new method for constructing incomplete Cholesky factorizationpreconditioners for use in solving large sparse symmetric positive-definitelinear systems. This method uses max-plus algebra to predict the positions ofthe largest entries in the Cholesky factor and then uses these positions as thesparsity pattern for the preconditioner.Our method builds on the max-plus incomplete LU factorization preconditionerrecently proposed in J. Hook and F. Tisseur, Incomplete LU preconditioner based on max-plus approximation of {LU} factorization, MIMS Eprint 2016.47, Manchester, 2016 but applied to symmetric positive-definite matrices, which comprise an important special case for the method and its application.An attractive feature of our approach is that the sparsity pattern of each columnof the preconditioner can be computed in parallel. Numerical comparisons aremade with other incomplete Cholesky factorization preconditioners using problems from a range of practical applications.We demonstrate that the new preconditioner can outperform traditionallevel-based preconditioners and offer a parallel alternative to a seriallimited-memory based approach.

KW - Hungarian scaling

KW - Incomplete factorizations

KW - Max-plus algebra

KW - Preconditioners

KW - Sparse symmetric linear systems

KW - Sparsity pattern

UR - http://www.scopus.com/inward/record.url?scp=85053779987&partnerID=8YFLogxK

U2 - 10.1137/16M1107735

DO - 10.1137/16M1107735

M3 - Article

VL - 40

SP - A1987-A2004

JO - SIAM Journal on Scientific Computing

JF - SIAM Journal on Scientific Computing

SN - 1064-8275

IS - 4

ER -