By using the concept of generating function associated with a Toeplitz matrix, we analyze existence conditions for the probability invariant vector π of certain stochastic semi-infinite Toeplitz-like matrices. An application to the shortest queue problem is shown. By exploiting the functional formulation given in terms of generating functions, we devise a weakly numerically stable algorithm for computing the probability invariant vector π. The algorithm is divided into three stages. At the first stage the zeros of a complex function are numerically computed by means of an extension of the Aberth method. At the second stage the first k components of π are computed by solving an interpolation problem, where k is a suitable constant associated with the matrix. Finally, at the third stage a triangular Toeplitz system is solved and its solution is refined by applying the power method or any other refinement method based on regular splittings. In the solution of the triangular Toeplitz system and at each step of the refinement method, special FFT-based techniques are applied in order to keep the arithmetic cost within the O(n log n) bound, where n is an upper bound to the number of the computed components. Numerical comparisons with the available algorithms show the effectiveness of our algorithm in a wide set of cases.

Solving certain queueing problems modelled by Toeplitz matrices

BINI, DARIO ANDREA;MEINI, BEATRICE
1993

Abstract

By using the concept of generating function associated with a Toeplitz matrix, we analyze existence conditions for the probability invariant vector π of certain stochastic semi-infinite Toeplitz-like matrices. An application to the shortest queue problem is shown. By exploiting the functional formulation given in terms of generating functions, we devise a weakly numerically stable algorithm for computing the probability invariant vector π. The algorithm is divided into three stages. At the first stage the zeros of a complex function are numerically computed by means of an extension of the Aberth method. At the second stage the first k components of π are computed by solving an interpolation problem, where k is a suitable constant associated with the matrix. Finally, at the third stage a triangular Toeplitz system is solved and its solution is refined by applying the power method or any other refinement method based on regular splittings. In the solution of the triangular Toeplitz system and at each step of the refinement method, special FFT-based techniques are applied in order to keep the arithmetic cost within the O(n log n) bound, where n is an upper bound to the number of the computed components. Numerical comparisons with the available algorithms show the effectiveness of our algorithm in a wide set of cases.
Bini, DARIO ANDREA; Meini, Beatrice
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/175412
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact