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 22 articles , 1 standard article )

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

1 2 next

  1. 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 BDMMAP/G/1 queue (2015)
  2. Guo, Pei-Chang: Newton-Shamanskii method for a quadratic matrix equation arising in quasi-birth-death problems (2014)
  3. Chesnokov, Andrey; van Barel, Marc: A direct method to solve block banded block Toeplitz systems with non-banded Toeplitz blocks (2010)
  4. Bini, Dario A.; Meini, Beatrice: The cyclic reduction algorithm: From Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub (2009)
  5. Meini, Beatrice: Nonlinear matrix equations and structured linear algebra (2006)
  6. Bini, Dario A.; Higham, Nicholas; Meine, Beatrice: Algorithms for the matrix $p$th root (2005)
  7. Bini, Dario A.; Latouche, Guy; Meini, Beatrice: Numerical methods for structured Markov chains. (2005)
  8. Bini, Dario A.; Meini, Beatrice: Non-skip-free M/G/1-type Markov chains and Laurent matrix power series (2004)
  9. Bini, Dario A.; Latouche, Guy; Meini, Beatrice: Solving nonlinear matrix equations arising in tree-like stochastic processes. (2003)
  10. Gemignani, L.: A superfast solver for Sylvester’s resultant linear systems generated by a stable and an anti-stable polynomial (2003)
  11. Hunt, E.: A probabilistic algorithm for determining the fundamental matrix of a block M/G/1 Markov chain (2003)
  12. 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)
  13. Bini, D.A.; Gemignani, L.; Meini, B.: Computations with infinite Toeplitz matrices and polynomials (2002)
  14. Bini, Dario A.; Latouche, Guy; Meini, Beatrice: Solving matrix polynomial equations arising in queueing problems (2002)
  15. Meini, Beatrice: Matrix equations and structures: Efficient solution of special discrete algebraic Riccati equations (2001)
  16. Bini, Dario Andrea; Meini, Beatrice: Effective methods for solving banded Toeplitz systems (1999)
  17. Favati, Paola; Meini, Beatrice: On functional iteration methods for solving nonlinear matrix equations arising in queueing problems (1999)
  18. Kailath, T. (ed.); Sayed, A.H. (ed.): Fast reliable algorithms for matrices with structure (1999)
  19. Latouche, G.; Ramaswami, V.: Introduction to matrix analytic methods in stochastic modeling (1999)
  20. Favati, Paola; Meini, Beatrice: Relaxed functional iteration techniques for the numerical solution of $M/G/1$ type Markov chains (1998)

1 2 next