Parallel Solution of Linear Systems with Striped Sparse Matrices. Part 1. VLSI Networks for Striped Matrices

摘要

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 tehcniques 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 opertaions 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 sturcture of the matrix. A companion paper examines this structure for the class of sparse matrices generated in Finite Element Analysis. (Author)