Parallel frontal solvers for large sparse linear systems

ABSTRACT

Many applications in science and engineering give rise to large sparse linear systems of equations that need to be solved as efficiently as possible. As the size of the problems of interest increases, it can become necessary to consider exploiting multiprocessors to solve these systems. We report on the design and development of parallel frontal solvers for the numerical solution of large sparse linear systems. Three codes have been developed for the mathematical software library HSL (www.cse.clrc.ac.uk/Activity/HSL). The first is for unsymmetric finite-element problems; the second is for symmetric positive definite finite-element problems; and the third is for highly unsymmetric linear systems such as those that arise in chemical process engineering. In each case, the problem is subdivided into a small number of loosely connected subproblems and a frontal method is then applied to each of the subproblems in parallel. We discuss how our software is designed to achieve the goals of portability, ease of use, efficiency, and flexibility, and illustrate the performance using problems arising from real applications.

REFERENCES

• 1: Benner, R., Montry, G., and Weigand, G. 1987. Concurrent multifrontal methods: shared memory, cache, and frontwidth issues. Int. J. Supercomput. Applics. 1, 26--44.
• 2: Bomhof, C. and van der Vorst, H. 2000. A parallel linear system solver for circuit simulation problems. Numerical Linear Algebra with Applications 7, 649--665.
• 3: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 4: Duff, I. 1984. Design features of a frontal code for solving sparse unsymmetric linear systems out-of-core. SIAM J. Sci. Stat. Comput. 5, 270--280.
• 5: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 6: I. S. Duff , J. K. Reid, The design of MA48: a code for the direct solution of sparse unsymmetric linear systems of equations, ACM Transactions on Mathematical Software (TOMS), v.22 n.2, p.187-226, June 1996 [doi>10.1145/229473.229476]
• 7: Duff, I. and Scott, J. 1994. The use of multiple fronts in Gaussian elimination. Tech. Rep. RAL-94-040, Rutherford Appleton Laboratory.
• 8: I. S. Duff , J. A. Scott, The design of a new frontal code for solving sparse, unsymmetric systems, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.30-45, March 1996 [doi>10.1145/225545.225550]
• 9: Duff, I. and Scott, J. 1998. MA62---a frontal code for sparse positive-definite symmetric systems from finite-element applications. In Innovative Computational Methods for Structural Mechanics, M. Papadrakakis and B. Topping, Eds. Saxe-Coburg Publications, Edinburgh, 1--25.
• 10: Duff, I. and Scott, J. 2002. A parallel direct solver for large sparse highly unsymmetric linear systems. Tech. Rep. RAL-TR-2002-033, Rutherford Appleton Laboratory, Didcot, Oxfordshire.
• 11: Golub, G., Sameh, A., and Sarin, V. 2001. A parallel balanced scheme for banded linear systems. Numerical Linear Algebra with Applications 8, 297--316.
• 12: Hendrickson, B. and Leland, R. 1995. The Chaco user's guide: Version 2.0. Tech. Rep. SAND94-2692, Sandia National Laboratories, Albuquerque, NM.
• 13: Hood, P. 1976. Frontal solution program for unsymmetric matrices. Int. J. Num. Meth. Eng. 10, 379--400.
• 14: Hu, Y., Maguire, K., and Blake, R. 2000. A multilevel unsymmetric matrix ordering for parallel process simulation. Computers in Chemical Engineering 23, 1631--1647.
• 15: Irons, B. 1970. A frontal solution program for finite-element analysis. Int. J. Num. Meth. Eng. 2, 5--32.
• 16: Mallya, J., Zitney, S., Choudhary, S., and Stadtherr, M. 1997. A parallel block frontal solver for large scale process simulation: reordering effects. Computers in Chemical Engineering 21, S439--S444.
• 17: MPI. 1994. A message-passing interface standard. Int. J. Supercomp. Applic. 8. Special edition on MPI.
• 18: Reid, J. and Scott, J. 1999. Ordering symmetric sparse matrices for small profile and wavefront. Int. J. Num. Meth. Eng 45, 1737--1755.
• 19: Scott, J. 1996. Element resequencing for use with a multiple front algorithm. Int. J. Num. Meth. Eng. 39, 3999--4020.
• 20: Scott, J. 1999a. A new row ordering strategy for frontal solvers. Numerical Linear Algebra with Applications 6, 1--23.
• 21: Scott, J. 1999b. On ordering elements for a frontal solver. Communications in Numerical Methods in Engineering 15, 309--323.
• 22: Scott, J. 2000. Row ordering for frontal solvers in chemical process engineering. Computers in Chemical Engineering 24, 1865--1880.
• 23: Scott, J. 2001a. The design of a portable parallel frontal solver for chemical process engineering problems. Computers in Chemical Engineering 25, 1699--1709.
• 24: Scott, J. 2001b. A parallel solver for finite element applications. Int. J. Num. Meth. Eng. 50, 1131--1141.
• 25: Scott, J. 2001c. Two-stage ordering for unsymmetric parallel row-by-row frontal solvers. Computers in Chemical Engineering 25, 323--332.
• 26: Sloan, S. 1989. A FORTRAN program for profile and wavefront reduction. Int. J. Num. Meth. Eng. 28, 2651--2679.
• 27: Zang, W. and Liu, E. 1991. A parallel frontal solver on the Alliant. Computers and Structures 38, 202--215.
• 28: Zone, O. and Keunings, R. 1991. Direct solution of two-dimensional finite element equations on distributed memory parallel computers. In High Performance Computing, M. Durand and F. E. Dabaghi, Eds. Elsevier Science Publications.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

General Terms:
Algorithms, Performance

Keywords:
Sparse matrices, finite-elements, frontal method, linear systems, parallel processing