{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:35:57Z","timestamp":1787322957775,"version":"3.56.0"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[1996,10]]},"abstract":"<jats:p>By extending the cyclic reduction technique to infinite block matrices we devise a new algorithm for computing the solution $G_0 $ of the matrix equation $G = \\Sigma _{i = 0}^{ + \\infty } G^i A_i $ arising in a wide class of queueing problems. Here $A_i ,i = 0,1, \\cdots ,$ are $k \\times k$ nonnegative matrices such that $\\Sigma _{i = 0}^{ + \\infty } A_i $ is column stochastic. Our algorithm, which under mild conditions generates a sequence of matrices converging quadratically to $G_0 $, can be fully described in terms of simple operations between matrix power series, i.e., power series in z having matrix coefficients. Such operations, like multiplication and reciprocation modulo $z^m $, can be quickly computed by means of FFT-based fast polynomial arithmetic; here m is the degree where the power series are numerically cut off in order to reduce them to polynomials. These facts lead to a dramatic reduction of the complexity of solving the given matrix equation; in fact, $O( k^3 m + k^2 m \\log m )$ arithmetic operations are sufficient to carry out each iteration of the algorithm. Numerical experiments and comparisons performed with the customary techniques show the effectiveness of our algorithm. For a problem arising from the modelling of metropolitan networks, our algorithm was about 30 times faster than the algorithms customarily used in the applications. Cyclic reduction applied to quasi-birth-death (QBD) problems, i.e., problems where $A_i = O$ for $i &gt; 2$, leads to an algorithm similar to the one of [Latouche and Ramaswami, J. Appi. Probab., 30 (1993), pp. 650\u2013674], but which has a lower computational cost.<\/jats:p>","DOI":"10.1137\/s0895479895284804","type":"journal-article","created":{"date-parts":[[2005,2,27]],"date-time":"2005-02-27T07:15:07Z","timestamp":1109488507000},"page":"906-926","source":"Crossref","is-referenced-by-count":107,"title":["On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems"],"prefix":"10.1137","volume":"17","author":[{"given":"Dario","family":"Bini","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Beatrice","family":"Meini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","unstructured":"G. Anastasi, L. Lenzini, B. Meini,  Performance Evaluation of a Worst Case Model of the Metaring MAC Protocol with Global Fairness, Performance Evaluation, to appear"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"D. Bini, B. Meini,  On cyclic reduction applied to a class of Toeplitz-like matrices arising in queueing problems,  Proc. of the Second International Workshop on Numerical Solution of Markov Chains, Raleigh, NC,  1995,  21\u201338 0862.60085","DOI":"10.1007\/978-1-4615-2241-6_2"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0265-3"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(86)90001-4"},{"key":"R5","volume-title":"The computational complexity of algebraic and numeric problems","author":"Borodin Allan","year":"1975"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0707049"},{"key":"R7","volume-title":"Introduction to stochastic processes","author":"\u00c7inlar Erhan","year":"1975"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.5.1107"},{"key":"R9","unstructured":"G. Latouche,  Algorithms for Evaluating the Matrix\n                      G\n                      in Markov Chains of  $PH\/G\/1$ Type, Bellcore Tech. report, Moorestown, NJ, 1992"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/14.4.583"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.2307\/3214773"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"G. Latouche, G. W. Stewart,  Numerical methods for  $M\/G\/1$ type queues,  Proc. of the Second International Workshop on Numerical Solution of Markov Chains, Raleigh, NC,  1995,  571\u2013581 0871.60072","DOI":"10.1007\/978-1-4615-2241-6_30"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0729085"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050303"},{"key":"R15","volume-title":"Structured stochastic matrices of $M\/G\/1$ type and their applications","author":"Neuts Marcel F.","year":"1989"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/1030046"},{"key":"R17","unstructured":"G. W. Stewart,  Implementing an Algorithm for Solving Block Hessenberg Systems, Tech. report, CS-TR-3295, Department of Computer Science, University of Maryland, College Park, MD,  1993"},{"key":"R18","volume-title":"Matrix Iterative Analysis","author":"Varga R.","year":"1963"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895479895284804","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:35:44Z","timestamp":1787319344000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895479895284804"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,10]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,10]]}},"alternative-id":["10.1137\/S0895479895284804"],"URL":"https:\/\/doi.org\/10.1137\/s0895479895284804","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,10]]}}}