Direct methods for sparse matrices - Direct methods for sparse matrices -

Introduction Graph theory Example of a sparse matrix Modern computer architectures Computational performance Problem formulation Sparse matrix test collections Exercises SPARSE MATRICES: STORAGE SCHEMES AND SIMPLE OPERATIONS Introduction Sparse vector storage Inner product of two packed vectors Adding packed vectors Use of full-sized arrays Coordinate scheme for storing sparse matrices Sparse matrix as a collection of sparse vectors Sherman’s compressed index scheme Linked lists Sparse matrix in column-linked list Sorting algorithms The counting sort Heap sort Transforming the coordinate scheme to other forms Access by rows and columns Supervariables Matrix by vector products Matrix by matrix products Permutation matrices Clique (or finite-element) storage Comparisons between sparse matrix structures Exercises GAUSSIAN ELIMINATION FOR DENSE MATRICES: THE ALGEBRAIC PROBLEM Introduction Solution of triangular systems Gaussian elimination Required row interchanges Relationship with LU factorization Dealing with interchanges LU factorization of a rectangular matrix Computational sequences, including blocking Symmetric matrices Multiple right-hand sides and inverses Computational cost Partitioned factorization Solution of block triangular systems Exercises GAUSSIAN ELIMINATION FOR DENSE MATRICES: NUMERICAL CONSIDERATIONS Introduction Computer arithmetic error Algorithm instability Controlling algorithm stability through pivoting Partial pivoting Threshold pivoting Rook pivoting Full pivoting The choice of pivoting strategy Orthogonal factorization Partitioned factorization Monitoring the stability Special stability considerations Solving indefinite symmetric systems Ill-conditioning: introduction Ill-conditioning: theoretical discussion Ill-conditioning: automatic detection The LINPACK condition estimator Hager’s method Iterative refinement Scaling Automatic scaling Scaling so that all entries are close to one Scaling norms I-matrix scaling Exercises Research exercises Introduction Numerical stability in sparse Gaussian elimination Trade-offs between numerical stability and sparsity Incorporating rook pivoting x 2 pivoting Other stability considerations Estimating condition numbers in sparse computation Orderings Block triangular matrix Local pivot strategies Band and variable band ordering Dissection Features of a code for the solution of sparse equations Input of data The ANALYSE phase The FACTORIZE phase The SOLVE phase Output of data and analysis of results Relative work required by each phase Multiple right-hand sides Computation of entries of the inverse Matrices with complex entries Writing compared with using sparse matrix software Exercises REDUCTION TO BLOCK TRIANGULAR FORM Introduction Finding the block triangular form in three stages Looking for row and column singletons Finding a transversal Background Transversal extension by depth-first search Analysis of the depth-first search transversal algorithm Implementation of the transversal algorithm Symmetric permutations to block triangular form Background The algorithm of Sargent and Westerberg Tarjan’s algorithm Implementation of Tarjan’s algorithm Essential uniqueness of the block triangular form Experience with block triangular forms Maximum transversals Weighted matchings The Dulmage—Mendelsohn decomposition Exercises Research exercise LOCAL PIVOTAL STRATEGIES FOR SPARSE MATRICES Introduction The Markowitz criterion Minimum degree (Tinney scheme 2)A priori column ordering Simpler strategies A more ambitious strategy: minimum fill-in Effect of tie-breaking on the minimum degree algorithm Numerical pivoting Sparsity in the right-hand side and partial solution Variability-type ordering The symmetric indefinite case Exercises Research exercises ORDERING SPARSE MATRICES FOR BAND SOLUTION Introduction Band and variable-band matrices Small bandwidth and profile: Cuthill—McKee algorithm Small bandwidth and profile: the starting node Small bandwidth and profile: Sloan algorithm Spectral ordering for small profile Calculating the Fiedler vector Hybrid orderings for small bandwidth and profile Hager’s exchange methods for profile reduction Blocking the entries of a symmetric variable-band matrix Refined quotient trees Incorporating numerical pivoting The fixed bandwidth case The variable bandwidth case Conclusion Exercises ORDERINGS BASED ON DISSECTION Introduction One-way dissection Finding the dissection cuts for one-way dissection Nested dissection Introduction to finding dissection cuts Multisection Comparing nested dissection with minimum degree Edge and vertex separators Methods for obtaining dissection sets Obtaining an initial separator set Refining the separator set Graph partitioning algorithms and software Dissection techniques for unsymmetric systems Background Graphs for unsymmetric matrices Ordering to singly bordered block diagonal form The performance of the ordering Some concluding remarks Exercises Research exercise IMPLEMENTING GAUSSIAN ELIMINATION WITHOUT SYMBOLIC FACTORIZE Introduction Markowitz ANALYSE FACTORIZE without pivoting FACTORIZE with pivoting SOLVE Hyper-sparsity and linear programming Switching to full form Loop-free code Interpretative code The use of drop tolerances to preserve sparsity Exploitation of parallelism Various parallelization opportunities Parallelizing the local ordering and sparse factorization steps Exercises IMPLEMENTING GAUSSIAN ELIMINATION WITH SYMBOLIC FACTORIZE Introduction Minimum degree ordering Approximate minimum degree ordering Dissection orderings Numerical FACTORIZE using static data structures Numerical pivoting within static data structures Band methods Variable-band (profile) methods Frontal methods: introduction Frontal methods: SPD finite-element problems Frontal methods: general finite-element problems Frontal methods for non-element problems Exploitation of parallelism Exercises Research exercise GAUSSIAN ELIMINATION USING TREES Introduction Multifrontal methods for finite-element problems Elimination and assembly trees The elimination tree Using the assembly tree for factorization The efficient generation of elimination trees Constructing the sparsity pattern of U The patterns of data movement Manipulations on assembly trees Ordering of children Tree rotations Node amalgamation Multifrontal methods: symmetric indefinite problems Exercises GRAPHS FOR SYMMETRIC AND UNSYMMETRIC MATRICES Introduction Symbolic analysis on unsymmetric systems Numerical pivoting using dynamic data structures Static pivoting Scaling and reordering The aims of scaling Scaling and reordering a symmetric matrix The effect of scaling Discussion of scaling strategies Supernodal techniques using assembly trees Directed acyclic graphs Parallel issues Parallel factorization Parallelization levels The balance between tree and node parallelism Use of memory Static and dynamic mapping Static mapping and scheduling Dynamic scheduling Codes for shared and distributed memory computers The use of low-rank matrices in the factorization Using rectangular frontal matrices with local pivoting Trees for unsymmetric matrices Exercises Research exercises THE SOLVE PHASE Introduction SOLVE at the node level Use of the tree by the SOLVE phase Sparse right-hand sides Multiple right-hand sides Computation of null-space basis Parallelization of SOLVE Parallelization of dense solve Order of access to the tree nodes Experimental results Exercises Research exercise OTHER SPARSITY-ORIENTED ISSUES Introduction The matrix modification formula The basic formula The stability of the matrix modification formula Applications of the matrix modification formula Application to stability corrections Building a large problem from subproblems Comparison with partitioning Application to sensitivity analysis The model and the matrix Model reduction Model reduction with a regular submodel Sparsity constrained backward error analysis Why the inverse of a sparse irreducible matrix is dense Computing entries of the inverse of a sparse matrix Sparsity in nonlinear computations Estimating a sparse Jacobian matrix Updating a sparse Hessian matrix Approximating a sparse matrix by a positive-definite one Solution methods based on orthogonalization Hybrid methods Domain decomposition Block iterative methods Exercises Research exercises