Cyclic reduction

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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, 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.

Notes and references

Text derived from https://en.wikipedia.org/w/index.php?oldid=1246515636 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001246515636 · captured 1726741235.0 · version history

Cite this page as: encyclopegia.org, “Cyclic reduction”, snapshot enwiki-001246515636. https://encyclopegia.org/a/cyclic-reduction

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.