Cyclic reduction is a
numerical method
In numerical analysis, a numerical method is a mathematical tool designed to solve numerical problems. The implementation of a numerical method with an appropriate convergence check in a programming language is called a numerical algorithm.
Mathem ...
for solving large linear systems by repeatedly splitting the problem. Each step eliminates even or odd rows and columns of a matrix and remains in a similar form. The elimination step is relatively expensive but splitting the problem allows parallel computation.
Applicability
The method only applies to matrices that can be represented as a (block)
Toeplitz matrix In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix:
:\qquad\begin
a & b ...
, such problems often arise in implicit solutions for partial differential equations on a lattice. For example fast solvers for
Poisson's equation
Poisson's equation is an elliptic partial differential equation of broad utility in theoretical physics. For example, the solution to Poisson's equation is the potential field caused by a given electric charge or mass density distribution; with th ...
express the problem as solving a tridiagonal matrix, discretising the solution on a regular grid.
Accuracy
Systems which have good numerical stability initially tend to get better with each step to a point where a good approximate solution can be given, but because the special matrix form must be preserved pivoting cannot be performed to improve numerical accuracy.
Comparison to multigrid
The method is not iterative, it seeks an exact solution to the linear problem consistent with the given boundary values, contrast that with the similar but computationally cheaper
multigrid method In numerical analysis, a multigrid method (MG method) is an algorithm for solving differential equations using a hierarchy of discretizations. They are an example of a class of techniques called multiresolution methods, very useful in problems exhi ...
which propagates error-correction estimates down and allows for different relaxation parameters at different scales, the iterative aspect allowing better incorporation of non-linear features.
Combination with
fast Fourier transform
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in th ...
FFT
Transforming from the spatial domain and restating the PDE is called a
spectral method
Spectral methods are a class of techniques used in applied mathematics and scientific computing to numerically solve certain differential equations. The idea is to write the solution of the differential equation as a sum of certain " basis functio ...
, Fourier analysis and cyclic reduction are combined in the FACR algorithm which is explained in Numerical Recipes – see 19.4 Fourier and Cyclic Reduction Methods for Boundary Value Problems.
[W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flanner]
Numerical Recipes In 'C': The Art Of Scientific Computing
p 885 Cambridge University Press 1988–1992
Notes and references
Numerical differential equations
{{Mathanalysis-stub