Incomplete LU Preconditioner Based on Max-Plus Approximation of LU Factorization

James Hook, Francoise Tisseur

Research output: Contribution to journalArticlepeer-review

9 Citations (SciVal)
67 Downloads (Pure)


We present a new method for the a priori approximation of the orders of magnitude of the entries in the LU factors of a complex or real matrix A. This approximation is used to determine the positions of the largest entries in the LU factors of A, and these positions are used as the sparsity pattern for an incomplete LU factorization preconditioner. Our method uses max-plus algebra and is based solely on the moduli of the entries of A. We also present techniques for predicting which permutation matrices will be chosen by Gaussian elimination with partial pivoting. We exploit the strong connection between the field of Puiseux series and the max-plus semiring to prove properties of the max-plus LU factors. Experiments with a set of test matrices from the University of Florida Sparse Matrix Collection show that our max-plus LU preconditioners outperform traditional level of fill methods and have similar performance to those preconditioners computed with more expensive threshold-based methods.
Original languageEnglish
Pages (from-to)1160 - 1189
Number of pages30
JournalSIAM Journal On Matrix Analysis and Applications (SIMAX)
Issue number4
Early online date19 Oct 2017
Publication statusPublished - 31 Dec 2017


Dive into the research topics of 'Incomplete LU Preconditioner Based on Max-Plus Approximation of LU Factorization'. Together they form a unique fingerprint.

Cite this