wathen_matrix


wathen_matrix, a C code which compares storage schemes (full, banded, sparse triplet, sparse) and solution strategies (A\x, Linpack, conjugate gradient (CG)) for linear systems involving the Wathen matrix, which can arise when solving a problem using the finite element method (FEM).

The Wathen matrix is a typical example of a matrix that arises during finite element computations. The parameters NX and NY specify how many elements are to be set up in the X and Y directions. The number of variables N is then

        N = 3 NX NY + 2 NX + 2 NY + 1
      
and the full linear system will require N * N storage for the matrix.

However, the matrix is sparse, and a banded or sparse storage scheme can be used to save storage. However, even if storage is saved, a revised program may eat up too much time because MATLAB's sparse storage scheme is not efficiently used by inserting nonzero elements one at a time. Moreover, if banded storage is employed, the user must provide a suitable fast solver. Simply "translating" a banded solver from another language will probably not provide an efficient routine.

This library looks at how the complexity of the problem grows with increasing NX and NY; how the computing time increases; how the various full, banded and sparse approaches perform.

Licensing:

The information on this web page is distributed under the MIT license.

Languages:

wathen_matrix is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

wathen_matrix_test

cg, a C code 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.

levenshtein_matrix, a C code which returns the Levenshtein distance matrix defined by two strings.

linpack_d, a C code which factors and solves linear systems using double precision real arithmetic, by Jack Dongarra, Jim Bunch, Cleve Moler, Pete Stewart.

sparse_display, a C code which can read information defining a matrix of numbers and display the sparsity pattern or location of the nonzero elements using gnuplot. This operation is already available in the built-in MATLAB "spy" command.

test_matrix, a C code which defines test matrices for which some of the determinant, eigenvalues, inverse, null vectors, P*L*U factorization or linear system solution are already known, including the Vandermonde and Wathen matrix.

Reference:

  1. Nicholas Higham,
    Algorithm 694: A Collection of Test Matrices in MATLAB,
    ACM Transactions on Mathematical Software,
    Volume 17, Number 3, September 1991, pages 289-305.
  2. Andrew Wathen,
    Realistic eigenvalue bounds for the Galerkin mass matrix,
    IMA Journal of Numerical Analysis,
    Volume 7, Number 4, October 1987, pages 449-457.

Source Code:


Last revised on 22 March 2022.