The cyclic reduction algorithm: From Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub (Q1027772)

The paper is devoted to the study of the features of the cyclic reduction (CR) algorithm for solving the discrete Poisson equation. In the beginning, the original formulation of the Poisson equation solution is presented, and some computational issues of CR, together with the roles of the even-odd and the odd-even permutation are discussed. The classical convergence properties are further recalled. Recent properties of CR including its functional formulation and its relationship with Graeffe iteration are discussed. A new formula for performing the CR step by avoiding breakdown is proven. Extensions of CR to block Hessenberg block Toeplitz matrices are reported, both for finite and for infinite systems, together with the evaluation/interpolation techniques for implementing CR. Convergence properties for this case are proven. Finally, CR applications are considered. Block banded Toeplitz systems, quadratic matrix equations, polynomial and power series matrix equations, matrix square root and algebraic Riccati equations are discussed. An effective technique which provides a substantial acceleration of CR in the applications is given, that is fundamental in critical cases.