Algorithms for Sparse Linear Systems

Preface
Contents
Notation: Quick Reference Summary
Notational Conventions Used for Matrices and Vectors
Notational Conventions Used When Discussing Graphs
Specific Variables and Matrices That Are Used Throughout
Abbreviations
1 An Introduction to Sparse Matrices
1.1 Motivation
1.2 Introductory Terminology and Concepts
1.2.1 Phases of a Sparse Direct Solver
1.2.2 Comments on the Computational Environment
1.2.3 Finite Precision Arithmetic
1.2.4 Bit Compatibility
1.2.5 Complexity of Algorithms
1.3 Sparse Matrices and Their Representation in a Computer
1.3.1 Sparse Vector Storage
1.3.2 Sparse Matrix Storage
1.4 Notes and References
2 Sparse Matrices and Their Graphs
2.1 Introduction to Graphs
2.2 Walks, Paths, Cycles, and DAGs
2.3 Trees, Components, and Connectivity
2.4 Adjacency Graphs
2.5 Matrix Permutations and Orderings
2.6 Lists, Stacks and Queues
2.7 Graph Searches
2.7.1 Breadth-First Search
2.7.2 Depth-First Search
2.8 Notes and References
3 Introduction to Matrix Factorizations
3.1 Gaussian Elimination: An Overview
3.1.1 Submatrix LU Factorizations
3.1.2 Column LU Factorizations
3.1.3 Factorizations by Bordering
3.2 Fill-in in Sparse Gaussian Elimination
3.3 Triangular Solves
3.4 Reducibility and Block Triangular Forms
3.5 Block Partitioning
3.5.1 Block Structure Based on Supervariables
3.5.2 Block Structure Using Symbolic Dot Products
3.6 Notes and References
4 Sparse Cholesky Solver: The Symbolic Phase
4.1 Column Replication Principle
4.2 Elimination Trees
4.3 Sparsity Pattern of L
4.4 Topological Orderings
4.5 Leaf Vertices of Row Subtrees
4.6 Supernodes and the Assembly Tree
4.6.1 Fundamental Supernodes
4.7 Notes and References
5 Sparse Cholesky Solver: The Factorization Phase
5.1 Dense Cholesky Factorizations
5.2 Introduction to Sparse Cholesky Factorizations
5.3 Supernodal Sparse Cholesky Factorizations
5.3.1 DAG-Based Approach
5.4 Multifrontal Method
5.5 Parallelism Within Sparse Cholesky Factorizations
5.6 Notes and References
6 Sparse LU Factorizations
6.1 Sparse LU Factorizations and Their Graph Models
6.1.1 Use of Elimination DAGs
6.1.2 Transitive Reduction and Equireachability
6.1.3 Symbolic LU Factorizations Using DAGs
6.1.4 Graph Pruning
6.1.5 Elimination Trees for Nonsymmetric Matrices
6.1.6 Supernodes in LU Factorizations
6.2 LU Multifrontal Method
6.3 Preprocessing Sparse Matrices
6.3.1 Bipartite Graphs and Matchings
6.3.2 Augmenting Paths
6.3.3 Weighted Matchings
6.3.4 Dulmage-Mendelsohn Decompositions
6.4 Notes and References
7 Stability, Ill-Conditioning, and Symmetric Indefinite Factorizations
7.1 Backward Stability
7.2 Pivoting Strategies for Dense Matrices
7.2.1 Partial Pivoting
7.2.2 Complete Pivoting
7.2.3 Rook Pivoting
7.2.4 2 2 Pivoting
7.3 Pivoting Strategies for Sparse Matrices
7.3.1 Threshold Partial Pivoting
7.3.2 Threshold 2 2 Pivoting
7.3.3 Relaxed and Static Pivoting
7.3.4 Special Indefinite Matrices that Avoid Pivoting
7.4 Solving Ill-Conditioned Problems
7.4.1 Iterative Refinement
7.4.2 Scaling to Reduce Ill-Conditioning
Equilibration Scaling
Matching-Based Scalings
Combining Matching-Based Scalings and Orderings
7.5 Notes and References
8 Sparse Matrix Ordering Algorithms
8.1 Local Fill-Reducing Orderings for Symmetric S{A}
8.1.1 Minimum Fill-in (MF) Criterion
8.1.2 Basic Minimum Degree (MD) Algorithm
8.1.3 Use of Indistinguishable Vertices
8.1.4 Degree Outmatching
8.1.5 Cliques and Quotient Graphs
8.1.6 Multiple Minimum Degree (MMD) Algorithm
8.1.7 Approximate Minimum Degree (AMD) Algorithm
8.2 Minimizing the Bandwidth and Profile
8.2.1 The Band and Envelope of a Matrix
8.2.2 Level-Based Orderings
8.2.3 Spectral Orderings
8.3 Local fill-reducing orderings for nonsymmetric S{A}
8.4 Global Nested Dissection Orderings
8.5 Bordered Forms
8.5.1 Doubly Bordered Form
8.5.2 Singly Bordered Form
8.5.3 Ordering to Singly Bordered Form
8.6 Notes and References
9 Algebraic Preconditioners and Approximate Factorizations
9.1 Introduction to Iterative Solvers
9.1.1 Stationary Iterative Methods
9.1.2 Krylov Subspace Methods
9.2 Introduction to Algebraic Preconditioners
9.2.1 Desirable Preconditioner Properties
9.2.2 Simple Algebraic Preconditioners
9.2.3 The Eisenstat Trick
9.3 Some Special Classes of Matrices
9.4 Introduction to Incomplete Factorizations
9.4.1 Incomplete Factorization Breakdown
9.4.2 Perturbing Entries to Prevent Breakdown
9.4.3 Pivoting to Prevent Breakdown
9.5 Factorizations as Preconditioner Components
9.5.1 Polynomial Preconditioning
9.5.2 Schur Complement Approach and Deflation
9.5.3 Domain Decomposition
9.6 Notes and References
10 Incomplete Factorizations
10.1 ILU(0) Factorization
10.2 Basic Incomplete Factorizations
10.3 Incomplete Factorizations Based on the Shortest Fill-Paths
10.4 Modifications Based on Maintaining Row Sums
10.5 Dynamic Compensation
10.6 Memory-Limited Incomplete Factorizations
10.7 Fixed-Point Iterations for Computing ILU Factorizations
10.8 Ordering in Incomplete Factorizations
10.9 Exploiting Block Structure
10.10 Notes and References
11 Sparse Approximate Inverse Preconditioners
11.1 Basic Approaches
11.2 Approximate Inverses Based on Frobenius Norm Minimization
11.2.1 SPAI Preconditioner
11.2.2 FSAI Preconditioner: SPD Case
11.2.3 FSAI Preconditioner: General Case
11.2.4 Determining a Good Sparsity Pattern
11.3 Factorized Approximate Inverses Based on Incomplete Conjugation
11.3.1 AINV Preconditioner: SPD Case
11.3.2 AINV Preconditioner: General Case
11.3.3 SAINV: Stabilization of the AINV Method
11.4 Notes and References
References
Index