Parallel Solution of Linear Systems with Striped Sparse Matrices. Part 1. VLSI Networks for Striped Matrices.
Abstract
The multiplication of a matrix by a vector and the solution of triangular linear systems are the most demanding operations in the majority of iterative techniques for the solution of linear systems. Data-driven VLSI networks that perform these two operations, efficiently, for sparse matrices are introduced. In order to avoid computations that involve zero operands, the non-zero elements in a sparse matrix are organized in the form of non intersecting stripes, and only the elements within the stripe structure of the matrix are manipulated. Detailed analysis of the networks proves that both operations may be completed in n global cycles with minimal communication overhead, where n is the order of the linear system. The number of cells in each network as well as the communication overhead are determined by the stripe structure of the matrix. A companion paper examines this structure for the class of sparse matrices generate din Finite Element Analysis. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1986
- Accession Number
- ADA166046
Entities
People
- Rami Melhem
Organizations
- University of Pittsburgh