cyclic_reduction
cyclic_reduction,
an Octave 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 offdiagonal 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, GaussSeidel, 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 MIT license
Languages:
cyclic_reduction is available in
a C version and
a C++ version and
a Fortran90 version and
a MATLAB version and
an Octave version.
Related Data and Programs:
cyclic_reduction_test
test_matrix,
a MATLAB code which
defines test matrices, some of
which have known determinants, eigenvalues and eigenvectors,
inverses and so on.
Reference:

Gene Golub, Charles VanLoan,
Matrix Computations,
Third Edition,
Johns Hopkins, 1996,
ISBN: 080184513X,
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 95113, January 1965.
Source Code:

c83_cr_fa.m,
factors a C83 system using cyclic reduction;

c83_cr_sl.m,
solves a C83 system factored by c83_cr_fa;

c83_cr_sls.m,
solves multiple C83 systems factored by c83_cr_fa;

c83_indicator.m,
sets up a C83 indicator matrix.

c83_mxv.m,
multiplies a C83 matrix times a vector;

c8mat_print.m,
prints a C8MAT.

c8mat_print_some.m,
prints some of a C8MAT.

c8vec_indicator.m,
sets a C8VEC to the indicator vector.

c8vec_print.m,
prints a C8VEC.

c8vec_print_some.m,
prints some of a C8VEC.

r83_cr_fa.m,
factors a R83 system using cyclic reduction;

r83_cr_sl.m,
solves a R83 system factored by r83_cr_fa;

r83_cr_sls.m,
solves multiple R83 systems factored by r83_cr_fa;

r83_jac_sl.m,
solves a R83 system using GaussSeidel iteration;

r83_mxv.m,
multiplies a R83 matrix times a vector;

r83_print.m,
prints a R83 matrix;

r83_print_some.m,
prints some of a R83 matrix;

r8mat_print.m,
prints an R8MAT, with an optional title;

r8mat_print_some.m,
prints some of an R8MAT;

r8vec_indicator.m,
sets an R8VEC to the indicator vector;

r8vec_print.m,
prints an R8VEC;

r8vec_print_some.m,
prints some of an R8VEC;
Last revised on 28 September 2022.