cyclic_reduction, a FORTRAN90 code 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:
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.
The computer code and data files described and made available on this web page are distributed under the MIT license
cyclic_reduction is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version.
dlap, a FORTRAN90 code which carries out the iterative solution of sparse linear systems.
lapack_examples, a FORTRAN77 program which demonstrates the use of the LAPACK linear algebra code.
linpack, a FORTRAN90 code which factors and solves systems of linear equations in a variety of formats and arithmetic types.
mgmres, a FORTRAN90 code which applies the restarted GMRES algorithm to solve a sparse linear system.
sparsekit, a FORTRAN90 code which carries out operations on sparse matrices, including conversion between various formats.
super_lu, a C code which implements some very fast direct solvers for systems of sparse linear equations.
test_matrix, a FORTRAN90 code which defines test matrices, some of which have known determinants, eigenvalues and eigenvectors, inverses and so on.