Accessibility navigation


A max-plus approach to incomplete Cholesky factorization preconditioners

Hook, J., Scott, J. ORCID: https://orcid.org/0000-0003-2130-1091, Tisseur, F. and Hogg, J. (2018) A max-plus approach to incomplete Cholesky factorization preconditioners. SIAM Journal on Scientific Computing, 40 (4). A1987-A2004. ISSN 1095-7197

[img]
Preview
Text (Open Access) - Published Version
· Available under License Creative Commons Attribution.
· Please see our End User Agreement before downloading.

461kB
[img] Text - Accepted Version
· Restricted to Repository staff only

361kB

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item DOI: 10.1137/16M1107735

Abstract/Summary

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.

Item Type:Article
Refereed:Yes
Divisions:Science > School of Mathematical, Physical and Computational Sciences > Department of Mathematics and Statistics
ID Code:76701
Publisher:Society for Industrial and Applied Mathematics

Downloads

Downloads per month over past year

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation