The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Numerical Algorithms

• Publication date

  2008-11-21

• Fields of study

  Mathematics, Materials Science, Computer Science

• Identifiers
  DOI 10.1007/s11075-008-9253-0
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Positive definite solution of the matrix equation $\boldsymbol {X=Q+A^{H}(I\otimes X-C)^{\delta}A}$

  2011cited by this paper
• Matrix Computations and Semiseparable Matrices: Linear Systems

  2010cited by this paper
• Matrix Computations and Semiseparable Matrices. Volume I: Linear Systems, R. Vandebril, M. Van Barel, N. Mastronardi

  2010cited by this paper
• Fast solution of a certain Riccati equation through Cauchy-like matrices

  2009cited by this paper
• Structured Markov chains solver: tool extension

  2009cited by this paper
• Detecting and Solving Hyperbolic Quadratic Eigenvalue Problems

  2008cited by this paper
• A First Course in the Numerical Analysis of Differential Equations: Fast Poisson solvers

  2008cited by this paper
• Functions of matrices - theory and computation

  2008cited by this paper
• MATRIX COMPUTATIONS AND SEMISEPARABLE MATRICES

  2008cited by this paper
• A probabilistic interpretation of cyclic reduction and its relationships with logarithmic reduction

  2008cited by this paper
• On the Doubling Algorithm for a (Shifted) Nonsymmetric Algebraic Riccati Equation

  2007influential reference
• Iterative Solution of a Nonsymmetric Algebraic Riccati Equation

  2007cited by this paper
• From Algebraic Riccati equations to unilateral quadratic matrix equations: old and new algorithms

  2007cited by this paper
• Nonsymmetric algebraic Riccati equations associated with an M-matrix: recent advances and algorithms

  2007cited by this paper
• A note on the solution of not balanced banded Toeplitz systems

  2007cited by this paper
• Structured Markov chains solver: software tools

  2006cited by this paper
• Efficient methods for solving a nonsymmetric algebraic Riccati equation arising in stochastic fluid models

  2006cited by this paper
• A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation

  2006cited by this paper
• Structured Markov chains solver: algorithms

  2006cited by this paper
• Nonlinear matrix equations and structured linear algebra

  2006cited by this paper
• On the solution of algebraic Riccati equations arising in fluid queues

  2006cited by this paper
• Numerical Methods for Structured Markov Chains (Numerical Mathematics and Scientific Computation)

  2005cited by this paper
• Algorithms for hyperbolic quadratic eigenvalue problems

  2005cited by this paper
• M/G/1-TYPE MARKOV CHAINS

  2005cited by this paper
• Shift Techniques and Canonical Factorizations in the Solution of M/G/1-Type Markov Chains

  2005cited by this paper
• Algorithms for the matrix pth root

  2005cited by this paper
• The Matrix Square Root from a New Functional Perspective: Theoretical Results and Computational Issues

  2005influential reference
• Numerical methods for structured Markov chains

  2005influential reference
• Non-skip-free M/G/1-type Markov chains and Laurent matrix power series

  2004cited by this paper
• A quadratically convergent Bernoulli-like algorithm for solving matrix polynomial equations in Markov chains.

  2004cited by this paper
• Effective Fast Algorithms for Polynomial Spectral Factorization

  2003cited by this paper
• A note on computing the matrix square root

  2003cited by this paper
• Polynomial factorization through Toeplitz matrix computations

  2003cited by this paper
• Comments on a Shifted Cyclic Reduction Algorithm for Quasi-Birth-Death Problems

  2002cited by this paper
• Solving matrix polynomial equations arising in queueing problems

  2002cited by this paper
• Computations with infinite Toeplitz matrices and polynomials

  2002cited by this paper
• Efficient computation of the extreme solutions of X + A*X-1A = Q and X - A*X-1A = Q

  2001cited by this paper
• Structured Matrices in Mathematics, Computer Science, and Engineering II

  2001cited by this paper
• Approximate displacement rank and applications

  2001cited by this paper
• Convergence Analysis of the Latouche-Ramaswami Algorithm for Null Recurrent Quasi-Birth-Death Processes

  2001cited by this paper
• Introduction to Matrix Analytic Methods in Stochastic Modeling

  2001influential reference
• Solving certain matrix equations by means of Toeplitz computations: algorithms and applications

  2001cited by this paper
• Global Existence and Stability of Solutions of Matrix Riccati Equations

  2001cited by this paper
• Analyzing M/G/1 paradigmsthrough QBDs: the role of the block structure in computing the matrixG

  2000cited by this paper
• Advances in Algorithmic Methods for Stochastic Models

  2000cited by this paper
• A Nonstandard Cyclic Reduction Method, Its Variants and Stability

  1999cited by this paper
• Teletraffic engineering in a competitive world : proceedings of the International Teletraffic Congress - ITC-16, Edinburgh International Conference Centre, United Kingdom, 7-11 June, 1999

  1999cited by this paper
• A Parallel Fast Direct Solver for Block Tridiagonal Systems with Separable Matrices of Arbitrary Dimension

  1999cited by this paper
• Effective Methods for Solving Banded Toeplitz Systems

  1999cited by this paper
• Matrix analytic methods for stochastic fluid flows

  1999cited by this paper
• Fast reliable algorithms for matrices with structure

  1999influential reference
• Advances in matrix-analytic methods for stochastic models

  1998cited by this paper
• Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations

  1998cited by this paper
• Stabilization by perturbation of ILL-conditioned cyclic reduction

  1998cited by this paper
• Nonsymmetric Algebraic Riccati Equations and Hamiltonian-like Matrices

  1998cited by this paper
• A Cyclic Reduction Approach to the Numerical Solution of Boundary Value ODEs

  1997cited by this paper
• Improved cyclic reduction for solving queueing problems

  1997influential reference
• Cyclic Reduction - History and Applications

  1997influential reference
• Orthogonal polynomials: applications and computation

  1996cited by this paper
• Stability of the block cyclic reduction

  1996influential reference
• On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems

  1996influential reference
• Cyclic reduction algorithm for solving collocation systems

  1996cited by this paper
• Hermitian solutions of the equation X = Q + NX−1N∗

  1996cited by this paper
• On Cyclic Reduction Applied to a Class of Toeplitz-Like Matrices Arising in Queueing Problems

  1995influential reference
• Compositional Markovian Modelling Using a Process Algebra

  1995cited by this paper
• On the stability of the cyclic reduction without back substitution for tridiagonal systems

  1995cited by this paper
• Cyclic reduction and FACR methods for piecewise hermite bicubic orthogonal spline collocation

  1994cited by this paper
• Backward error analysis of cyclic reduction for the solution of tridiagonal systems

  1994cited by this paper
• Cyclic Reduction for Special Tridiagonal Systems

  1994cited by this paper
• Fluid Models in Queueing Theory and Wiener-Hopf Factorization of Markov Chains

  1994cited by this paper
• Optimized cyclic reduction for the solution of linear tridiagonal systems on parallel computers

  1993cited by this paper
• Necessary and sufficient conditions for the existence of a positive definite solution of the matrix equation X + A*X-1A = Q

  1993cited by this paper
• Parallel factorizations for tridiagonal matrices

  1993cited by this paper
• A Parallel Version of the Cyclic Reduction Algorithm on a Hypercube

  1993cited by this paper
• A logarithmic reduction algorithm for quasi-birth-death processes

  1993cited by this paper
• A Tricyclic Tridiagonal Equation Solver

  1992cited by this paper
• Analysis of multimedia traffic queues with finite buffer and overload control II. Applications

  1992cited by this paper
• Algorithms for Special Tridiagonal Systems

  1991cited by this paper
• Analysis of multi-media traffic queues with finite buffer and overload control. I. Algorithm

  1991cited by this paper
• Optimizing Tridiagonal Solvers for Alternating Direction Methods on Boolean Cube Multiprocessors

  1989cited by this paper
• The ordering of tridiagonal matrices in the cyclic reduction method for Poisson's equation

  1989cited by this paper
• Vector and parallel methods for the direct solution of Poisson's equation

  1989cited by this paper
• Structured Stochastic Matrices of M/G/1 Type and Their Applications

  1989cited by this paper
• Truncated interval arithmetic block cyclic reduction

  1989cited by this paper
• Cyclic reduction for tridiagonal systems of equations with interval coefficients on vector computers

  1989cited by this paper
• A Parallel and Vector Variant of the Cyclic Reduction Algorithm

  1988cited by this paper
• Applied and Computational Complex Analysis.

  1988cited by this paper
• Fast Poisson solvers for MIMD computers

  1988cited by this paper
• Approximate Cyclic Reduction for Solving Poisson's Equation

  1987cited by this paper
• A parallel block cyclic reduction algorithm for the fast solution of elliptic equations

  1987cited by this paper
• Preconditioning by incomplete block cyclic reduction

  1984cited by this paper
• A ‘potential-theoretic’ note on the quadratic Wiener-Hopf equation for Q-matrices

  1982cited by this paper
• Matrix-Geometric Solutions in Stochastic Models

  1981cited by this paper
• Parallel Computers 2: Architecture, Programming and Algorithms

  1981cited by this paper
• On the FACR( l) algorithm for the discrete Poisson equation

  1980cited by this paper
• Linear Systems

  1980cited by this paper
• Direct methods for the solution of the discrete Poisson equation: Some comparisons

  1979cited by this paper
• Algorithm 541: Efficient Fortran Subprograms for the Solution of Separable Elliptic Partial Differential Equations [D3]

  1979cited by this paper
• THE METHODS OF CYCLIC REDUCTION, FOURIER ANALYSIS AND THE FACR ALGORITHM FOR THE DISCRETE SOLUTION OF POISSON'S EQUATION ON A RECTANGLE*

  1977cited by this paper
• A Cyclic Reduction Algorithm for Solving Block Tridiagonal Systems of Arbitrary Dimension

  1977cited by this paper

• A Block-Shifted Cyclic Reduction Algorithm for Solving a Class of Quadratic Matrix Equations

  2025influential citation
• Cyqlone: A Parallel, High-Performance Linear Solver for Optimal Control

  2025cites this paper
• Multi-Dimensional Markov Chains of M/G/1 Type

  2025cites this paper
• Computing the matrix square root with the doubling algorithm

  2025cites this paper
• A matching Schur complement preconditioning technique for inverse source problems

  2024cites this paper
• On certain classes of nonlinear matrix equations: theory, applications, and numerical solution

  2024cites this paper
• A structure-preserving doubling algorithm for the square root of regular M-matrix

  2024cites this paper
• Deflating subspaces of T-palindromic pencils and algebraic T-Riccati equations

  2024influential citation
• Pointwise Error Estimates of Numerical Solutions to Linear Quadratic Optimal Control Problems

  2024cites this paper
• Parallel cyclic reduction of padded bordered almost block diagonal matrices

  2024cites this paper
• Invariant subspaces of T-palindromic pencils and algebraic T-Riccati equations

  2023influential citation
• DeepPCR: Parallelizing Sequential Operations in Neural Networks

  2023cites this paper
• Theoretical analysis of the extended cyclic reduction algorithm

  2022cites this paper
• Taylor polynomials as an estimator for certain toeplitz matrices

  2022cites this paper
• Speedup of tridiagonal system solvers

  2021cites this paper
• Roots of Characteristic Polynomial Sequences in Iterative Block Cyclic Reductions

  2021cites this paper
• A family of fast fixed point iterations for M/G/1-type Markov chains

  2020cites this paper
• Lösung linearer Gleichungssysteme

  2020cites this paper
• A fast method for solving a block tridiagonal quasi-Toeplitz linear system

  2020cites this paper
• Low-rank updates and divide-and-conquer methods for quadratic matrix equations

  2019cites this paper
• ON NEWTON'S METHOD FOR SOLVING A SYSTEM OF NONLINEAR MATRIX EQUATIONS

  2019cites this paper
• On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes

  2018influential citation
• Parallel cyclic reduction strategies for linear systems that arise in dynamic optimization problems

  2018cites this paper
• Electrical Networks and Algebraic Graph Theory: Models, Properties, and Applications

  2018cites this paper
• On solving separable block tridiagonal linear systems using a GPU implementation of radix-4 PSCR method

  2018cites this paper
• Doubling algorithms for stationary distributions of fluid queues: A probabilistic interpretation

  2018influential citation
• Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox

  2018cites this paper
• Robust and scalable hierarchical matrix-based fast direct solver and preconditioner for the numerical solution of elliptic partial differential equations

  2017cites this paper
• A specialised cyclic reduction algorithm for linear algebraic equation systems with quasi-tridiagonal matrices

  2017cites this paper
• Efficient cyclic reduction for Quasi-Birth–Death problems with rank structured blocks

  2017cites this paper
• A fast algorithm of two-level banded Toeplitz systems of linear equations with application to image restoration

  2017cites this paper
• Efficient cyclic reduction for QBDs with rank structured blocks

  2016influential citation
• Parallel Solution of Diagonally Dominant Banded Triangular Toeplitz Systems Using Taylor Polynomials

  2016cites this paper
• Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes

  2016cites this paper
• Banded Linear Systems

  2016cites this paper
• On the decay of the off-diagonal singular values in cyclic reduction

  2016cites this paper
• Special Linear Systems

  2016cites this paper
• Decay bounds for the numerical quasiseparable preservation in matrix functions

  2016cites this paper
• Matrix structures in queuing models

  2016cites this paper
• Domain decomposition based coupling between the lattice Boltzmann method and traditional CFD methods - Part II: Numerical solution to the backward facing step flow

  2015cites this paper
• An iteration‐based hybrid parallel algorithm for tridiagonal systems of equations on multi‐core architectures

  2015cites this paper
• Parallel algorithm for solving penta-diagonal linear systems

  2015cites this paper
• A fast algorithm for solving banded Toeplitz systems

  2015influential citation
• A parallel radix‐4 block cyclic reduction algorithm

  2014cites this paper
• Fast solution of unsymmetric banded Toeplitz systems by means of spectral factorizations and Woodbury's formula

  2014cites this paper
• A Hybrid Parallel Tridiagonal Solver on Multi-core Architectures

  2014cites this paper
• The palindromic cyclic reduction and related algorithms

  2014cites this paper
• An Accelerated Recursive Doubling Algorithm for Block Tridiagonal Systems

  2014cites this paper
• Matrix structures and applications

  2014cites this paper
• On solution of large systems of linear equations with block-Toeplitz banded matrices

  2013cites this paper
• A Parallel Solver for Incompressible Fluid Flows

  2013cites this paper
• Revisiting parallel cyclic reduction and parallel prefix-based algorithms for block tridiagonal systems of equations

  2013cites this paper
• Numerical Solution of Algebraic Riccati Equations

  2012influential citation
• Applied Parallel and Scientific Computing

  2012influential citation
• Fast Modeling of Radiation and Conduction Heat Transfer and application example

  2012cites this paper
• Fast Poisson Solvers for Graphics Processing Units

  2012cites this paper
• Algorithms for Quadratic Matrix and Vector Equations

  2012cites this paper
• Kron Reduction of Graphs With Applications to Electrical Networks

  2011influential citation
• Rapid Elliptic Solvers

  2011cites this paper
• Spectral Properties and Companion Forms of Operator- and Matrix Polynomials

  2011cites this paper
• A Compressed Cyclic Reduction for QBD processes with Low-Rank Upper and Lower Transitions

  2011cites this paper
• Matrix‐Geometric Distributions

  2011cites this paper
• Laminar magnetohydrodynamic duct flow in the presence of a magnetic dipole

  2011cites this paper
• Using the Sherman–Morrison–Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems

  2011cites this paper
• Transforming algebraic Riccati equations into unilateral quadratic matrix equations

  2010cites this paper
• Parallelizing Hilbert-Huang Transform on a GPU

  2010cites this paper
• Structured Markov chains solver: tool extension

  2009cites this paper