Memory Management Issues in Sparse Multifrontal Methods On Multiprocessors

Abstract

This article addresses the problems of memory man agement in a parallel sparse matrix factorization based on a multifrontal approach. We describe how we have adapted and modified the ideas of Duff and Reid used in a sequential symmetric multifrontal method to de sign an efficient memory management scheme for parallel sparse matrix factorization. With our solution, using the minimum size of the working area to run the multifrontal method on a multiprocessor, we can ex ploit only a part of the parallelism of the method. If we slightly increase the size of the working space, then most of the potential parallelism of the method can be exploited. We have designed a flexible memory man agement scheme which adapts well to a variation in the size of the working area and/or the number of pro cessors. General parallel applications can always be represented in terms of a computational graph, which is effectively the underlying structure of a parallel mul tifrontal method. Therefore, we believe that the tech niques presented here are useful when designing an efficient memory management scheme for a wider range of parallel applications.

Get full access to this article

View all access options for this article.

References

Amestoy, P.R. 1991. Factorization of large sparse matrices based on a multifrontal approach in a multiprocessor environment. Ph.D. thesis TH/ PA/91/2, CERFACS, Toulouse, France.

Curtis, A.R. , and Reid, J.K. 1972. On the automatic scaling of matrices for gaussian elimination . J. Inst. Maths. Applics. 10: 118-124.

Duff, I.S. 1989. Multiprocessing a sparse matrix code on the Alliant FX/8 . J. Comput. Appl. Math. 27: 229-239.

Duff, I.S. , Grimes, R.G. , and Lewis, J.G. 1989. Sparse matrix test problems. ACM Trans. Math. Softw. 15:1-14.

Duff, I.S. , Grimes, R.G. , and Lewis, J.G. 1992. Users' guide for the Harwell-Boeing sparse matrix collection. Technical Report TR/PA/92/86. CERFACS, Toulouse, France.

Duff, I.S. , and Reid, J.K. 1983. The multifrontal solution of indefinite sparse symmetric linear systems. ACM Tram. Math. Softw. 9:302-325.

Duff, I.S. , and Reid, J.K. 1984. The multifrontal solution of unsymmetric sets of linear systems. SIAM J. Matrix Anal. and Applics. 5:633-641.

Liu, J.W.H. 1986. On the storage requirement in the out-of-core multifrontal method for sparse factorization. ACM Trans. Math. Softw. 12:127-148.

Liu, J.W.H. 1987. A note on sparse factorization in a paging environment . SIAM J. Sci. Stat. Comput. 8:1085-1088.

10.

Liu, J.W.H. 1989. The multifrontal method and paging in sparse Cholesky factorization. ACM Trans. Math. Softw. 15:310-325.

11.

Liu, J.W.H. 1990. The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Appl. 11:134-172.

12.

Liu, J.W.H. 1992. The multifrontal method for sparse matrix solution: theory and practice. SIAM Rev. 34:82-109.

13.

Reid, J.K. 1984. TREE-SOLVE, a Fortran package for solving large sets of linear finite elements equations. Technical Report CSS 155. AERE Harwell, Oxfordshire , UK.

14.

Reingold, E.M. , and Hansen, W.J. 1986. Data structures in Pascal. Boston: Little, Brown.

15.

Yang, C.W. 1992. A parallel multifrontal method for sparse symmetric definite systems on the CRAY Y-MP. In Proceedings of the Fifth SIAM Conference on Parallel Processing for Scientific Computing . Philadelphia: SIAM, pp. 47-51.