Parallel solution of linear systems with striped sparse matrices (Q1102072)

The multiplication of a vector by a matrix and the solution of triangular linear systems are the two basic ingredients in most iterative solvers. In order to avoid computations that involve zero operands, the non-zero elements in a sparse matrix are organized in the form of non-overlapping stripes, and only the elements within the stripe structure of the matrix are manipulated. This paper contains (i) the definition of the stripe structure of a general sparse matrix, (ii) a description of a VLSI network which uses the stripe structure in the parallel multiplication of a vector by a matrix, (iii) some results concerning the property of non-overlapping stripes, (iv) an extension of (ii) to a network for the solution of triangular linear systems.