CYCLIC_REDUCTION
A Direct Solution Method for Tridiagonal Linear Systems.

CYCLIC_REDUCTION is a FORTRAN90 library which applies the cyclic reduction method to solve a tridiagonal system of linear equations A*x=b.

The matrix is assumed to be diagonally dominant - that is, for every row, we require that the magnitude of the diagonal entry be at least as great as the sum of the magnitudes of the two off-diagonal elements. This is (just barely) true for the "-1, 2, -1" matrix, for instance.

Other methods for solving tridiagonal linear systems include:

• Gauss elimination with pivoting;
• the Thomas algorithm, (Gauss elimination without pivoting);
• the Jacobi, Gauss-Seidel, and SOR iterative methods;

Cyclic reduction is a form of Gauss elimination. It proceeds by first eliminating half of the variables simultaneously, then half of the remainder, and so on. This amounts to more work, but the work in each elimination step can be done in parallel. Thus, unlike the Gauss and Thomas algorithms, cyclic reduction offers a procedure for the direct solution of a tridiagonal linear system that can take advantage of parallelism.

Cyclic reduction can also be adapted to the block tridiagonal linear systems that arise when Poisson's equation is discretized over a 2D region.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

CYCLIC_REDUCTION is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

CSPARSE, a C library which carries out the direct solution of sparse linear systems.

DLAP, a FORTRAN90 library which carries out the iterative solution of sparse linear systems.

LAPACK_EXAMPLES, a FORTRAN77 program which demonstrates the use of the LAPACK linear algebra library.

LINPACK, a FORTRAN90 library which factors and solves systems of linear equations in a variety of formats and arithmetic types.

LINPLUS, a FORTRAN90 library which carries out simple manipulations of matrices in a variety of formats.

MGMRES, a FORTRAN90 library which applies the restarted GMRES algorithm to solve a sparse linear system.

SPARSEKIT, a FORTRAN90 library which carries out operations on sparse matrices, including conversion between various formats.

SUPER_LU, a C library which implements some very fast direct solvers for systems of sparse linear equations.

TEST_MAT, a FORTRAN90 library which defines test matrices, some of which have known determinants, eigenvalues and eigenvectors, inverses and so on.

Reference:

1. Gene Golub, Charles VanLoan,
   Matrix Computations,
   Third Edition,
   Johns Hopkins, 1996,
   ISBN: 0-8018-4513-X,
   LC: QA188.G65.
2. 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.

Source Code:

• cyclic_reduction.f90, the source code.

Examples and Tests:

• cyclic_reduction_test.f90, a sample calling program.
• cyclic_reduction_test.txt, the output file.

List of Routines:

• C83_CR_FA decomposes a C83 matrix using cyclic reduction.
• C83_CR_SL solves a linear system factored by C83_CR_FA.
• C83_CR_SLS solves several linear systems factored by C83_CR_FA.
• C83_INDICATOR sets up a C83 indicator matrix.
• C83_MXV multiplies a C83 matrix times a C8VEC.
• C83_PRINT prints a C83 matrix.
• C83_PRINT_SOME prints some of a C83 matrix.
• C8MAT_PRINT prints a C8MAT.
• C8MAT_PRINT_SOME prints some of a C8MAT.
• C8VEC_INDICATOR sets a C8VEC to an "indicator" vector.
• C8VEC_PRINT prints a C8VEC, with an optional title.
• C8VEC_PRINT_SOME prints some of a C8VEC.
• R83_CR_FA decomposes an R83 matrix using cyclic reduction.
• R83_CR_SL solves a linear systems factored by R83_CR_FA.
• R83_CR_SLS solves several linear systems factored by R83_CR_FA.
• R83_PRINT prints an R83 matrix.
• R83_PRINT_SOME prints some of an R83 matrix.
• R8MAT_PRINT prints an R8MAT.
• R8MAT_PRINT_SOME prints some of an R8MAT.
• R8VEC_INDICATOR sets an R8VEC to the indicator vector.
• R83_MXV multiplies an R83 matrix times an R8VEC.
• R8VEC_PRINT prints an R8VEC, with an optional title.
• R8VEC_PRINT_SOME prints "some" of an R8VEC.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the FORTRAN90 source codes.