Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes


Authors: Dario A. Bini, Stefano Massei and Beatrice Meini
Journal: Math. Comp.
MSC (2010): Primary 15A16, 65F60, 15B05
DOI: https://doi.org/10.1090/mcom/3301
Published electronically: January 24, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Denote by $ \mathcal {W}_1$ the set of complex valued functions of the form $ a(z)=\sum _{i=-\infty }^{+\infty }a_iz^i$ such that $ \sum _{i=-\infty }^{+\infty }\vert ia_i\vert<\infty $. We call QT-matrix a quasi-Toeplitz matrix $ A$, associated with a symbol $ a(z)\in \mathcal W_1$, of the form $ A=T(a)+E$, where $ T(a)=(t_{i,j})_{i,j\in \mathbb{Z}^+}$ is the semi-infinite Toeplitz matrix such that $ t_{i,j}=a_{j-i}$, for $ i,j\in \mathbb{Z}^+$, and $ E=(e_{i,j})_{i,j\in \mathbb{Z}^+}$ is a semi-infinite matrix such that $ \sum _{i,j=1}^{+\infty }\vert e_{i,j}\vert$ is finite. We prove that the class of QT-matrices is a Banach algebra with a suitable sub-multiplicative matrix norm. We introduce a finite representation of QT-matrices together with algorithms which implement elementary matrix operations. An application to solving quadratic matrix equations of the kind $ AX^2+BX+C=0$, encountered in the solution of Quasi-Birth and Death (QBD) stochastic processes with a denumerable set of phases, is presented where $ A,B,C$ are QT-matrices.


References [Enhancements On Off] (What's this?)

  • [1] B. Beckermann and A. Townsend,
    On the singular values of matrices with displacement,
    Technical report, arXiv:1609.09494, 2016.
  • [2] Michele Benzi and Paola Boito, Decay properties for functions of matrices over $ C^*$-algebras, Linear Algebra Appl. 456 (2014), 174-198. MR 3223897, https://doi.org/10.1016/j.laa.2013.11.027
  • [3] Michele Benzi and Valeria Simoncini, Decay bounds for functions of Hermitian matrices with banded or Kronecker structure, SIAM J. Matrix Anal. Appl. 36 (2015), no. 3, 1263-1282. MR 3391978, https://doi.org/10.1137/151006159
  • [4] Daniele Bertaccini and Fabio Di Benedetto, Spectral analysis of nonsymmetric quasi-Toeplitz matrices with applications to preconditioned multistep formulas, SIAM J. Numer. Anal. 45 (2007), no. 6, 2345-2367. MR 2361893, https://doi.org/10.1137/060650349
  • [5] D. A. Bini, G. Fiorentino, L. Gemignani, and B. Meini, Effective fast algorithms for polynomial spectral factorization, Numer. Algorithms 34 (2003), no. 2-4, 217-227. International Conference on Numerical Algorithms, Vol. II (Marrakesh, 2001). MR 2043897, https://doi.org/10.1023/B:NUMA.0000005364.00003.ea
  • [6] D. A. Bini, L. Gemignani, and B. Meini, Computations with infinite Toeplitz matrices and polynomials, Linear Algebra Appl. 343/344 (2002), 21-61. Special issue on structured and infinite systems of linear equations. MR 1878936, https://doi.org/10.1016/S0024-3795(01)00341-X
  • [7] D. A. Bini, G. Latouche, and B. Meini, Numerical Methods for Structured Markov Chains, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2005,. Oxford Science Publications. MR 2132031
  • [8] D. A. Bini, S. Massei, and B. Meini, On functions of quasi Toeplitz matrices, Mat. Sb. 208 (2017), no. 11, 56-74 (Russian). MR 3717197
  • [9] Dario A. Bini and Beatrice Meini, The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub, Numer. Algorithms 51 (2009), no. 1, 23-60. MR 2505832, https://doi.org/10.1007/s11075-008-9253-0
  • [10] D. A. Bini and B. Meini,
    On the exponential of semi-infinite quasi Toeplitz matrices,
    arXiv:1611.06380v2, 2016.
  • [11] Albrecht Böttcher and Sergei M. Grudsky, Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis, Birkhäuser Verlag, Basel, 2000. MR 1772773
  • [12] Albrecht Böttcher and Sergei M. Grudsky, Spectral Properties of Banded Toeplitz Matrices, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. MR 2179973
  • [13] Albrecht Böttcher and Bernd Silbermann, Introduction To Large Truncated Toeplitz Matrices, Universitext, Springer-Verlag, New York, 1999. MR 1724795
  • [14] David R. Brillinger, The analyticity of the roots of a polynomial as functions of the coefficients, Math. Mag. 39 (1966), 145-147. MR 0204616, https://doi.org/10.2307/2689304
  • [15] B. L. Buzbee, G. H. Golub, and C. W. Nielson, On direct methods for solving Poisson's equations, SIAM J. Numer. Anal. 7 (1970), 627-656. MR 0287717, https://doi.org/10.1137/0707049
  • [16] Guy Fayolle, Roudolf Iasnogorodski, and Vadim Malyshev, Random Walks in the Quarter-plane: Algebraic Methods, Boundary Value Problems and Applications, Applications of Mathematics (New York), vol. 40, Springer-Verlag, Berlin, 1999. MR 1691900
  • [17] I. C. Gohberg, On an application of the theory of normed rings to singular integral equations, Uspehi Matem. Nauk (N.S.) 7 (1952), no. 2(48), 149-156 (Russian). MR 0048689
  • [18] R. W. Hockney, A fast direct solution of Poisson's equation using Fourier analysis, J. Assoc. Comput. Mach. 12 (1965), 95-113. MR 0213048, https://doi.org/10.1145/321250.321259
  • [19] James R. Jackson, Networks of waiting lines, Operations Res. 5 (1957), 518-521. MR 0093061
  • [20] Masahiro Kobayashi and Masakiyo Miyazawa, Revisiting the tail asymptotics of the double QBD process: refinement and complete solutions for the coordinate and diagonal directions, Matrix-analytic methods in stochastic models, Springer Proc. Math. Stat., vol. 27, Springer, New York, 2013, pp. 145-185. MR 3067681, https://doi.org/10.1007/978-1-4614-4909-6_8
  • [21] Daniel Kressner and Robert Luce, Fast Computation of the Matrix Exponential for a Toeplitz Matrix, SIAM J. Matrix Anal. Appl. 39 (2018), no. 1, 23-47. MR 3743744
  • [22] D. P. Kroese, W. R. W. Scheinhardt, and P. G. Taylor, Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process, Ann. Appl. Probab. 14 (2004), no. 4, 2057-2089. MR 2099663, https://doi.org/10.1214/105051604000000477
  • [23] G. Latouche, S. Mahmoodi, and P. G. Taylor,
    Level-phase independent stationary distributions for gi/m/1-type markov chains with infinitely-many phases,
    Perform. Eval., 70 (2013), no. 9, 551-563.
  • [24] Guy Latouche and Masakiyo Miyazawa, Product-form characterization for a two-dimensional reflecting random walk, Queueing Syst. 77 (2014), no. 4, 373-391. MR 3225816, https://doi.org/10.1007/s11134-013-9381-7
  • [25] G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling, ASA-SIAM Series on Statistics and Applied Probability, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; American Statistical Association, Alexandria, VA, 1999. MR 1674122
  • [26] S. Massei.
    Exploiting rank structures in the numerical solution of Markov chains and matrix functions,
    PhD thesis, Scuola Normale Superiore, Pisa, 2017.
  • [27] Masakiyo Miyazawa, Light tail asymptotics in multidimensional reflecting processes for queueing networks, TOP 19 (2011), no. 2, 233-299. MR 2859501, https://doi.org/10.1007/s11750-011-0179-7
  • [28] Allan J. Motyer and Peter G. Taylor, Decay rates for quasi-birth-and-death processes with countably many phases and tridiagonal block generators, Adv. in Appl. Probab. 38 (2006), no. 2, 522-544. MR 2264956, https://doi.org/10.1239/aap/1151337083
  • [29] Marcel F. Neuts, Matrix-geometric Solutions in Stochastic Models: An Algorithmic Approach, Johns Hopkins Series in the Mathematical Sciences, vol. 2, Johns Hopkins University Press, Baltimore, Md., 1981. MR 618123
  • [30] Alexandre Ostrowski, Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent, Acta Math. 72 (1940), 99-155 (French). MR 0001944, https://doi.org/10.1007/BF02546329
  • [31] S. Pozza and V. Simoncini,
    Decay bounds for non-hermitian matrix functions,
    Technical report, arXiv:1605.01595v3, 2016.
  • [32] Yutaka Sakuma and Masakiyo Miyazawa, On the effect of finite buffer truncation in a two-node Jackson network, J. Appl. Probab. 42 (2005), no. 1, 199-222. MR 2144904
  • [33] S. Serra Capizzano, Generalized locally Toeplitz sequences: spectral analysis and applications to discretized partial differential equations, Linear Algebra Appl. 366 (2003), 371-402. Special issue on structured matrices: analysis, algorithms and applications (Cortona, 2000). MR 1987730, https://doi.org/10.1016/S0024-3795(02)00504-9
  • [34] David Stanford, Wayne Horn, and Guy Latouche, Tri-layered QBD processes with boundary assistance for service resources, Stoch. Models 22 (2006), no. 3, 361-382. MR 2247588, https://doi.org/10.1080/15326340600820315
  • [35] Yukio Takahashi, Kou Fujimoto, and Naoki Makimoto, Geometric decay of the steady-state probabilities in a quasi-birth-and-death process with a countable number of phases, Stoch. Models 17 (2001), no. 1, 1-24. MR 1852862, https://doi.org/10.1002/asmb.429.abs
  • [36] Evgenij E. Tyrtyshnikov, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl. 232 (1996), 1-43. MR 1366576, https://doi.org/10.1016/0024-3795(94)00025-5

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 15A16, 65F60, 15B05

Retrieve articles in all journals with MSC (2010): 15A16, 65F60, 15B05


Additional Information

Dario A. Bini
Affiliation: Dipartimento di Matematica, Università di Pisa, Largo B Pontecorvo 5, 56127 Pisa, Italy
Email: dario.bini@unipi.it

Stefano Massei
Affiliation: Scuola Normale Superiore, Cavalieri 7, 56126 Pisa, Italy
Address at time of publication: EPFL SB MATH ANCHP, CH-1015 Lausanne, Switzerland
Email: stefano.massei@epfl.ch

Beatrice Meini
Affiliation: Dipartimento di Matematica, Università di Pisa, Largo B Pontecorvo 5, 56127 Pisa, Italy
Email: beatrice.meini@unipi.it

DOI: https://doi.org/10.1090/mcom/3301
Received by editor(s): November 24, 2016
Received by editor(s) in revised form: May 26, 2017
Published electronically: January 24, 2018
Additional Notes: This work was supported by GNCS of INdAM
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society