Parallel Block Methods for Sparse symmetric Linear Systems of Equations
Abstract
In this work, we present a new graph-theoretic algorithm for the purpose of exploiting parallelism in the sparsity structure of large symmetric matrices. The key objectives of the algorithm are to identify full blocks in a symmetric matrix M that can be factored independently of each other and also to keep the number of fill elements generated in the process of factoring the blocks as small as possible. The graph-theoretic algorithm has running-time proportional to the number of vertices and edges in an undirected graph, making the algorithm very suitable for extremely large sparse symmetric problems. Using this graph-theoretic algorithm, we develop a block method for the solution of sparse symmetric linear systems of equations. This block method takes full advantage of the parallel capabilities of high-performance computers and makes good use of the standard routines in the quality linear algebra library LAPACK to perform the numerical computations in terms of Level 2 and Level 3 Basic Linear Algebra Subprograms (BLAS) operations. There are many defense critical applications in the Navy in the areas of signal processing, structural mechanics, and computational hydrodynamics that give rise to large sparse symmetric matrices. We strongly recommend the implementation of the presented algorithms and their application to these problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1991
- Accession Number
- ADA242315
Entities
People
- A. K. Kevorkian