Abstract
We present and analyze a general algorithm which computes efficient static schedulings of block computations for parallel sparse linear factorization. Our solver, based on a supernodal fan-in approach, is fully driven by this scheduling. We give an overview of the algorithms and present performance results on a 16-node IBM-SP2 with 66 MHz Power2 thin nodes for a collection of grid and irregular problems.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
P. Amestoy, T. Davis, and I. Duff. An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. and Appl., 17:886–905, 1996.
C. Ashcraft. The fan-both family of column-based distributed Cholesky factorization algorithms. Graph Theory and Sparse Matrix Computation, IMA, Springer-Verlag, 56:159–190, 1993.
C. Ashcraft, S.C. Eisenstat, and J. W.-H. Liu. A fan-in algorithm for distributed sparse numerical factorization. SIAM J. Sci. Stat. Comput., 11(3):593–599, 1990.
C. Ashcraft, S.C. Eisenstat, J. W.-H. Liu, and A. Sherman. A comparison of three column based distributed sparse factorization schemes. In Proc. Fifth SIAM Conf. on Parallel Processing for Scientific Computing, 1991.
P. Charrier and J. Roman. FrAlgorithmique et calculs de complexité pour un solveur de type dissections emboîtées. Numerische Mathematik, 55:463–476, 1989.
I.S. Duff. Sparse numerical linear algebra: direct methods and preconditioning. Technical Report TR/PA/96/22, CERFACS, 1996.
G.A. Geist and E. Ng. Task scheduling for parallel sparse Cholesky factorization. Internat. J. Parallel Programming, 18(4):291–314, 1989.
F. Pellegrini and J. Roman. Sparse matrix ordering with scotch. In Proceedings of HPCN’97, itVienna, LNCS 1225, pages 370–378, April 1997.
F. Pellegrini and J. Roman. Sparse matrix ordering with scotch. InProceedings of HPCN’97, Vienna, LNCS 1225, pages 370–378, April 1997.
A. Pothen and C. Sun. A mapping algorithm for parallel sparse Cholesky factorization. SIAM J. Sci. Comput., 14(5):1253–1257, September 1993.
E. Rothberg. Performance of panel and block approaches to sparse Cholesky factorization on the iPSC/860 and Paragon multicomputers. SIAM J. Sci. Comput., 17(3):699–713, May 1996.
E. Rothberg and A. Gupta. An efficient block-oriented approach to parallel sparse Cholesky factorization. SIAM J. Sci. Comput., 15(6):1413–1439, November 1994.
E. Rothberg and R. Schreiber. Improved load distribution in parallel sparse Cholesky factorization. In Proceedings of Supercomputing’94, pages 783–792. IEEE, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hénon, P., Ramet, P., Roman, J. (1999). A Mapping and Scheduling Algorithm for Parallel Sparse Fan-In Numerical Factorization⋆. In: Amestoy, P., et al. Euro-Par’99 Parallel Processing. Euro-Par 1999. Lecture Notes in Computer Science, vol 1685. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48311-X_148
Download citation
DOI: https://doi.org/10.1007/3-540-48311-X_148
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66443-7
Online ISBN: 978-3-540-48311-3
eBook Packages: Springer Book Archive