A Parallel Approach to the Solution of Sparse Linear Systems

• M. V. Ribeiro Jr. IPRJ
• J. S. Aude UFRJ

DOI: https://doi.org/10.5753/sbac-pad.2000.41208

Resumo

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.

Palavras-chave: sparse linear systems, minimum degree ordering algorithm, Choleski factorization, MPI, parallelism

Referências

Agerwala T. et al., 1995. SP2 System Architecture. IBM Systems Journal, Vol. 34, No. 2 – Scalable Parallel Computing.

Alvarado F. L., Pothen A., Schreiber R., 1998. Highly Parallel Sparse Triangular Solution. Sparse Matrix Computations: Graph Theory Issues and Algorithms, IMA Volumes in Mathematics and its Applications, Springer-Verlag, Univ. of Minnesota.

Amestoy P. R., Davis T. A., Duff I. S., 1996. An Approximate Minimum Degree Algorithm. SIAM J. Matrix Anal. Appl., 17(4), pp. 886–905.

Duff I. S., Reid J. K., 1974. A Comparison of Sparsity Orderings for Obtaining a Pivotal Sequence in Gaussian Elimination. J. Inst. Math. Appl., 14, pp. 281–291.

Duff I. S., Reid J. K., 1982. MA27 – A Set of Fortran Subroutines for Solving Sparse Symmetric Sets of Linear Equations. Tech. report, AERE R10333, HMSO, London.

Duff I. S., Erisman A. M., Reid J. K., 1997. Direct Methods for Sparse Matrices. Oxford University Press, Oxford, UK.

George A., 1973. Nested Dissection of a Regular Finite Element Mesh. SIAM J. Numer. Anal., 10, pp. 345–363.

George J. A., Liu J. W. H., 1978. An Automatic Nested-Dissection Algorithm for Irregular Finite Elements Problems. SIAM J. Numer. Anal., 15, pp. 1053–1069.

George A., Liu J. W. H., 1980. Implementation of the Minimum Degree Algorithm Using Quotient Graphs. ACM Trans. Math. Software, 6, pp. 337–358.

George A., Liu J. W. H., 1980. A Minimum Degree Algorithm. SIAM J. Numer. Anal., 17, pp. 82–299.

George A., Liu J. W. H., 1981. Computer Solution of Large Sparse Positive Definite Systems. Prentice Hall, Englewood Cliffs, NJ.

George A., Liu J. W. H., 1989. The Evolution of the Minimum Degree Ordering Algorithm. SIAM Rev., 31, pp. 1–19.

Kumar V., Grama A., Gupta A., Karypis G., 1994. Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings Publishing Company.

Liu J. W. H., 1985. Modification of the Minimum Degree Ordering by Multiple Elimination. ACM Trans. Math. Software, 11, pp. 141–153.

Pacheco P. S., 1997. Parallel Programming with MPI. Morgan Kaufmann Publishers, San Francisco, California.

Rose D. J., 1970. Symmetric Elimination on Sparse Positive Definite Systems and Potential Flow Network Problem. Ph.D. Thesis, Harvard University.

Rose D. J., 1973. A Graph-theoretic Study of the Numerical Solution of Sparse Positive Definite Systems of Linear Equations. Graph Theory and Computing, R. C. Read (ed.), Academic Press, New York, pp. 183–217.

Saad Y., December 1998. Supercomputing Institute – Research Bulletin, Volume 15, Number 1, University of Minnesota, Minneapolis.

Yannakakis M., 1981. Computing the Minimum Fill-In is NP-Complete. SIAM J. Alg. Disc. Math., 2, pp. 77–79.