×

Solution of sparse positive definite systems on a hypercube. (English) Zbl 0678.65014

The paper provides a detailed overview of an experimental package for solving large sparse positive definite systems of the form \(Ax=b\) on multiprocessors with a hypercube interconnection network. The method of Cholesky factorization \(A=LL^ T\) is used, involving four steps: (1) ordering: determine a permutation matrix P so that \(PAP^ T\) has sparse Cholesky factor L; (2) symbolic factorization: determine the structure of L and set up a data structure that exploits the sparsity of L; (3) numerical factorization: place the nonzeros of A into the data structure and then compute L; (4) triangular solution: using L, solve the triangular systems \(Lu=Pb\), \(L^ Tv=u\) and set \(x=P^ Tv.\)
The article treats all these steps in detail, explains the role of elimination trees in the exploitation of sparsity and the identification of parallelism, provides pseudo-code algorithms, and presents numerical experiments run on an Intel iPSC multiprocessor showing that the reduction in execution time as the number of processors increases is much less significant for steps 1, 2, and 4 above, compared to the numerical factorization (step 3).
Reviewer: F.Flandoli

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation

Software:

symrcm; SPARSPAK; MA27; YSMP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chu, E. C.H.; George, J. A.; Liu, J. W.-H.; Ng, E. G.-Y., User’s guide for SPARSPAK-A: Waterloo sparse linear equations package, (Technical Report CS-84-36 (1984), University of Waterloo: University of Waterloo Waterloo, Ontario)
[2] Duff, I. S., Full matrix techniques in sparse Gaussian elimination, (Watson, G. A., Lecture Notes in Mathematics, 912 (1982), Springer: Springer Berlin), 71-84 · Zbl 0475.65014
[3] Duff, I. S., Parallel implementation of multifrontal schemes, Parallel Comput., 3, 193-204 (1986) · Zbl 0628.65018
[4] Duff, I. S.; Johnsson, L., The effect of orderings on the parallelization of sparse code, (Technical Memorandum (1986), Mathematical and Computer Science Division, Argonne National Laboratory)
[5] Duff, I. S.; Reid, J. K., MA27 — A set of FORTRAN subroutines for solving sparse symmetric sets of linear equations, (Technical Report AERE R 10533 (1982), Harwell) · Zbl 0515.65022
[6] Duff, I. S.; Reid, J. K., The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Software, 9, 302-325 (1983) · Zbl 0515.65022
[7] Duff, I. S.; Reid, J. K., The multifrontal solution of unsymmetric sets of linear equations, SIAM J. Sci. Statist. Comput., 5, 633-641 (1984) · Zbl 0557.65017
[8] Eisenstat, S. C.; Gursky, M. C.; Schultz, M. H.; Sherman, A. H., The Yale sparse matrix package I. The symmetric codes, Internat. J. Numer. Meth. Engrg., 18, 1145-1151 (1982) · Zbl 0492.65012
[9] Eisenstat, S. C.; Schultz, M. H.; Sherman, A. H., Applications of an element model for Gaussian elimination, (Bunch, J. R.; Rose, D. J., Sparse Matrix Computations (1976), Academic Press: Academic Press New York), 85-96 · Zbl 0356.65024
[10] Eisenstat, S. C.; Schultz, M. H.; Sherman, A. H., Software for sparse Gaussian elimination with limited core storage, (Duff, I. S.; Stewart, G. W., Sparse Matrix Proceedings (1978), SIAM Press: SIAM Press Philadelphia, PA), 135-153 · Zbl 0407.65012
[11] George, J. A., Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10, 345-363 (1973) · Zbl 0259.65087
[12] George, J. A.; Liu, J. W.-H., An automatic nested dissection algorithm for irregular finite element problems, SIAM J. Numer. Anal., 15, 1053-1069 (1978) · Zbl 0408.65064
[13] George, J. A.; Liu, J. W.-H., Computer Solution of Large Sparse Positive Definite Systems (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0516.65010
[14] George, J. A.; Liu, J. W.-H., A fast implementation of the minimum degree algorithm using quotient graphs, ACM Trans. Math. Software, 6, 337-358 (1980) · Zbl 0467.65011
[15] George, J. A.; Liu, J. W.-H., A minimal storage implementation of the minimum degree algorithm, SIAM J. Numer. Anal., 17, 282-299 (1980) · Zbl 0424.65006
[16] George, J. A.; Liu, J. W.-H., An optimal algorithm for symbolic factorization of symmetric matrices, SIAM J. Comput., 9, 583-593 (1980) · Zbl 0452.68049
[17] George, J. A.; Liu, J. W.-H.; Ng, E. G.-Y., Communication results for parallel sparse Cholesky factorization on a hypercube, Parallel Comput., 10, 287-298 (1989) · Zbl 0687.65024
[18] Gilbert, J. R.; Tarjan, R. E., The analysis of a nested dissection algorithm, Numer. Math., 50, 377-404 (1987) · Zbl 0645.65012
[19] Heath, M. T.; Romine, C. H., Parallel solution of triangular systems on distributed memory-multiprocessors, (Technical Report ORNL/TM-10384 (1987), Mathematical Sciences Section, Oak Ridge National Laboratory: Mathematical Sciences Section, Oak Ridge National Laboratory Oak Ridge, TN 37831) · Zbl 0645.65014
[20] Jess, J. A.G.; Kees, H. G.M., A data structure for parallel L/U decomposition, IEEE Trans. Comput., 31, 231-239 (1982) · Zbl 0479.68034
[21] Lipton, R. J.; Rose, D. J.; Tarjan, R. E., Generalized nested dissection, SIAM J. Numer. Anal., 16, 346-358 (1979) · Zbl 0435.65021
[22] Liu, J. W.-H., A compact row storage scheme for Cholesky factors using elimination trees, ACM Trans. Math. Software, 12, 127-148 (1986) · Zbl 0605.65015
[23] Liu, J. W.-H., Computational models and task scheduling for parallel sparse Cholesky factorization, Parallel Comput., 3, 327-342 (1986) · Zbl 0609.65014
[24] Liu, J. W.-H., Equivalent sparse matrix reordering by elimination tree rotations, SIAM J. Sci. Statist. Comput., 9, 424-444 (1988) · Zbl 0651.65016
[25] Liu, J. W.-H., Modification of the minimum degree algorithm by multiple elimination, ACM Trans. Math. Software, 11, 141-153 (1985) · Zbl 0568.65015
[26] Liu, J. W.-H., On general row merging schemes for sparse Givens transformations, SIAM J. Sci. Statist. Comput., 7, 1190-1211 (1986) · Zbl 0605.65031
[27] Liu, J. W.-H., Reordering sparse matrices for parallel elimination, (Technical Report CS-87-01 (1987), Dept. of Computer Science, York University) · Zbl 0677.65023
[28] Liu, J. W.-H., The role of elimination trees in sparse factorization, (Technical Report CS-87-12 (1987), Dept. of Computer Science, York University) · Zbl 0697.65013
[29] Liu, J. W.-H.; Sherman, A. H., Comparative analysis of the Cuthill-McKee and reverse Cuthill-McKee ordering algorithms for sparse matrices, SIAM J. Numer. Anal., 13, 198-213 (1976) · Zbl 0331.65022
[30] Parter, S. V., The use of linear graphs in Gaussian elimination, SIAM Rev., 3, 364-369 (1961)
[31] Peters, F. J., Sparse Matrices and Substructures, (Mathematical Centre Tracts, 119 (1980), Mathematisch Centrum: Mathematisch Centrum Amsterdam) · Zbl 0427.65017
[32] Romine, C. H.; Ortega, J. M., Parallel solution of triangular systems of equations, Parallel Comput., 6, 109-114 (1988) · Zbl 0665.65024
[33] Rose, D. J., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, (Read, R. C., Graph Theory and Computing (1972), Academic Press: Academic Press New York), 183-217
[34] Schreiber, R., A new implementation of sparse Gaussian elimination, ACM Trans. Math Software, 8, 256-276 (1982) · Zbl 0491.65013
[35] Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. Algebra Disc. Methods, 2, 77-79 (1981) · Zbl 0496.68033
[36] Zmikewski, E.; Gilbert, J. R., A parallel algorithm for large sparse Cholesky factorization on a multiprocessor, (Technical Report TR 86-733 (1986), Dept. of Computer Science, Cornell University: Dept. of Computer Science, Cornell University Ithaca, NY)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.