Experimental study of ILU preconditioners for indefinite matrices

Edmond Chow, Yousef Saad

Research output: Contribution to journalArticle

157 Citations (Scopus)

Abstract

Incomplete LU factorization preconditioners have been surprisingly successful for many cases of general nonsymmetric and indefinite matrices. However, their failure rate is still too high for them to be useful as black-box library software for general matrices. Besides fatal breakdowns due to zero pivots, the major causes of failure are inaccuracy, and instability of the triangular solves. When there are small pivots, both these problems can occur, but these problems can also occur without small pivots. Through examples from actual problems, this paper shows how these problems evince themselves, how these problems can be detected, and how these problems can sometimes be circumvented through pivoting, reordering, scaling, perturbing diagonal elements, and preserving symmetric structure. The goal of this paper is to gain a better practical understanding of ILU preconditioners and help improve their reliability.

Original languageEnglish (US)
Pages (from-to)387-414
Number of pages28
JournalJournal of Computational and Applied Mathematics
Volume86
Issue number2
DOIs
StatePublished - Dec 10 1997

Fingerprint

Preconditioner
Experimental Study
Pivot
Factorization
Incomplete LU Factorization
Pivoting
Reordering
Failure Rate
Black Box
Breakdown
Triangular
Scaling
Software
Zero

Keywords

  • Incomplete factorization preconditioning
  • Instability
  • Ordering
  • Pivoting

Cite this

Experimental study of ILU preconditioners for indefinite matrices. / Chow, Edmond; Saad, Yousef.

In: Journal of Computational and Applied Mathematics, Vol. 86, No. 2, 10.12.1997, p. 387-414.

Research output: Contribution to journalArticle

@article{f6dc2b0b8e6e4d6dbe449dfc47125be3,
title = "Experimental study of ILU preconditioners for indefinite matrices",
abstract = "Incomplete LU factorization preconditioners have been surprisingly successful for many cases of general nonsymmetric and indefinite matrices. However, their failure rate is still too high for them to be useful as black-box library software for general matrices. Besides fatal breakdowns due to zero pivots, the major causes of failure are inaccuracy, and instability of the triangular solves. When there are small pivots, both these problems can occur, but these problems can also occur without small pivots. Through examples from actual problems, this paper shows how these problems evince themselves, how these problems can be detected, and how these problems can sometimes be circumvented through pivoting, reordering, scaling, perturbing diagonal elements, and preserving symmetric structure. The goal of this paper is to gain a better practical understanding of ILU preconditioners and help improve their reliability.",
keywords = "Incomplete factorization preconditioning, Instability, Ordering, Pivoting",
author = "Edmond Chow and Yousef Saad",
year = "1997",
month = "12",
day = "10",
doi = "10.1016/S0377-0427(97)00171-4",
language = "English (US)",
volume = "86",
pages = "387--414",
journal = "Journal of Computational and Applied Mathematics",
issn = "0377-0427",
publisher = "Elsevier",
number = "2",

}

TY - JOUR

T1 - Experimental study of ILU preconditioners for indefinite matrices

AU - Chow, Edmond

AU - Saad, Yousef

PY - 1997/12/10

Y1 - 1997/12/10

N2 - Incomplete LU factorization preconditioners have been surprisingly successful for many cases of general nonsymmetric and indefinite matrices. However, their failure rate is still too high for them to be useful as black-box library software for general matrices. Besides fatal breakdowns due to zero pivots, the major causes of failure are inaccuracy, and instability of the triangular solves. When there are small pivots, both these problems can occur, but these problems can also occur without small pivots. Through examples from actual problems, this paper shows how these problems evince themselves, how these problems can be detected, and how these problems can sometimes be circumvented through pivoting, reordering, scaling, perturbing diagonal elements, and preserving symmetric structure. The goal of this paper is to gain a better practical understanding of ILU preconditioners and help improve their reliability.

AB - Incomplete LU factorization preconditioners have been surprisingly successful for many cases of general nonsymmetric and indefinite matrices. However, their failure rate is still too high for them to be useful as black-box library software for general matrices. Besides fatal breakdowns due to zero pivots, the major causes of failure are inaccuracy, and instability of the triangular solves. When there are small pivots, both these problems can occur, but these problems can also occur without small pivots. Through examples from actual problems, this paper shows how these problems evince themselves, how these problems can be detected, and how these problems can sometimes be circumvented through pivoting, reordering, scaling, perturbing diagonal elements, and preserving symmetric structure. The goal of this paper is to gain a better practical understanding of ILU preconditioners and help improve their reliability.

KW - Incomplete factorization preconditioning

KW - Instability

KW - Ordering

KW - Pivoting

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

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

U2 - 10.1016/S0377-0427(97)00171-4

DO - 10.1016/S0377-0427(97)00171-4

M3 - Article

VL - 86

SP - 387

EP - 414

JO - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

SN - 0377-0427

IS - 2

ER -