Search

We examine the mechanics of the send and receive mechanism of MPI and in particular how we can implement message passing in a robust way so that our performance is not significantly affected by changes to the MPI system. This leads us to using the Isend/Irecv protocol which will entail sometimes significant algorithmic changes. We discuss this within the context of two different algorithms for sparse Gaussian elimination that we have parallelized. One is a multifrontal solver called MUMPS, the other is a supernodal solver called SuperLU. Both algorithms are difficult to parallelize on distributed memory machines. Our initial strategies were based on simple MPI point-to-point communication primitives. With such approaches, the parallel performance of both codes are very sensitive to the MPI implementation, the way MPI internal buffers are used in particular. We then modified our codes to use more sophisticated nonblocking versions of MPI communication. This significantly improved the performance robustness (independent of the MPI buffering mechanism) and scalability, but at the cost of increased code complexity.

AMD is a set of routines that implements the approximate minimum degree ordering algorithm to permute sparse matrices prior to numerical factorization. There are versions written in both C and Fortran 77. A MATLAB interface is included. Categories and Subject Descriptors: G.1.3 [Numerical Analysis]: Numerical Linear Algebra--Linear systems (direct and iterative methods); sparse structural, and very large systems (direct and iterative methods); G.4 [Mathematics of Computing]: Mathematical Software--Algorithm design and analysis; efficiency General Terms: Algorithms, Experimentation, Performance Additional Key Words and Phrases: Linear equations, minimum degree, ordering methods, sparse matrices

The need to solve large sparse linear systems of equations efficiently lies at the heart of many applications in computational science and engineering. For very large systems when using direct factorization methods of solution, it can be beneficial and sometimes necessary to use multiple processors, because of increased memory availability as well as reduced factorization time. We report on the development of a new parallel code that is designed to solve linear systems with a highly unsymmetric sparsity structure using a modest number of processors (typically up to about 16). The problem is first subdivided into a number of loosely connected subproblems and a variant of sparse Gaussian elimination is then applied to each of the subproblems in parallel. An interface problem in the variables on the boundaries of the subproblems must also be factorized. We discuss how our software is designed to achieve the goals of portability, ease of use, efficiency, and flexibility, and illustrate its performance on an SGI Origin 2000, a Cray T3E, and a 2-processor Compaq DS20, using problems arising from real applications. Categories and Subject Descriptors: G.1.0 [Numerical Analysis]: General--Numerical algorithms; G.1.3 [Numerical Analysis]: Numerical Linear Algebra--Sparse, structured, and very large systems (direct and iterative methods) General Terms: Algorithms, Performance Additional Key Words and Phrases: Sparse matrices, highly unsymmetric linear systems, Gaussian elimination, parallel processing

We introduce a new code for the direct solution of sparse symmetric linear equations that solves indefinite systems with 2 x 2 pivoting for stability. This code, called MA57, is in HSL 2002 and supersedes the well used HSL code MA27. We describe some of the implementation details and emphasize the novel features of MA57. These include restart facilities, matrix modification, partial solution for matrix factors, solution of multiple right-hand sides, and iterative refinement and error analysis. The code is written in Fortran 77, but there are additional facilities within a Fortran 90 implementation that include the ability to identify and change pivots. Several of these facilities have been developed particularly to support optimization applications, and we illustrate the performance of the code on problems arising therefrom. Categories and Subject Descriptors: G.1.3 [Numerical Analysis]: Numerical Linear Algebra--Sparse, structured, and very large systems (direct and iterative methods); G.4 [Mathematical Software]: Algorithm design and analysis; user interfaces General Terms: Algorithms, performance, reliability Additional Key Words and Phrases: Augmented systems, direct sparse factorization, multifrontal method, numerical optimization, sparse definite and indefinite systems

The Basic Linear Algebra Subprograms for sparse matrices (Sparse BLAS) as defined by the BLAS Technical Forum are a set of routines providing basic operations for sparse matrices and vectors. A principal goal of the Sparse BLAS standard is to aid in the development of iterative solvers for large sparse linear systems by specifying on the one hand interfaces for a high-level description of vector and matrix operations for the algorithm developer and on the other hand leaving enough freedom for vendors to provide the most efficient implementation of the underlying algorithms for their specific architectures. The Sparse BLAS standard defines interfaces and bindings for the three target languages: C, Fortran 77 and Fortran 95. We describe here our Fortran 95 implementation intended as a reference model for the Sparse BLAS. We identify the underlying complex issues of the representation and the handling of sparse matrices and give suggestions to other implementors of how to address them. Categories and Subject Descriptors: G. 1.3 [Numerical Analysis]: Numerical Linear Algebra General Terms: Algorithms, Design, Standardization Additional Key Words and Phrases: BLAS, iterative linear solvers, programming standard, Sparse BLAS, sparse data structures, unstructured sparse matrices

We discuss the interface design for the Sparse Basic Linear Algebra Subprograms (BLAS), the kernels in the recent standard from the BLAS Technical Forum that are concerned with unstructured sparse matrices. The motivation for such a standard is to encourage portable programming while allowing for library-specific optimizations. In particular, we show how this interface can shield one from concern over the specific storage scheme for the sparse matrix. This design makes it easy to add further functionality to the sparse BLAS in the future. We illustrate the use of the Sparse BLAS with examples in the three supported programming languages, Fortran 95, Fortran 77, and C. Categories and Subject Descriptors: G.1.3 [Numerical Analysis]: Numerical Linear Algebra--sprase, structured, and very large systems (direct and iterative methods); G.4 [Mathematical Software]: user interfaces General Terms: Design, Standardization Additional Key Words and Phrases: Algorithms, computational kernels, software, sparse BLAS, sparse iterative methods, sparse matrices

This paper provides a comprehensive study and comparison of two state-of-the-art direct solvers for large sparse sets of linear equations on large-scale distributed-memory computers. One is a multifrontal solver called MUMPS, the other is a supernodal solver called SuperLU. We describe the main algorithmic features of the two solvers and compare their performance characteristics with respect to uniprocessor speed, interprocessor communication, and memory requirements. For both solvers, preorderings for numerical stability and sparsity play an important role in achieving high parallel efficiency. We analyse the results with various ordering algorithms. Our performance analysis is based on data obtained from runs on a 512-processor Cray T3E using a set of matrices from real applications. We also use regular 3D grid problems to study the scalability of the two solvers. Categories and Subject Descriptors: G.1.3 [Numerical Analysis]: Numerical Linear Algebra--Sparse, structured, and very large systems (direct and iterative methods); G.4 [Mathematics of Computing]: Mathematical Software--Parallel and vector implementations General Terms: Algorithms, Performance Additional Key Words and Phrases: Sparse direct solvers, parallelism, distributed-memory computers, multifrontal and supernodal factorizations

This article proposes a set of Level 3 Basic Linear Algebra Subprograms and associated kernels for sparse matrices. A major goal is to design and develop a common framework to […]