Solution of sparse positive definite systems on a hypercube
The paper provides a detailed overview of an experimental package for solving large sparse positive definite systems of the form \(Ax=b\) on multiprocessors with a hypercube interconnection network. The method of Cholesky factorization \(A=LL^ T\) is used, involving four steps: (1) ordering: determine a permutation matrix P so that \(PAP^ T\) has sparse Cholesky factor L; (2) symbolic factorization: determine the structure of L and set up a data structure that exploits the sparsity of L; (3) numerical factorization: place the nonzeros of A into the data structure and then compute L; (4) triangular solution: using L, solve the triangular systems \(Lu=Pb\), \(L^ Tv=u\) and set \(x=P^ Tv.\) The article treats all these steps in detail, explains the role of elimination trees in the exploitation of sparsity and the identification of parallelism, provides pseudo-code algorithms, and presents numerical experiments run on an Intel iPSC multiprocessor showing that the reduction in execution time as the number of processors increases is much less significant for steps 1, 2, and 4 above, compared to the numerical factorization (step 3).
- A compact row storage scheme for Cholesky factors using elimination trees
- A Data Structure for Parallel L/U Decomposition
- A Fast Implementation of the Minimum Degree Algorithm Using Quotient Graphs
- A Minimal Storage Implementation of the Minimum Degree Algorithm
- A New Implementation of Sparse Gaussian Elimination
- An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems
- An Optimal Agorithm for Symbolic Factorization of Symmetric Matrices
- Communication results for parallel sparse Cholesky factorization on a hypercube
- Comparative Analysis of the Cuthill–McKee and the Reverse Cuthill–McKee Ordering Algorithms for Sparse Matrices
- Computational models and task scheduling for parallel sparse Cholesky factorization
- Computing the Minimum Fill-In is NP-Complete
- Equivalent Sparse Matrix Reordering by Elimination Tree Rotations
- Generalized Nested Dissection
- scientific article; zbMATH DE number 3816913 (Why is no real title available?)
- scientific article; zbMATH DE number 3666074 (Why is no real title available?)
- scientific article; zbMATH DE number 3746322 (Why is no real title available?)
- scientific article; zbMATH DE number 3555309 (Why is no real title available?)
- scientific article; zbMATH DE number 3633617 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- Modification of the minimum-degree algorithm by multiple elimination
- Modified Cyclic Algorithms for Solving Triangular Systems on Distributed-Memory Multiprocessors
- Nested Dissection of a Regular Finite Element Mesh
- On General Row Merging Schemes for Sparse Givens Transformations
- Parallel implementation of multifrontal schemes
- Reordering sparse matrices for parallel elimination
- The analysis of a nested dissection algorithm
- The ijk forms of factorization methods. II: Parallel systems
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- The Multifrontal Solution of Unsymmetric Sets of Linear Equations
- The Role of Elimination Trees in Sparse Factorization
- Yale sparse matrix package I: The symmetric codes
- scientific article; zbMATH DE number 3885206 (Why is no real title available?)
- A LINEAR ARRAY FOR LARGE SPARSE MATRIX OPERATIONS - I CHOLESKY FACTORIZATION
- A LINEAR ARRAY FOR LARGE SPARSE MATRIX OPERATIONS – II TRIANGULAR SYSTEM SOLVERS AND MATRIX MULTIPLICATION
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- A Polyhedral Method for Sparse Systems with Many Positive Solutions
- A latency tolerant hybrid sparse solver using incomplete Cholesky factorization
- A survey of direct methods for sparse linear systems
- Task scheduling for parallel sparse Cholesky factorization
This page was built for publication: Solution of sparse positive definite systems on a hypercube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124265)
