Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Numerically aware orderings for sparse symmetric indefinite linear systems
Hogg J., Scott J., Thorne S. ACM Transactions on Mathematical Software44 (2):1-22,2017.Type:Article
Date Reviewed: Nov 16 2017

The LDLT decomposition of a real symmetric matrix where L is lower triangular with unit diagonal and D diagonal except for 2x2 blocks is a challenge when the matrix is sparse and indefinite. Even if the matrix is reordered to limit fill-in, a small diagonal or an ill-conditioned 2x2 block may occur during the factorization. In this case, that pivot must be delayed until it is improved by updating.

Hogg and Scott [1] reviewed several pivoting strategies for sparse indefinite linear systems as applied to a set of particularly difficult symmetric indefinite systems. They found that matching-based strategies experienced fewer delayed pivots. In these methods, larger off-diagonal matrix entries are matched with smaller diagonal entries and moved together in hopes that the pair will form a well-conditioned block during factorization. This work describes a nested dissection (ND) algorithm [2] in which each stage is modified. Large off-diagonals match with small diagonals to form well-conditioned diagonal blocks while staying within the structure of the ND ordering.

The new method was tested using several problems that were identified by Hogg and Scott [1] as particularly challenging. The performance was compared with four other methods: an ordering using only ND code, a basic matching-based ordering, and two versions of another matching-based method. As a gauge of backward error, a generated system was solved for each factorization and the residual was reduced by iterative refinement. The results show that this numerically aware ND method required significantly fewer delayed pivots and flops than the other methods.

Reviewer:  Charles R. Crawford Review #: CR145660 (1801-0014)
1) Hogg, J. D.; Scott, J. A. Pivoting strategies for tough indefinite systems. ACM Transactions Mathematical Software 40, 1(2013), 1–22.
2) George, A. Nested dissection of a regular finite-element mesh. SIAM J. Numer. Analysis 10, 2(1973), 345–363.
Bookmark and Share
 
Numerical Linear Algebra (G.1.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Numerical Linear Algebra": Date
Exploiting fast matrix multiplication within the level 3 BLAS
Higham N. ACM Transactions on Mathematical Software 16(4): 352-368, 2000. Type: Article
Aug 1 1991
Fundamentals of matrix computations
Watkins D., John Wiley & Sons, Inc., New York, NY, 1991. Type: Book (9780471614142)
Jun 1 1992
Computational methods for linear control systems
Petkov P., Christov N., Konstantinov M., Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1991. Type: Book (9780131618039)
Jun 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy