Abstract
A multilevel algorithm is presented for direct, parallel factorization of the large sparse matrices that arise from finite element and spectral element discretization of elliptic partial differential equations. Incomplete nested dissection and domain decomposition are used to distribute the domain among the processors and to organize the matrix into sections in which pivoting is applied to stabilize the factorization of indefinite equation sets. The algorithm is highly parallel and memory efficient; the efficient use of sparsity in the matrix allows the solution of larger problems as the number of processors is increased, and minimizes computations as well as the number and volume of communications among the processors. The number of messages and the total volume of messages passed during factorization, which are used as measures of algorithm efficiency, are reduced significantly compared to other algorithms. Factorization times are low and speedups high for implementation on an Intel iPSC/860 hypercube computer. Furthermore, the timings for forward and back substitutions are more than an order-of-magnitude smaller than the matrix decomposition times.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A. V., Hopcroft, J. E., and Ullman, J. D. (1983).Data Structures and Algorithms, Addison-Wesley, Reading, Massachusetts.
Ashcraft, C., Eisenstat, S., and Liu, J. (1990). A fan-in algorithm for distributed sparse numerical factorization,SIAM J. Sci. Statist. Comput. 11, 593–599.
Benner, R. E., Montry, G. R., Weigand, C. G., and Duff, I. S. (1987). Concurrent multifrontal methods: shared memory, cache, and frontwidth issues,Int'l. J. of Supercomp. Appl. 1(3), 26–44.
Chan, T., and Saad, Y. (1986). Multigrid algorithms on the hypercube multiprocessor,IEEE Trans, on Computers C-35, 969–977.
Chu, E., and George, A. (1987). Gaussian elimination with partial pivoting and load balancing on a multiprocessor,Parallel Computing 5, 65–74.
Chu, E., George, A., and Liu, J. W. H. (1984). User's guide for SPARSPAK-A, Technical Report CS-84-36, Department of Computer Science, Waterloo University, Waterloo, Ontario.
Dayde, M. J., and Duff, I. S. (1991). Use of level 3 BLAS in LU factorization in a multiprocessing environment on three vector multiprocessors: the Alliant FX/80, the Cray-2, and the IBM 3090 VF,Int'l. J. Supercomp. Appl. 5(3), 92–110.
Duff, I. S. (1989). Direct solvers,Computer Physics Reports 11, 21–50.
Duff, I. S., and Johnsson, S. L. (1989). Node orderings and concurrency in structurally-symmetric sparse systems, Carey, G. F. (ed.), Wiley, New York,Parallel Super computing: Methods, Algorithms, and Applications, pp. 177–188.
Duff, I. S., and Reid, J. K. (1983). The multifrontal solution of indefinite sparse symmetric linear equations,ACM Trans. Math. Software 9(3), 302–325.
Duff, I. S., and Reid, J. K. (1984). The multifrontal solution of unsymmetric sets of linear equations,SIAM J. Sci. Statist. Comput. 5(3), 633–641.
George, A. (1973). Nested dissection of a regular finite element mesh,SIAM J. Numer. Anal. 10, 345–367.
George, A., and Liu, J. W. H. (1981).Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, Englewood Cliffs, New Jersey.
George, A., and Ng, E. (1988). On the complexity of sparse QR and LU factorization of finiteelement matrices,SIAM J. Sci. Statist. Comput. 9(5), 849–861.
George, A., and Rashwan, H. (1985). Auxiliary storage methods for solving finite element systems,SIAM J. Sci, Statist. Comput. 6(9), 882–910.
Heath, M. T., Ng, E., and Peyton, B. W. (1991). Parallel algorithms for sparse linear systems,SIAM Review 33(3), 420–460.
Hood, P. (1976). Frontal solution program for unsymmetric matrices,J. Num. Meth. Engng. 10, 379–399.
Hood, P. (1977). Note on frontal solution program for unsymmetric matrices,J. Num. Math. Engng. 11, 1055.
Intel (1990).iPSC/2 and iPSC/860 Programmer's Reference Manual, Intel Scientific Computers, Beaverton, Oregon.
Irons, B. M. (1970). A frontal solution program for finite element analysis,Int'l. J. Num. Meth. Engng. 2, 5–32.
Kuck (1992).CLASSPACK Basic Math Library, Kuck and Associates, Inc., Champaign, Illinois.
Lucas, R. F., Blank, T., and Tiemann, J. J. (1987). A parallel solution method for large sparse systems of equations,IEEE Trans. Computer-Aided Design CAD-6(6), 981–991.
Mu, M., and Rice, J. R. (1992). A grid-based subtree-subcube assignment strategy for solving partial differential equations on hypercubes,SIAM J. Sci. Stat. Comput. 13(3), 826–839.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mehrabi, M.R., Brown, R.A. An incomplete nested dissection algorithm for parallel direct solution of finite element discretizations of partial differential equations. J Sci Comput 8, 373–387 (1993). https://doi.org/10.1007/BF01061145
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01061145