A Max-Plus Approach to Incomplete Cholesky Factorization Preconditioners

James Hook, Jennifer Scott, Francoise Tisseur, Jonathan Hogg

    Research output: Contribution to journalArticlepeer-review


    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, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 1160--1189] but is 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
    JournalSIAM Journal on Scientific Computing
    Issue number4
    Early online date3 Jul 2018
    Publication statusPublished - 3 Jul 2018


    • Sparse symmetric linear systems
    • incomplete factorizations
    • Preconditioners
    • Hungarian scaling
    • max-plus algebra
    • sparsity pattern


    Dive into the research topics of 'A Max-Plus Approach to Incomplete Cholesky Factorization Preconditioners'. Together they form a unique fingerprint.

    Cite this