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 (block) 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. Moreover, to a point where a good approximate solution can be given,^[1] 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^[2] which is explained in Numerical Recipes – see 19.4 Fourier and Cyclic Reduction Methods for Boundary Value Problems.^[3]

Notes and references

^ Walter Gander and Gene H. Golub, Cyclic Reduction – History and Applications, Proceedings of the Workshop on Scientific Computing 10–12 March 1997
^ P. N. Swarztrauber, The method of cyclic reduction, Fourier analysis and the FACR algorithm for the discrete solution of Poisson's equation on a rectangle, Society for Industrial and Applied Mathematics' SIAM Review 19 pp. 490–501 1977
^ W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery Numerical Recipes In 'C': The Art Of Scientific Computing Archived 2013-08-06 at the Wayback Machine p 885 ISBN 0-521-43108-5 Cambridge University Press 1988–1992

This mathematical analysis–related article is a stub. You can help Wikipedia by expanding it.

[1] Walter Gander and Gene H. Golub, Cyclic Reduction – History and Applications, Proceedings of the Workshop on Scientific Computing 10–12 March 1997

[2] P. N. Swarztrauber, The method of cyclic reduction, Fourier analysis and the FACR algorithm for the discrete solution of Poisson's equation on a rectangle, Society for Industrial and Applied Mathematics' SIAM Review 19 pp. 490–501 1977

[3] W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery Numerical Recipes In 'C': The Art Of Scientific Computing Archived 2013-08-06 at the Wayback Machine p 885 ISBN 0-521-43108-5 Cambridge University Press 1988–1992

[1]

[2]

[3]