Cyclic reduction


Cyclic reduction is a numerical method 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 Toeplitz matrix, such problems often arise in implicit solutions for partial differential equations on a lattice. For example fast solvers for Poisson's equation 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 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] FFT

Transforming from the spatial domain and restating the PDE is called a spectral method, 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.