A fully asynchronous multifrontal solver using distributed dynamic scheduling. (English) Zbl 0992.65018

Amestoy, Patrick R.; Duff, Iain S.; L’Excellent, Jean-Yves; Koster, Jacko

SIAM J. Matrix Anal. Appl. 23, No. 1, 15-41 (2001).

Summary: We analyze the main features and discuss the tuning of the algorithms for the direct solution of sparse linear systems on distributed memory computers developed in the context of a long term European research project. The algorithms use a multifrontal approach and are especially designed to cover a large class of problems. The problems can be symmetric positive definite, general symmetric, or unsymmetric matrices, both possibly rank deficient, and they can be provided by the user in several formats. The algorithms achieve high performance by exploiting parallelism coming from the sparsity in the problem and that available for dense matrices. The algorithms use a dynamic distributed task scheduling technique to accommodate numerical pivoting and to allow the migration of computational tasks to lightly loaded processors. Large computational tasks are divided into subtasks to enhance parallelism. Asynchronous communication is used throughout the solution process to efficiently overlap communication with computation.
We illustrate our design choices by experimental results obtained on an SGI Origin 2000 and an IBM SP2 for test matrices provided by industrial partners in the PARASOL project.

MSC:

65F05	Direct numerical methods for linear systems and matrix inversion
65F50	Computational methods for sparse matrices
65Y05	Parallel numerical computation
65Y20	Complexity and performance of numerical algorithms

Keywords:

sparse linear equations; Gaussian elimination; multifrontal methods; asynchronous parallelism; distributed memory computation; dynamic scheduling; algorithms; performance; pivoting

Software:

Algorithm 679; MUMPS; METIS; BLAS; SPOOLES; Scotch; PARASOL; LAPACK; ScaLAPACK