Search

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 […]

1. INTRODUCTION In a previous article [Duff and Scott 1996], we discussed the design and performance of a general frontal code, MA42, for solving sparse unsymmetric systems of equations. It […], We describe the design, implementation, and performance of a frontal code for the solution of large sparse symmetric systems of linear finite-element equations. The code is intended primarily for positive-definite systems, since numerical pivoting is not performed. The resulting software package, MA62, will be included in the Harwell Subroutine Library. We illustrate the performance of our new code on a range of problems arising from real engineering and industrial applications. The performance of the code is compared with that of the Harwell Subroutine Library general frontal solver MA42 and with other positive-definite codes from the Harwell Subroutine Library. 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: Finite-element equations, Gaussian elimination, Level 3 BLAS, sparse symmetric linear equations, symmetric frontal method

1. INTRODUCTION The Level 3 BLAS are a set of computational kernels targeted at matrix-matrix operations with the aim of providing efficient and portable implementations of algorithms on high-performance computers. […], We describe a version of the Level 3 BLAS which is designed to be efficient on RISC processors. This is an extension of previous studies by the authors and colleagues on a similar approach for efficient serial and parallel implementations on virtual-memory and shared-memory multiprocessors. All our codes are written in Fortran and use loop-unrolling, blocking, and copying to improve the performance. A blocking technique is used to express the BLAS in terms of operations involving triangular blocks and calls to the matrix-matrix multiplication kernel (GEMM). No manufacturer-supplied or assembler code is used. This blocked implementation uses the same blocking ideas as in our implementation for vector machines except that the ordering of loops is designed for efficient reuse of data held in cache and not necessarily for parallelization. All the codes are specifically tuned for RISC processors. The software also includes a tuned version of GEMM. A parameter which controls the blocking allows efficient exploitation of the memory hierarchy on the various target computers. We present results on a range of RISC-based workstations and multiprocessors: CRAY T3D, DEC 8400 5/300, HP 715/64, IBM SP2, MEIKO CS2-HA, SGI Power Challenge 10000, and SUN UltraSPARC-1 model 140. This implementation of the Level 3 BLAS is available on anonymous FTP, and we welcome input from users to improve and extend our BLAS implementation. Categories and Subject Descriptors: G.4 [Mathematics of Computing]: Mathematical Software; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems--Computations on matrices; G.1.0 [Numerical Analysis]: General Numerical algorithms; G.1.3 [Numerical Analysis]: Numerical Linear Algebra--Linear systems (direct and iterative methods) General Terms: Algorithms, Measurement, Performance Additional Key Words and Phrases: Blocking, Level 3 BLAS, loop-unrolling, matrix-matrix kernels, RISC processors

We discuss the organization of frontal matrices in multifrontal methods for the solution of large sparse sets of unsymmetric linear equations. In the multifrontal method, work on a frontal matrix […]