linplus
linplus,
a FORTRAN77 code which
carries out operations such as matrix-vector products,
matrix factorization, linear solvers including Gauss-elimination,
Jacobi iteration, Gauss-Seidel iteration, Conjugate Gradient (CG),
for matrices in a
variety of formats, including banded, border-banded, circulant, lower
triangular, pentadiagonal, sparse, symmetric, toeplitz, tridiagonal,
upper triangular and vandermonde formats.
The routines are primarily organized by the arithmetic type, and the
storage format of the matrix they operate on. Some of these formats
were defined by LINPACK, while others are new; I just made them up when
I had to solve problems involving such matrices. The formats include:
-
C83 - Complex double precision tridiagonal;
-
C8CI - Complex double precision circulant;
-
C8GE - Complex double precision general;
-
C8TO - Complex double precision Toeplitz;
-
R83 - Real double precision tridiagonal;
-
R83P - Real double precision tridiagonal periodic;
-
R83S - Real double precision tridiagonal scalar;
-
R83V - Real double precision tridiagonal, 3 vector storage;
-
R85 - Real double precision pentadiagonal;
-
R8BB - Real double precision border-banded;
-
R8BLT - Real double precision banded lower triangular matrix;
-
R8BTO - Real double precision block Toeplitz;
-
R8BUT - Real double precision banded upper triangular matrix;
-
R8CB - Real double precision compact band;
-
R8CBB - Real double precision compact border-banded;
-
R8CC - Real double precision compressed column sparse
= Harwell Boeing Unsymmetric Assembled format
= MATLAB sparse format;
-
R8CI - Real double precision circulant;
-
R8GB - Real double precision general band,
used by LINPACK and LAPACK;
-
R8GD - Real double precision general diagonal;
-
R8GE - Real double precision general, used by LINPACK and LAPACK;
-
R8LT - Real double precision lower triangular;
-
R8LTT - Real double precision lower triangular Toeplitz,
(moved to a separate library);
-
R8NCF - Real double precision Nonsymmetric Coordinate Format,
one of the formats used by NSPCG;
-
R8PBL - Real double precision positive-definite symmetric band
matrix, store diagonal and lower triangle;
-
R8PBU - Real double precision positive-definite symmetric band
matrix, store diagonal and upper triangle;
-
R8PO - Real double precision positive-definite symmetric,
used by LINPACK and LAPACK;
-
R8PP - Real double precision positive-definite symmetric Packed,
used by LINPACK and LAPACK;
-
R8RI - Real double precision Row-Indexed matrix,
used by Numerical Recipes;
-
R8S3 - Real double precision sparse matrix stored by row,
column, value (used by SLAP/DLAP, symmetric or nonsymmetric);
-
R8SD - Real double precision symmetric diagonal;
-
R8SM - Real double precision Sherman Morrison system A - u * v';
-
R8SP - Real double precision sparse matrix stored by row,
column, value, used by CSPARSE ("sparse triplet"),
SLAP/DLAP (nonsymmetric SLAP triad format), MATLAB,
and SPARSEKIT ("COO" format);
-
R8SR - Real double precision sparse matrix stored by diagonal
and rows;
-
R8SS - Real double precision symmetric skyline;
-
R8STO - Real double precision symmetric Toeplitz;
-
R8TO - Real double precision Toeplitz;
-
R8UT - Real double precision upper triangular;
-
R8UTP - Real double precision upper triangular, packed
(only nonzeros are stored);
-
R8VEC - Real double precision vector, which in some cases
is used to store a matrix;
-
R8VM - Real double precision Vandermonde;
Licensing:
The computer code and data files described and made available on this web page
are distributed under
the GNU LGPL license.
Languages:
linplus is available in
a C version and
a C++ version and
a FORTRAN77 version and
a FORTRAN90 version and
a MATLAB version and
a Python version.
Related Data and Programs:
linplus_test
CG,
a FORTRAN77 library which
implements a simple version of the conjugate gradient (CG) method
for solving a system of linear equations of the form A*x=b,
suitable for situations in which the matrix A is positive definite
(only real, positive eigenvalues) and symmetric.
CG_RC,
a FORTRAN77 library which
implements the conjugate gradient (CG) method for solving
a positive definite sparse linear system A*x=b, using reverse communication.
CR,
a data directory which
contains examples of the Compressed Row (CR)
sparse matrix file format;
HB_TO_ST,
a FORTRAN77 program which
converts a sparse matrix from Harwell-Boeing to sparse triplet format.
HBSMC,
a dataset directory which
contains the Harwell-Boeing Sparse Matrix Collection
of large sparse matrices.
LAPACK,
a FORTRAN77 library which
contains modern linear algebra routines.
LINPACK,
a FORTRAN77 library which
factors and solves systems of linear equations in a variety of
formats and arithmetic types.
LINPACK_BENCH,
a FORTRAN77 program which
measures the time taken by LINPACK to solve a
particular linear system.
MGMRES,
a FORTRAN77 library which
applies the restarted GMRES algorithm to solve a sparse linear system.
SPARSEKIT,
a FORTRAN77 library which
carries out operations on sparse matrices, including conversion between
various formats.
TEMPLATES,
a FORTRAN77 library which
implements various iterative methods for solving a linear system.
TEST_MAT,
a FORTRAN77 library which
defines test matrices, some of
which have known determinants, eigenvalues and eigenvectors,
inverses and so on.
TOEPLITZ,
a FORTRAN77 library
solves a variety of Toeplitz and circulant linear systems.
TOEPLITZ_CHOLESKY,
a FORTRAN77 library which
computes the Cholesky factorization of a nonnegative definite symmetric
Toeplitz matrix.
WATHEN,
a FORTRAN77 library which
compares storage schemes (full, banded, sparse triplet) and
solution strategies (Linpack full, Linpack banded,
conjugate gradient (CG)) for linear systems involving the Wathen matrix,
which can arise when solving a problem using the
finite element method (FEM).
Reference:
-
Edward Anderson, Zhaojun Bai, Christian Bischof, Susan Blackford,
James Demmel, Jack Dongarra, Jeremy Du Croz, Anne Greenbaum,
Sven Hammarling, Alan McKenney, Danny Sorensen,
LAPACK User's Guide,
Third Edition,
SIAM, 1999,
ISBN: 0898714478,
LC: QA76.73.F25L36
-
Frank Beckman,
The Solution of Linear Equations by the Conjugate Gradient Method,
in Mathematical Methods for Digital Computers,
edited by John Ralston, Herbert Wilf,
Wiley, 1967,
ISBN: 0471706892.
-
Paul Bratley, Bennett Fox, Linus Schrage,
A Guide to Simulation,
Second Edition,
Springer, 1987,
ISBN: 0387964673.
-
Ward Cheney, David Kincaid,
Numerical Mathematics and Computing,
Brooks-Cole Publishing, 2004,
ISBN: 0534201121.
-
Philip Davis,
Circulant Matrices,
Second Edition,
Chelsea, 1994,
ISBN: 0828403384,
LC: QA188.D37.
-
Jack Dongarra, Jim Bunch, Cleve Moler, Pete Stewart,
LINPACK User's Guide,
SIAM, 1979,
ISBN13: 978-0-898711-72-1,
LC: QA214.L56.
-
Iain Duff, Roger Grimes, John Lewis,
User's Guide for the Harwell-Boeing Sparse Matrix Collection,
October 1992.
-
Bennett Fox,
Algorithm 647:
Implementation and Relative Efficiency of Quasirandom
Sequence Generators,
ACM Transactions on Mathematical Software,
Volume 12, Number 4, December 1986, pages 362-376.
-
Gene Golub, Charles VanLoan,
Matrix Computations,
Third Edition,
Johns Hopkins, 1996,
ISBN: 0-8018-4513-X,
LC: QA188.G65.
-
Roger Hockney,
A fast direct solution of Poisson's equation using Fourier Analysis,
Journal of the ACM,
Volume 12, Number 1, pages 95-113, January 1965.
-
David Kahaner, Cleve Moler, Steven Nash,
Numerical Methods and Software,
Prentice Hall, 1989,
ISBN: 0-13-627258-4,
LC: TA345.K34.
-
Charles Lawson, Richard Hanson, David Kincaid, Fred Krogh,
Algorithm 539: Basic Linear Algebra Subprograms for Fortran Usage,
ACM Transactions on Mathematical Software,
Volume 5, Number 3, September 1979, pages 308-323.
-
Albert Nijenhuis, Herbert Wilf,
Combinatorial Algorithms for Computers and Calculators,
Second Edition,
Academic Press, 1978,
ISBN: 0-12-519260-6,
LC: QA164.N54.
-
William Press, Brian Flannery, Saul Teukolsky, William Vetterling,
Numerical Recipes in FORTRAN: The Art of Scientific Computing,
Third Edition,
Cambridge University Press, 2007,
ISBN13: 978-0-521-88068-8,
LC: QA297.N866.
Source Code:
Last revised on 20 October 2023.