A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling
Patrick Amestoy, Iain Duff, Jean-Yves L’Excellent et al. · SIAM Journal on Matrix Analysis and Applications · 2001
In this paper, 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.
Cited by 2,287 works. doi:10.1137/s0895479899358194
Authors
References
- LAPACK Users' Guide
- A set of level 3 basic linear algebra subprograms
- Direct Methods for Sparse Matrices
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems
- Direct Methods for Sparse Matrices.
- An Approximate Minimum Degree Ordering Algorithm
- Rank revealing QR factorizations
- Multifrontal parallel distributed symmetric and unsymmetric solvers
- Highly scalable parallel algorithms for sparse matrix factorization