# Cyclic reduction

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Cyclic_reduction
> Markdown URL: https://mediated.wiki/source/Cyclic_reduction.md
> Source: https://en.wikipedia.org/wiki/Cyclic_reduction
> Source revision: 1246515636
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

'''Cyclic reduction''' is a [numerical method](/source/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](/source/Toeplitz_matrix). Such problems often arise in implicit solutions for partial differential equations on a lattice.  For example fast solvers for [Poisson's equation](/source/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,<ref>Walter Gander and Gene H. Golub, [http://www.inf.ethz.ch/personal/gander/papers/cyclic.pdf Cyclic Reduction – History and Applications], Proceedings of the Workshop on Scientific Computing 10–12 March 1997</ref> 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](/source/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](/source/fast_Fourier_transform) FFT==
Transforming from the spatial domain and restating the PDE is called a [spectral method](/source/spectral_method), Fourier analysis and cyclic reduction are combined in the FACR algorithm<ref>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.&nbsp;490–501 1977</ref> which is explained in Numerical Recipes – see 19.4 Fourier and Cyclic Reduction Methods for Boundary Value Problems.<ref>W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery [http://www2.units.it/ipl/students_area/imm2/files/Numerical_Recipes.pdf Numerical Recipes In 'C': The Art Of Scientific Computing] {{Webarchive|url=https://web.archive.org/web/20130806091928/http://www2.units.it/ipl/students_area/imm2/files/Numerical_Recipes.pdf |date=2013-08-06 }} p 885 {{ISBN|0-521-43108-5}} Cambridge University Press 1988–1992</ref>

==Notes and references==

{{Reflist}}

{{Numerical PDE}}

Category:Numerical differential equations

{{Mathanalysis-stub}}

---
Adapted from the Wikipedia article [Cyclic reduction](https://en.wikipedia.org/wiki/Cyclic_reduction) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Cyclic_reduction?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.