Matrix Algorithms

Contents:

• 1 Matrix Nomenclature
• 2 Matrix Algebra
  • 2.1 Matrix Equality
  • 2.2 Matrix Transposition
  • 2.3 Scalar Multiplication
  • 2.4 Matrix Addition
  • 2.5 Matrix Multiplication
  • 2.6 Inverse of a Matrix
  • 2.7 Rank of a Matrix
  • 2.8 Similarity Transformations
  • 2.9 Partitioning a Matrix
• 3 Linear Systems
  • 3.1 Solving Fully Determined Systems
  • 3.2 Solving Underdetermined Systems
  • 3.3 Solving Overdetermined Systems
  • 3.4 Computational Complexity of Linear Systems
• 4 LU Decomposition
  • 4.1 Gaussian Elimination
  • 4.2 Doolittle’s LU Factorization
  • 4.3 Crout’s LU Factorization
  • 4.4 LDU Factorization
  • 4.5 Numerical Instability During Factorization
  • 4.6 Pivoting Strategies for Numerical Stability
  • 4.7 Diagonal Dominance and Pivoting
  • 4.8 Partial Pivoting
  • 4.9 Complete Pivoting
  • 4.10 Computational Complexity of Pivoting
  • 4.11 Scaling Strategies
• 5 Solving Triangular Systems
  • 5.1 Forward Substitution
  • 5.2 Backward Substitution
  • 5.3 Outer Product Formulation
• 6 Factor Update
  • 6.1 LDU Factor Update
  • 6.2 LU Factor Update
  • 6.3 Additional Considerations
• 7 Symmetric Matrices
  • 7.1 LDU Decomposition of Symmetric Matrices
  • 7.2 LU Decomposition of Symmetric Matrices
  • 7.3 Symmetric Matrix Data Structures
  • 7.4 Doolittle’s Method for Symmetric Matrices
  • 7.5 Crout’s Method for Symmetric Matrices
  • 7.6 Forward Substitution for Symmetric Systems
    • 7.6.1 Forward Substitution Using Lower Triangular Factors
    • 7.6.2 Forward Substitution Using Upper Triangular Factors
  • 7.7 Backward Substitution for Symmetric Systems
    • 7.7.1 Back Substitution Using Upper Triangular Factors
    • 7.7.2 Back Substitution Using Lower Triangular Factors
  • 7.8 Symmetric Factor Update
    • 7.8.1 Symmetric LDU Factor Update
    • 7.8.2 Symmetric LU Factor Update
• 8 Sparse Matrices
  • 8.1 Sparse Matrix Methodology
  • 8.2 Abstract Data Types for Sparse Matrices
    • 8.2.1 Sparse Matrix
    • 8.2.2 Adjacency List
    • 8.2.3 Reduced Graph
    • 8.2.4 List
    • 8.2.5 Mapping
    • 8.2.6 Vector
  • 8.3 Pivoting To Preserve Sparsity
    • 8.3.1 Markowitz Pivot Strategy
    • 8.3.2 Minimum Degree Pivot Strategy
  • 8.4 Symbolic Factorization of Sparse Matrices
    • 8.4.1 Symbolic Factorization with Minimum Degree Pivot
    • 8.4.2 Computational Complexity of Symbolic Factorization
  • 8.5 Creating PAP^T from a Symbolic Factorization
  • 8.6 Numeric Factorization of Sparse Matrices
  • 8.7 Solving Sparse Linear Systems
    • 8.7.1 Permute the Constant Vector
    • 8.7.2 Sparse Forward Substitution
    • 8.7.3 Sparse Backward Substitution
    • 8.7.4 Permute the Solution Vector
  • 8.8 Sparse LU Factor Update
    • 8.8.1 Factorization Path of a Singleton Update
    • 8.8.2 Revising LU after a Singleton Update
• 9 Implementation Notes
  • 9.1 Sparse Matrix Representation
  • 9.2 Database Cache Performance
    • 9.2.1 Sequential Matrix Element Retrieval
    • 9.2.2 Arbitrary Matrix Element Retrieval
    • 9.2.3 Arbitrary Matrix Element Update
    • 9.2.4 Matrix Element Insertion
    • 9.2.5 Matrix Element Deletion
    • 9.2.6 Empirical Performance Measurements
  • 9.3 Floating Point Performance
  • 9.4 Auxiliary Store
• References

List of Tables:

• 1 Database Cache Benchmarks
• 2 Floating Point Benchmarks
• 3 Math Library Benchmarks

List of Figures:

• 1 Computational Sequence of Doolittle’s Method
• 2 Computational Sequence of Crout’s Method
• 3 Computational Sequence of Tinney’s LDU Decomposition
• 4 Matrix Tuple Structure
• 5 Sparse Matrix Representation

List of Algorithms:

• 1 Gaussian Elimination
• 2 Doolittle’s LU Decompostion
• 3 Crout’s LU Decomposition
• 4 Forward Substitution
• 5 Backward Substitution
• 6 Forward Substitution - Outer Product
• 7 Back Substitution - Outer Product
• 8 LDU Factor Update
• 9 LU Factor Update
• 10 Symmetric Doolittle’s Method
• 11 Symmetric Doolittle’s Method - Array Based
• 12 Symmetric Crout’s Method
• 13 Symmetric Crout’s Method - Array Based
• 14 Symmetric Forward Substitution via Upper Triangular Factors
• 15 Symmetric Forward Substitution using U with Array Storage
• 16 Symmetric Forward Substitution using U, Outer Product
• 17 Symmetric Forward Substitution using U, Outer Product, Array
• 18 Symmetric Back Substitution using Lower Triangular Factors
• 19 Symmetric Backward Substitution using L with Array Storage
• 20 Symmetric LDU Factor Update
• 21 Symmetric LU Factor Update
• 22 Symbolic Factorization of a Sparse Matrix ^†
• 23 Construct PAP^T of a Sparse Matrix ^†
• 24 Construct PAP^T of a Sparse Symmetric Matrix ^†
• 25 LU Decomposition of a Sparse Matrix by Doolittle’s Method ^†
• 26 LU Decomposition of Sparse Symmetric Matrix by Doolittle’s Method ^†
• 27 Permute b to order P
• 28 Sparse Forward Substitution
• 29 Symmetric Sparse Forward Substitution
• 30 Sparse Back Substitution
• 31 Permute x to order Q
• 32 Factorization Path
• 33 Symmetric Factorization Path
• 34 Structurally Symmetric Sparse LU Factor Update
• 35 Symmetric Sparse LU Factor Update