A Parallel Approach to the Solution of Sparse Linear Systems - Ribeiro Jr., M. V.; Aude, J. S. (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2000)
This paper discusses the parallel implementation of direct methods for the solution of positive definite sparse linear systems. The adopted procedure consists of four phases: ordering with the use of the approximate minimum degree algorithm; symbolic factorization; Choleski numerical factorization; and solution of the final triangular system. It has been implemented on a 6 processor IBM SP2 platform with the use of MPI. Only the Choleski factorization phase has been implemented in parallel. However, different PESE permutation matrices are concurrently processed during the orderin and symbolic factorization phases by the available processors. The result with the lowest number of fill-ins is the one processed by the numerical factorization. The system parformance has been evaluated with the use of matrices extracted from the Harwell-Boeing set. Speed-up factors above 4 have been achieved with 6 processors. In addition, over 30% fill-in reduction has been obtained by the concurrent processing of alternate ordering possibilities.