Analysis and comparison of two general sparse solvers for distributed memory computers

ABSTRACT

This paper provides a comprehensive study and comparison of two state-of-the-art direct solvers for large sparse sets of linear equations on large-scale distributed-memory computers. One is a multifrontal solver called MUMPS, the other is a supernodal solver called superLU. We describe the main algorithmic features of the two solvers and compare their performance characteristics with respect to uniprocessor speed, interprocessor communication, and memory requirements. For both solvers, preorderings for numerical stability and sparsity play an important role in achieving high parallel efficiency. We analyse the results with various ordering algorithms. Our performance analysis is based on data obtained from runs on a 512-processor Cray T3E using a set of matrices from real applications. We also use regular 3D grid problems to study the scalability of the two solvers.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Patrick R. Amestoy , Timothy A. Davis , Iain S. Duff, An Approximate Minimum Degree Ordering Algorithm, SIAM Journal on Matrix Analysis and Applications, v.17 n.4, p.886-905, Oct. 1996 [doi>10.1137/S0895479894278952]
	2	AMESTOY,P.R.AND DUFF, I. S. 1993. Memory management issues in sparse multifrontal methods on multiprocessors. Int. J. Supercomput. Appl. 7, 64-82.
	3	AMESTOY, P. R., DUFF,I.S.,AND L' EXCELLENT, J.-Y. 2000. Multifrontal parallel distributed symmetric and unsymmetric solvers. Comput. Methods Appl. Mech. Eng., 501-520.
	4	Patrick R. Amestoy , Iain S. Duff , Jean-Yves L'Excellent , Jacko Koster, A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling, SIAM Journal on Matrix Analysis and Applications, v.23 n.1, p.15-41, 2001 [doi>10.1137/S0895479899358194]
	5	AMESTOY, P. R., DUFF,I.S.,AND PUGLISI, C. 1996. Multifrontal QR factorization in a multiprocessor environment. Int. J. Num. Lin. Alg. Appl. 3(4), 275-300.
	6	AMESTOY,P.R.,AND PUGLISI, C. 2000. An unsymmetrized multifrontal LU factorization. Tech. Rep. RT/APO/00/3, ENSEEIHT-IRIT. Also Lawrence Berkeley National Laboratory report LBNL-46474.
	7	ARIOLI, M., DEMMRL,J.,AND DUFF, I. S. 1989. Solving sparse linear systems with sparse backward error. SIAM J. Matrix Anal. Appl. 10, 165-190.
	8	ASHCRAFT,C.AND GRIMES, R. G. 1999. SPOOLES: An object oriented sparse matrix library. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing. San Antonio, Texas. http://www.netlib.org/linalg/spooles.
	9	Michele Benzi , John C. Haws , Miroslav Tuma, Preconditioning Highly Indefinite and Nonsymmetric Matrices, SIAM Journal on Scientific Computing, v.22 n.4, p.1333-1353, 2000 [doi>10.1137/S1064827599361308]
	10	BORCHARDT, J., GRUND,F.,AND HORN, D. 1997. Parallel numerical methods for large systems of differential-algebraic equations in industrial applications. Tech. Rep. 382, Weierstra-Institut fur Angewandte Analysis und Stochastik, Berlin.
	11	James W. Demmel , Stanley C. Eisenstat , John R. Gilbert , Xiaoye S. Li , Joseph W. H. Liu, A Supernodal Approach to Sparse Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.720-755, July 1999 [doi>10.1137/S0895479895291765]
	12	James W. Demmel , John R. Gilbert , Xiaoye S. Li, An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.915-952, Oct. 1999 [doi>10.1137/S0895479897317685]
	13	DUFF,I.S.,GRIMES,R.G.,AND LEWIS, J. G. 1997. The Rutherford-Boeing Sparse Matrix Collection. Tech. Rep. RAL-TR-97-031, Rutherford Appleton Laboratory.
	14	Iain S. Duff , Jacko Koster, The Design and Use of Algorithms for Permuting Large Entries to the Diagonal of Sparse Matrices, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.889-901, Oct. 1999 [doi>10.1137/S0895479897317661]
	15	I. S. Duff , J. Koster, On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix, SIAM Journal on Matrix Analysis and Applications, v.22 n.4, p.973-996, 2000 [doi>10.1137/S0895479899358443]
	16	Cong Fu , Xiangmin Jiao , Tao Yang, Efficient Sparse LU Factorization with Partial Pivoting on Distributed Memory Architectures, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.109-125, February 1998 [doi>10.1109/71.663864]
	17	John R. Gilbert , Joseph W. H. Liu, Elimination structures for unsymmetric sparse LU factors, SIAM Journal on Matrix Analysis and Applications, v.14 n.2, p.334-352, April 1993 [doi>10.1137/0614024]
	18	GUPTA, A. 2000. WSMP: Watson Sparse Matrix Package. Tech. rep., IBM research division, T. J. Watson Research Center, Yorktown Heights. http://www.cs.umn.edu/ agupta/wsmp.html.
	19	Anshul Gupta , George Karypis , Vipin Kumar, Highly Scalable Parallel Algorithms for Sparse Matrix Factorization, IEEE Transactions on Parallel and Distributed Systems, v.8 n.5, p.502-520, May 1997 [doi>10.1109/71.598277]
	20	Michael T. Heath , Esmond Ng , Barry W. Peyton, Parallel algorithms for sparse linear systems, SIAM Review, v.33 n.3, p.420-460, Sept. 1991 [doi>10.1137/1033099]
	21	HEATH,M.T.AND RAGHAVAN, P. 1997. Performance of a fully parallel sparse solver. Int. J. Supercomput. Appl. 11, 1, 49-64.
	22	Pascal Hénon , Pierre Ramet , Jean Roman, A Mapping and Scheduling Algorithm for Parallel Sparse Fan-In Numerical Factorization, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.1059-1067, August 31-September 03, 1999
	23	HSL. 2000. A collection of Fortran codes for large scale scientific computation. http://www. cse.clrc.ac.uk/Activity/HSL.
	24	KARYPIS,G.AND KUMAR, V. 1998. METIS "A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices" Version 4.0. University of Minnesota.
	25	Xiaoye S. Li , James W. Demmel, Making sparse Gaussian elimination scalable by static pivoting, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-17, November 07-13, 1998, San Jose, CA
	26	LI,X.S.AND DEMMEL, J. W. 1999. A scalable sparse direct solver using static pivoting. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing. San Antonio, Texas. http://www.siam.org/meetings/pp99/.
	27	LI,X.S.,DEMMEL,J.W.,BAILEY, D. H., HENRY, G., HIDA, Y., ISKANDAR, J., KAHAN, W., KAPUR, A., MARTIN,M.C.,TUNG,T.,AND YOO, D. J. 2000. Design, Implementation and Testing of Extended and Mixed Precision BLAS. Tech. Rep. LBNL-45991, Lawrence Berkeley National Laboratory, Berkeley. June. (also LAPACK Working Note #149). Submitted to ACM Trans. Math. Soft.
	28	Joseph W. H. Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Transactions on Mathematical Software (TOMS), v.11 n.2, p.141-153, June 1985 [doi>10.1145/214392.214398]
	29	NAGEL, W. E., ARNOLD, A., WEBER, M., HOPPE, H.-C., AND SOLCHENRACH, K. 1996. VAMPIR: Visualization and Analysis of MPI resources. Supercomput. 12, 1 (Jan.), 69-80.
	30	Esmond Ng , Barry W. Peyton, A supernodal Cholesky factorization algorithm for shared-memory multiprocessors, SIAM Journal on Scientific Computing, v.14 n.4, p.761-769, July 1993 [doi>10.1137/0914048]
	31	ROTHBEEG, E. 1994 Efficient sparse Cholesky factorization on distributed-memory multiprocessors. In Proceedings Fifth SIAM Conference on Applied Linear Algebra, J. Lewis Ed. SIAM Press, Philadelphia, 141.
	32	SCHENK, O., GARTNER, K., AND FICHTNER, W. 2000 Efficient sparse LU factorization with left-right looking strategy on shared memory multiprocessors. BIT 40, 1, 158-176.