A LOCALLY OPTIMIZED REORDERING ALGORITHM AND ITS APPLICATION TO A PARALLEL SPARSE LINEAR-SYSTEM SOLVER

A coarse-grain parallel solver for systems of linear algebraic equatio ns with general sparse matrices by Gaussian elimination is discussed. Before the factorization two other steps are performed. A reordering a lgorithm is used during the first step in order to obtain a permuted m atrix with as many zero elements under the main diagonal as possible. During the second step the reordered matrix is partitioned into blocks for asynchronous parallel processing (normally the number of blocks i s equal to the number of processors). It is possible to obtain blocks with nearly the same number of rows, because there is no requirement t o produce square diagonal blocks. The first step is much more importan t than the second one and has a significant influence on the performan ce of the solver. A straightforward implementation of the reordering a lgorithm will result in O(n2) operations. By using binary trees this c ost can be reduced to O(NZ log n), where NZ is the number of non-zero elements in the matrix and n is its order (normally NZ is much smaller than n2). Some experiments on parallel computers with shared memory h ave been performed. The results show that a solver based on the propos ed reordering performs better than another solver based on a cheaper ( but at the same time rather crude) reordering whose cost is only O(NZ) operations.