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

From MaRDI portal
Revision as of 14:54, 28 February 2024 by SwMATHimport240215 (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
The cyclic reduction algorithm: From Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub
scientific article

    Statements

    The cyclic reduction algorithm: From Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub (English)
    0 references
    0 references
    0 references
    30 June 2009
    0 references
    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.
    0 references
    iterative methods
    0 references
    cyclic reduction
    0 references
    Toeplitz systems
    0 references
    Hessenberg systems
    0 references
    Markov chains
    0 references
    matrix equations
    0 references
    Poisson equation
    0 references
    convergence
    0 references
    Graeffe iteration
    0 references
    matrix square root
    0 references
    algebraic Riccati equations
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references