Improved cyclic reduction for solving queueing problems. The cyclic reduction technique (Buzbee et al., 1970), rephrased in functional form (Bini and Meini, 1996), provides a numerically stable, quadratically convergent method for solving the matrix equation X = ∑+ ∞ i=0 Xi Ai, where the Ai’s are nonnegative k × k matrices such that ∑+ ∞ i=0 Ai is column stochastic. In this paper we propose a further improvement of the above method, based on a point-wise evaluation/interpolation at a suitable set of Fourier points, of the functional relations defining each step of cyclic reduction (Bini and Meini,1996). This new technique allows us to devise an algorithm based on FFT having a lower computational cost and a higher numerical stability. Numerical results and comparisons are provided.

References in zbMATH (referenced in 29 articles , 1 standard article )

Showing results 1 to 20 of 29.
Sorted by year (citations)

1 2 next

  1. Gu, Guiding; Li, Wang; Li, Ren-Cang: Highly accurate Latouche-Ramaswami logarithmic reduction algorithm for quasi-birth-and-death process (2022)
  2. Bini, Dario A.; Meini, Beatrice; Meng, Jie: Solving quadratic matrix equations arising in random walks in the quarter plane (2020)
  3. Chen, Cairong; Li, Ren-Cang; Ma, Changfeng: Highly accurate doubling algorithm for quadratic matrix equation from quasi-birth-and-death process (2019)
  4. Meng, Jie; Seo, Sang-Hyup; Kim, Hyun-Min: Condition numbers and backward error of a matrix polynomial equation arising in stochastic models (2018)
  5. Maity, Arunava; Gupta, U. C.: A comparative numerical study of the spectral theory approach of Nishimura and the roots method based on the analysis of (\mathrmBDMMAP/\mathrmG/1) queue (2015)
  6. Guo, Pei-Chang: Newton-Shamanskii method for a quadratic matrix equation arising in quasi-birth-death problems (2014)
  7. Myllykoski, Mirko; Rossi, Tuomo: A parallel radix-4 block cyclic reduction algorithm. (2014)
  8. Chesnokov, Andrey; van Barel, Marc: A direct method to solve block banded block Toeplitz systems with non-banded Toeplitz blocks (2010)
  9. Lucia, Marcello; Maggio, Fabio; Rodriguez, Giuseppe: Numerical solution of the Helmholtz equation in an infinite strip by Wiener-Hopf factorization (2010)
  10. Bini, Dario A.; Meini, Beatrice: The cyclic reduction algorithm: From Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub (2009)
  11. Meini, Beatrice: Nonlinear matrix equations and structured linear algebra (2006)
  12. Bini, Dario A.; Higham, Nicholas; Meine, Beatrice: Algorithms for the matrix (p)th root (2005)
  13. Bini, Dario A.; Latouche, Guy; Meini, Beatrice: Numerical methods for structured Markov chains. (2005)
  14. Bini, Dario A.; Meini, Beatrice: Non-skip-free M/G/1-type Markov chains and Laurent matrix power series (2004)
  15. Bini, Dario A.; Latouche, Guy; Meini, Beatrice: Solving nonlinear matrix equations arising in tree-like stochastic processes. (2003)
  16. Gemignani, L.: A superfast solver for Sylvester’s resultant linear systems generated by a stable and an anti-stable polynomial (2003)
  17. Hunt, E.: A probabilistic algorithm for determining the fundamental matrix of a block M/G/1 Markov chain (2003)
  18. Alfa, Attahiru Sule; Sengupta, Bhaskar; Takine, Tetsuya; Xue, Jungong: A new algorithm for computing the rate matrix of GI/M/1 type Markov chains. (2002)
  19. Bini, D. A.; Gemignani, L.; Meini, B.: Computations with infinite Toeplitz matrices and polynomials (2002)
  20. Bini, Dario A.; Latouche, Guy; Meini, Beatrice: Solving matrix polynomial equations arising in queueing problems (2002)

1 2 next