Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox
Bini D. A., Massei S., Robol L.
Banach algebra Wiener algebra Mathematics - Numerical Analysis FOS: Mathematics Toeplitz matrices Infinite matrices Applied Mathematics Numerical Analysis (math.NA) MATLAB
Quasi Toeplitz (QT) matrix is a semi-infinite matrix of the kind $A=T(a)+E$ where $T(a)=(a_{j-i})_{i,j\in\mathbb Z^+}$, $E=(e_{i,j})_{i,j\in\mathbb Z^+}$ is compact and the norms $\lVert a\rVert_{\mathcal W} = \sum_{i\in\mathbb Z}|a_i|$ and $\lVert E \rVert_2$ are finite. These properties allow to approximate any QT-matrix, within any given precision, by means of a finite number of parameters. QT-matrices, equipped with the norm $\lVert A \rVert_{\mathcal QT}=\alpha\lVert a\rVert_{\mathcal{W}} \lVert E \rVert_2$, for $\alpha = (1+\sqrt 5)/2$, are a Banach algebra with the standard arithmetic operations. We provide an algorithmic description of these operations on the finite parametrization of QT-matrices, and we develop a MATLAB toolbox implementing them in a transparent way. The toolbox is then extended to perform arithmetic operations on matrices of finite size that have a Toeplitz plus low-rank structure. This enables the development of algorithms for Toeplitz and quasi-Toeplitz matrices whose cost does not necessarily increase with the dimension of the problem. Some examples of applications to computing matrix functions and to solving matrix equations are presented, and confirm the effectiveness of the approach.
Source: Numerical algorithms 81 (2019): 741–769. doi:10.1007/s11075-018-0571-6
Publisher: Baltzer Science Publishers, Bussum ;, Paesi Bassi
[2] D. Bini, S. Massei, B. Meini, and L. Robol. On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes. Numer. Linear Algebra Appl., in press.
[3] D. Bini and V. Y. Pan. Polynomial and matrix computations. Vol. 1. Progress in Theoretical Computer Science. Birkh¨auser Boston, Inc., Boston, MA, 1994. Fundamental algorithms.
[4] D. A. Bini and A. B¨ottcher. Polynomial factorization through Toeplitz matrix computations. Linear Algebra Appl., 366:25-37, 2003.
[5] D. A. Bini, G. Fiorentino, L. Gemignani, and B. Meini. Effective fast algorithms for polynomial spectral factorization. Numer. Algorithms, 34(2-4):217-227, 2003.
[6] D. A. Bini, L. Gemignani, and B. Meini. Computations with infinite Toeplitz matrices and polynomials. Linear Algebra Appl., 343/344:21-61, 2002.
[7] D. A. Bini, S. Massei, and B. Meini. On functions of quasi Toeplitz matrices. Sb. Math., 208(11):56-74, 2017.
[8] D. A. Bini, S. Massei, and B. Meini. Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes. Mathematics of Computation, 2017. Accepted for publication, arXiv:1611.06337.
[9] D. A. Bini, S. Massei, and L. Robol. Efficient cyclic reduction for quasi-birth-death problems with rank structured blocks. Appl. Numer. Math., 116:37-46, 2017.
[10] D. A. Bini, S. Massei, and L. Robol. On the decay of the off-diagonal singular values in cyclic reduction. Linear Algebra Appl., 519:27-53, 2017.
[11] D. A. Bini and B. Meini. Effective methods for solving banded Toeplitz systems. SIAM J. Matrix Anal. Appl., 20(3):700-719, 1999.
[12] D. A. Bini and B. Meini. The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond. Numer. Algorithms, 51(1):23-60, 2009.
[13] D. A. Bini and B. Meini. On the exponential of semi-infinite quasi-toeplitz matrices. arXiv preprint arXiv:1611.06380, 2016.
[14] A. B¨ottcher and S. M. Grudsky. Spectral properties of banded Toeplitz matrices. Siam, 2005.
[15] A. B¨ottcher and M. Halwass. A Newton method for canonical Wiener-Hopf and spectral factorization of matrix polynomials. Electron. J. Linear Algebra, 26:873-897, 2013.
[16] A. B¨ottcher and M. Halwass. Wiener-Hopf and spectral factorization of real polynomials by Newton's method. Linear Algebra Appl., 438(12):4760-4805, 2013.
[17] A. B¨ottcher and B. Silbermann. Introduction to large truncated Toeplitz matrices. Springer Science & Business Media, 2012.
[18] I. C. Gohberg. On an application of the theory of normed rings to singular integral equations. Uspehi Matem. Nauk (N.S.), 7(2(48)):149-156, 1952.
[19] J. Guti´errez-Guti´errez, P. M. Crespo, and A. B¨ottcher. Functions of the banded Hermitian block Toeplitz matrices in signal processing. Linear Algebra Appl., 422(2-3):788-807, 2007.
[20] N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev., 53(2):217-288, 2011.
[21] N. J. Higham. Functions of matrices: theory and computation. SIAM, 2008.
[22] J. R. Jackson. Networks of waiting lines. Oper. Res., 5(4):518-521, 1957.
[23] S. Kapodistria and Z. Palmowski. Matrix geometric approach for random walks: Stability condition and equilibrium distribution. Stoch. Models, 33(4):572-597, 2017.
[24] M. Kobayashi and M. Miyazawa. Revisiting the tail asymptotics of the double QBD process: refinement and complete solutions for the coordinate and diagonal directions. In Matrixanalytic methods in stochastic models, volume 27 of Springer Proc. Math. Stat., pages 145-185. Springer, New York, 2013.
[25] D. Kressner and R. Luce. Fast Computation of the Matrix Exponential for a Toeplitz Matrix. SIAM J. Matrix Anal. Appl., 39(1):23-47, 2018.
[26] G. Latouche, G. T. Nguyen, and P. G. Taylor. Queues with boundary assistance: the effects of truncation. Queueing Syst., 69(2):175-197, 2011.
[27] G. Latouche and V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM Series on Statistics and Applied Probability. SIAM, Philadelphia PA, 1999.
[28] G. Latouche and P. Taylor. Truncation and augmentation of level-independent QBD processes. Stochastic Process. Appl., 99(1):53-80, 2002.
[29] S. T. Lee, H.-K. Pang, and H.-W. Sun. Shift-invert Arnoldi approximation to the Toeplitz matrix exponential. SIAM J. Sci. Comput., 32(2):774-792, 2010.
[30] M. Lindner. Infinite matrices and their finite sections. Frontiers in Mathematics. Birkh¨auser Verlag, Basel, 2006. An introduction to the limit operator method.
[31] M. Miyazawa. Light tail asymptotics in multidimensional reflecting processes for queueing networks. Top, 19(2):233-299, 2011.
[32] M. F. Neuts. Matrix-geometric solutions in stochastic models: an algorithmic approac h. Courier Dover Publications, 1981.
[33] C. C. Paige. Bidiagonalization of matrices and solutions of the linear equations. SIAM J. Numer. Anal., 11:197-209, 1974.
[34] H. Widom. Asymptotic behavior of block Toeplitz matrices and determinants. II. Advances in Math., 21(1):1-29, 1976.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:389395,
title = {Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox},
author = {Bini D. A. and Massei S. and Robol L.},
publisher = {Baltzer Science Publishers, Bussum ;, Paesi Bassi},
doi = {10.1007/s11075-018-0571-6 and 10.48550/arxiv.1801.08158},
journal = {Numerical algorithms},
volume = {81},
pages = {741–769},
year = {2019}
}
0000-0002-6545-1748
