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

DOI10.1007/S11075-008-9253-0zbMath1170.65021OpenAlexW1498989325MaRDI QIDQ1027772

Beatrice Meini, Dario Andrea Bini

Publication date: 30 June 2009

Published in: Numerical Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11075-008-9253-0

zbMATH Keywords

convergenceMarkov chainsiterative methodsmatrix square rootPoisson equationmatrix equationsalgebraic Riccati equationscyclic reductionToeplitz systemsGraeffe iterationHessenberg systems

Mathematics Subject Classification ID

Stationary stochastic processes (60G10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Matrix equations and identities (15A24) Numerical analysis or methods applied to Markov chains (65C40) Iterative numerical methods for linear systems (65F10) Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Finite difference methods for boundary value problems involving PDEs (65N06)

Related Items (21)

On solution of large systems of linear equations with block-Toeplitz banded matrices ⋮ Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes ⋮ Parallel cyclic reduction strategies for linear systems that arise in dynamic optimization problems ⋮ Efficient cyclic reduction for quasi-birth-death problems with rank structured blocks ⋮ Low-rank updates and divide-and-conquer methods for quadratic matrix equations ⋮ A parallel radix-4 block cyclic reduction algorithm ⋮ Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox ⋮ A specialised cyclic reduction algorithm for linear algebraic equation systems with quasi-tridiagonal matrices ⋮ Speedup of tridiagonal system solvers ⋮ Pointwise error estimates of numerical solutions to linear quadratic optimal control problems ⋮ Using the Sherman-Morrison-Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems ⋮ Matrix Structures in Queuing Models ⋮ A fast method for solving a block tridiagonal quasi-Toeplitz linear system ⋮ On the decay of the off-diagonal singular values in cyclic reduction ⋮ A fast algorithm for solving banded Toeplitz systems ⋮ Transforming algebraic Riccati equations into unilateral quadratic matrix equations ⋮ The palindromic cyclic reduction and related algorithms ⋮ Decay bounds for the numerical quasiseparable preservation in matrix functions ⋮ Fast solution of unsymmetric banded Toeplitz systems by means of spectral factorizations and Woodbury's formula ⋮ A Compressed Cyclic Reduction for QBD processes with Low-Rank Upper and Lower Transitions ⋮ ON NEWTON'S METHOD FOR SOLVING A SYSTEM OF NONLINEAR MATRIX EQUATIONS

Uses Software

• FISHPAK
• na12
• OPQ
• SMCSolver
• mftoolbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic interpretation of cyclic reduction and its relationships with logarithmic reduction
• Nonlinear matrix equations and structured linear algebra
• On the solution of algebraic Riccati equations arising in fluid queues
• Fast solution of a certain Riccati equation through Cauchy-like matrices
• Fast Poisson solvers for MIMD computers
• A parallel block cyclic reduction algorithm for the fast solution of elliptic equations
• Vector and parallel methods for the direct solution of Poisson's equation
• On the FACR(l) algorithm for the discrete Poisson equation
• Direct methods for the solution of the discrete Poisson equation: some comparisons
• The ordering of tridiagonal matrices in the cyclic reduction method for Poisson's equation
• A parallel version of the cyclic reduction algorithm on a hypercube
• Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains
• Cyclic reduction and FACR methods for piecewise Hermite bicubic orthogonal spline collocation
• Computations with infinite Toeplitz matrices and polynomials
• Improved cyclic reduction for solving queueing problems
• Effective fast algorithms for polynomial spectral factorization
• Non-skip-free M/G/1-type Markov chains and Laurent matrix power series
• A quadratically convergent Bernoulli-like algorithm for solving matrix polynomial equations in Markov chains
• Necessary and sufficient conditions for the existence of a positive definite solution of the matrix equation \(X+A^*X^{-1}A=Q\)
• Truncated interval arithmetic block cyclic reduction
• Manifestations of the Schur complement
• Polynomial factorization through Toeplitz matrix computations
• On the stability of the cyclic reduction without back substitution for tridiagonal systems
• Optimized cyclic reduction for the solution of linear tridiagonal systems on parallel computers
• Efficient methods for solving a nonsymmetric algebraic Riccati equation arising in stochastic fluid models
• A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation
• Algorithms for the matrix \(p\)th root
• A note on computing the matrix square root
• Stability of the block cyclic reduction
• Hermitian solutions of the equation \(X=Q+NX^{-1}N^*\)
• Addition à notre memoire: Recherches sur la méthode de Graeffe et les zéros des polynômes et des séries de Laurent. (Acta mathematica 72, 1940/41.)
• Cyclic reduction algorithm for solving collocation systems
• Convergence Analysis of the Latouche--Ramaswami Algorithm for Null Recurrent Quasi-Birth-Death Processes
• A Cyclic Reduction Approach to the Numerical Solution of Boundary Value ODEs
• Algorithms for Special Tridiagonal Systems
• Optimizing Tridiagonal Solvers for Alternating Direction Methods on Boolean Cube Multiprocessors
• Preconditioning By Incomplete Block Cyclic Reduction
• A note on the solution of not balanced banded Toeplitz systems
• On the Doubling Algorithm for a (Shifted) Nonsymmetric Algebraic Riccati Equation
• Detecting and Solving Hyperbolic Quadratic Eigenvalue Problems
• Approximate Cyclic Reduction for Solving Poisson’s Equation
• A Parallel and Vector Variant of the Cyclic Reduction Algorithm
• Cyclic Reduction for Tridiagonal Systems of Equations with Interval Coefficients on Vector Computers
• Stabilization by perturbation of ILL-conditioned cyclic reduction^∗
• Algorithm 541: Efficient Fortran Subprograms for the Solution of Separable Elliptic Partial Differential Equations [D3]
• A Tricyclic Tridiagonal Equation Solver
• A direct Method for the Discrete Solution of Separable Elliptic Equations
• On a Cyclic Reduction Method for the Solution of Poisson’s Equations
• Some Aspects of the Cyclic Reduction Algorithm for Block Tridiagonal Linear Systems
• The Methods of Cyclic Reduction, Fourier Analysis and the FACR Algorithm for the Discrete Solution of Poisson’s Equation on a Rectangle
• A Cyclic Reduction Algorithm for Solving Block Tridiagonal Systems of Arbitrary Dimension
• Second-order convergent algorithms for the steady-state Riccati equation†
• Parallel Factorizations for Tridiagonal Matrices
• Introduction to Matrix Analytic Methods in Stochastic Modeling
• Nonsymmetric Algebraic Riccati Equations and Hamiltonian-like Matrices
• A Nonstandard Cyclic Reduction Method, Its Variants and Stability
• Effective Methods for Solving Banded Toeplitz Systems
• A Parallel Fast Direct Solver for Block Tridiagonal Systems with Separable Matrices of Arbitrary Dimension
• A logarithmic reduction algorithm for quasi-birth-death processes
• Cyclic Reduction for Special Tridiagonal Systems
• Backward Error Analysis of Cyclic Reduction for the Solution of Tridiagonal Systems
• Comments on a Shifted Cyclic Reduction Algorithm for Quasi-Birth-Death Problems
• Efficient computation of the extreme solutions of $X+A^*X^{-1}A=Q$ and $X-A^*X^{-1}A=Q$
• The Matrix Square Root from a New Functional Perspective: Theoretical Results and Computational Issues
• On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems
• Algorithms for hyperbolic quadratic eigenvalue problems
• Functions of Matrices
• Iterative Solution of a Nonsymmetric Algebraic Riccati Equation
• Numerical Methods for Structured Markov Chains
• Shift Techniques and Canonical Factorizations in the Solution of M/G/1-Type Markov Chains
• A Fast Direct Solution of Poisson's Equation Using Fourier Analysis
• On Direct Methods for Solving Poisson’s Equations
• Global existence and stability of solutions of matrix Riccati equations
• Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations
• Solving matrix polynomial equations arising in queueing problems

This page was built for publication: The cyclic reduction algorithm: From Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub