An optimal parallel algorithm for sparse matrix bandwidth reduction on a linear array

Abstract

A simple and efficient algorithm for the bandwidth reduction of sparse symmetric matrices is proposed. It involves column-row permutations and is well-suited to map onto the linear array topology of the SIMD architectures. The efficiency of the algorithm is compared with the other existing algorithms. The interconnectivity and the memory requirement of the linear array are discussed and the complexity of its layout area is derived. The parallel version of the algorithm mapped onto the linear array is then introduced and is explained with the help of an example. The optimality of the parallel algorithm is proved by deriving the time complexities of the algorithm on a single processor and the linear array.

Keywords:

• Linear array
• sparse matrix
• bandwidth reduction
• parallel algorithm
• band form
• complexity analysis
• layout area
• SIMD

C.R. Categories:

• G.1.0
• G.1.3
• G.4.0