Solution of sparse positive definite systems on a hypercube
type: Item
instance of: scholarly article
title: Solution of sparse positive definite systems on a hypercube
zbMATH Open document ID: 0678.65014
DOI: 10.1016/0377-0427(89)90364-6
author: S. H. Smith
published in: Journal of Computational and Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 65Y05
zbMATH DE Number: 4111891
zbMATH Keywords: parallel computation
zbMATH Keywords: large sparse positive definite systems
zbMATH Keywords: multiprocessors
zbMATH Keywords: hypercube
zbMATH Keywords: Cholesky factorization
zbMATH Keywords: symbolic factorization
zbMATH Keywords: numerical factorization
zbMATH Keywords: data structure
zbMATH Keywords: triangular solution
zbMATH Keywords: elimination trees
zbMATH Keywords: pseudo-code algorithms
zbMATH Keywords: numerical experiments
reviewed by: Franco Flandoli
describes a project that uses: MA27
describes a project that uses: symrcm
describes a project that uses: SPARSPAK
describes a project that uses: YSMP
MaRDI profile type: Publication
full work available at URL: 0377-0427(89)90364-6
OpenAlex ID: W2752093666
cites work: Q3930537
cites work: Parallel implementation of multifrontal schemes
cites work: The Multifrontal Solution of Indefinite Sparse Symmetric Linear
cites work: The Multifrontal Solution of Unsymmetric Sets of Linear Equations
cites work: Yale sparse matrix package I: The symmetric codes
cites work: Q4127871
cites work: Q4194361
cites work: Nested Dissection of a Regular Finite Element Mesh
cites work: An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems
cites work: Q3664299
cites work: A Fast Implementation of the Minimum Degree Algorithm Using Quotient Graphs
cites work: A Minimal Storage Implementation of the Minimum Degree Algorithm
cites work: An Optimal Agorithm for Symbolic Factorization of Symmetric Matrices
cites work: Communication results for parallel sparse Cholesky factorization on a hypercube
cites work: The analysis of a nested dissection algorithm
cites work: Modified Cyclic Algorithms for Solving Triangular Systems on Distributed-Memory Multiprocessors
cites work: A Data Structure for Parallel L/U Decomposition
cites work: Generalized Nested Dissection
cites work: A compact row storage scheme for Cholesky factors using elimination trees
cites work: Computational models and task scheduling for parallel sparse Cholesky factorization
cites work: Equivalent Sparse Matrix Reordering by Elimination Tree Rotations
cites work: Modification of the minimum-degree algorithm by multiple elimination
cites work: On General Row Merging Schemes for Sparse Givens Transformations
cites work: Reordering sparse matrices for parallel elimination
cites work: The Role of Elimination Trees in Sparse Factorization
cites work: Comparative Analysis of the Cuthill–McKee and the Reverse Cuthill–McKee Ordering Algorithms for Sparse Matrices
cites work: Q3862948
cites work: The ijk forms of factorization methods. II: Parallel systems
cites work: Q5683627
cites work: A New Implementation of Sparse Gaussian Elimination
cites work: Computing the Minimum Fill-In is NP-Complete
description: scientific article; zbMATH DE number 4111891