Abstract
A 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\(\|a\|_{_{\mathcal {W}}}={\sum }_{i\in \mathbb Z}|a_{i}|\) and \(\|E\|_{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\(\|A\|_{_{\mathcal {Q}\mathcal {T}}}=\alpha {\|a\|}_{_{\mathcal {W}}}+\|E\|_{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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bean, N., Latouche, G.: Approximations to quasi-birth-and-death processes with infinite blocks. Adv. Appl. Probab. 42(4), 1102–1125 (2010)
Bini, D., Massei, S., Meini, B., Robol, L.: On Quadratic Matrix Equations with Infinite Size Coefficients Encountered in QBD Stochastic Processes. Numerical Linear Algebra Application, in press
Bini, D., Pan, V.Y: Polynomial and Matrix Computations, vol. 1. Progress in Theoretical Computer Science. Birkhäuser Boston, Inc, Boston (1994). Fundamental algorithms
Bini, D.A., Böttcher, A: Polynomial factorization through Toeplitz matrix computations. Linear Algebra Appl. 366, 25–37 (2003)
Bini, D.A., Fiorentino, G., Gemignani, L., Meini, B.: Effective fast algorithms for polynomial spectral factorization. Numer. Algorithm. 34(2-4), 217–227 (2003)
Bini, D.A., Gemignani, L., Meini, B.: Computations with infinite Toeplitz matrices and polynomials. Linear Algebra Appl. 343(/344), 21–61 (2002)
Bini, D.A., Massei, S., Meini, B.: On functions of quasi Toeplitz matrices. Sb. Math. 208(11), 56–74 (2017)
Bini, D.A., Massei, S., Meini, B.: Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes. Math. Comp. (2018)
Bini, D.A., Massei, S., Robol, L.: Efficient cyclic reduction for quasi-birth-death problems with rank structured blocks. Appl. Numer Math. 116, 37–46 (2017)
Bini, D.A., Massei, S., Robol, L.: On the decay of the off-diagonal singular values in cyclic reduction. Linear Algebra Appl. 519, 27–53 (2017)
Bini, D.A., Meini, B.: Effective methods for solving banded Toeplitz systems. SIAM J. Matrix Anal. Appl. 20(3), 700–719 (1999)
Bini, D.A., Meini, B.: The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond. Numer. Algorithm. 51(1), 23–60 (2009)
Bini, D.A., Meini, B.: On the exponential of semi-infinite quasi-Toeplitz matrices. arXiv:1611.06380 (2016)
Böttcher, A., Grudsky, SM: Spectral properties of banded Toeplitz matrices. SIAM, PA (2005)
Böttcher, A., Halwass, M.: A Newton method for canonical Wiener-Hopf and spectral factorization of matrix polynomials. Electron. J. Linear Algebra 26, 873–897 (2013)
Böttcher, A., Halwass, M.: Wiener-Hopf and spectral factorization of real polynomials by Newton’s method. Linear Algebra Appl. 438(12), 4760–4805 (2013)
Böttcher, A., Silbermann, B: Introduction to Large Truncated Toeplitz Matrices. Springer Science & Business Media, Berlin (2012)
Gohberg, I.C.: On an application of the theory of normed rings to singular integral equations. Uspehi Matem. Nauk. (N.S.) 7(2(48)), 149–156 (1952)
Gutiérrez-Gutiérrez, J, Crespo, P.M., Böttcher, A: Functions of the banded Hermitian block Toeplitz matrices in signal processing. Linear Algebra Appl. 422(2-3), 788–807 (2007)
Halko, N., Martinsson, P.-G., Tropp, J.A.: Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2011)
Higham, N.J.: Functions of matrices: theory and computation. SIAM, PA (2008)
Jackson, J.R.: Networks of waiting lines. Oper. Res. 5(4), 518–521 (1957)
Kapodistria, S., Palmowski, Z.: Matrix geometric approach for random walks. Stability condition and equilibrium distribution. Stoch. Model. 33(4), 572–597 (2017)
Kobayashi, M., Miyazawa, M.: Revisiting the tail asymptotics of the double QBD process: refinement and complete solutions for the coordinate and diagonal directions. In: Matrix-Analytic Methods in Stochastic Models, Volume 27 of Springer Proc. Math. Stat., pp. 145–185. Springer, New York (2013)
Kressner, D., Luce, R.: Fast computation of the matrix exponential for a Toeplitz matrix. SIAM J. Matrix Anal. Appl. 39(1), 23–47 (2018)
Latouche, G., Nguyen, G.T., Taylor, P.G.: Queues with boundary assistance: the effects of truncation. Queueing Syst. 69(2), 175–197 (2011)
Latouche, G., Ramaswami, V.: Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM Series on Statistics and Applied Probability. SIAM Philadelphia, PA (1999)
Latouche, G., Taylor, P.: Truncation and augmentation of level-independent QBD processes. Stoch. Process. Appl. 99(1), 53–80 (2002)
Lee, S.T., Pang, H.-K., Sun, H.-W.: Shift-invert ARnoldi approximation to the Toeplitz matrix exponential. SIAM J. Sci. Comput. 32(2), 774–792 (2010)
Lindner, M.: Infinite Matrices and Their Finite Sections. Frontiers in Mathematics. Birkhäuser Verlag, Basel (2006). An introduction to the limit operator method
Miyazawa, M.: Light tail asymptotics in multidimensional reflecting processes for queueing networks. Top 19(2), 233–299 (2011)
Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Courier Dover Publications, USA (1981)
Paige, C.C.: Bidiagonalization of matrices and solutions of the linear equations. SIAM J. Numer. Anal. 11, 197–209 (1974)
Widom, H.: Asymptotic behavior of block Toeplitz matrices and determinants. II Adv. Math. 21(1), 1–29 (1976)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work has been supported by the GNCS/INdAM project 2018 “Tecniche innovative per problemi di algebra lineare”. The authors are members of the research group GNCS.
Appendix
Appendix
Here, we report the main algorithms that we have implemented to perform inversion of QT matrices, namely, the Sieveking-Kung algorithm [3] for inverting triangular Toepliz matrices (or power series), and an algorithm based on cyclic reduction [12] to compute the Wiener-Hopf factorization of a symbol \(a(z)\). We also provide a general view of the available algorithms for the Wiener-Hopf factorization [4, 5, 16], with an outline of their relevant computational properties. Choosing the more convenient algorithm for this factorization depends on several aspects like the degree of a(z), and the location of its zeros, and this is an issue to be better understood.
1.1 A.1 The Sieveking-Kung algorithm
We shortly recall the Sieveking-Kung algorithm for computing the first \(k + 1\) coefficients \(v_{0},\ldots ,v_{k}\) of \(v(z)={\sum }_{i = 0}^{\infty }v_{i}z^{i}\) such that \(v(z)u(z)= 1\), or equivalently, the first k entries in the first row of T(u)− 1. For more details, we refer the reader to the book [3].
For notational simplicity, denote \(V_{q}\) the \(q\times q\) leading submatrix of \(T(u)\). Consider \(V_{2q}\) and partition it into four square blocks of size q:
so that
Since the inverse of an upper triangular Toeplitz matrix is still upper triangular and Toeplitz, it is sufficient to compute the first row of \(V_{2q}^{-1}\). The first half clearly coincides with the first row of \(V_{q}^{-1}\), and the second half is given by \(-{e_{1}^{T}} V_{q}^{-1}S_{q} V_{q}^{-1},\) where \(e_{i}\) is the vector with the i-th component equal to 1 and with the remaining components equal to zero.
Thus, the algorithm works this way: for a given (small) q, compute the first q components by solving the system \({V_{q}^{T}} x=e_{1}\). Then, by subsequent doubling steps, compute \(2q\), \(4q\), \(8q,\ldots \), components until some stop condition is satisfied. Observe that, denoting \(v_{q}(z)\) the polynomial obtained at step q, the residual error \(r_{q}(z)=a(z)v_{q}(z)-1\) can be easily computed so that the stop condition \({\|r_{q}\|}_{_{\mathcal {W}}}\le \epsilon {\|a\|}_{_{\mathcal {W}}}\) can be immediately implemented. Concerning the convergence speed, it must be pointed out that the equation \(r_{2q}(z)=r_{q}(z)^{2}\) holds true (see [3]), implying that the convergence to zero of the norm of the residual error is quadratic.
This approach has a low computational cost since the products Toeplitz matrix by vector can be implemented by means of FFT for an overall cost of the Sieveking-Kung algorithm of \(O(n\log n)\) arithmetic operations.
This algorithm, here described in matrix form, can be equivalently rephrased in terms of polynomials and power series.
1.2 A.2 The Wiener-Hopf factorization
We recall and synthesize the available algorithms for computing the coefficients of the polynomials \(u(z)\) and \(l(z)\) such that a(z) = u(z)l(z− 1) is the Wiener-Hopf factorization of \(a(z)\). Denote \(\xi _{i}\) the zeros of \(a(z)\) ordered so that |ξi|≤|ξi+ 1|. This way, \(|\xi _{n_{+}}|<1<|\xi _{1+n_{+}}|\); moreover, \(u(\xi _{i})= 0\) for \(i = 1,\ldots ,n_{+}\) while \(l(\xi _{i}^{-1})= 0\) for \(i=n_{+}+ 1,\ldots ,n_{+}+n_{-}\).
A first approach is based on reducing the problem to solving a quadratic matrix equation. Let \(p\ge \max (n_{-},n_{+})\), reblock the matrices in the equation \(T(a)=T(u)T(l^{-1})\) into \(p\times p\) blocks and obtain
where, by using the MATLAB notation,
and \(a_{i}= 0\) if i is out of range.
Set \(W=U_{0}L_{0}\), \(R=-U_{1}U_{0}^{-1}\), \(G=-L_{0}^{-1}L_{1}\) and get the factorization
Multiplying the above equation to the right by the block column vector with entries \(I,G,G^{2},G^{3},\ldots \) or multiplying to the left by the block row vector with entries \(I, R,R^{2},R^{3},\ldots \) one finds that the matrices R and G are solutions of the equations
and have eigenvalues \(\xi _{1},\ldots ,\xi _{n_{+}}\) and \(\xi _{n_{+} + 1}^{-1},\ldots ,\xi _{n_{+}+n_{-}}^{-1}\), respectively, so that they have spectral radius less than 1. For more details in this regard, we refer the reader to [6].
Observe that, since
then \(Ge_{p-n_{-}+ 1}=-l_{n_{-}} L_{0}^{-1}e_{1}\), while \({e_{1}^{T}}G=-l_{0}^{-1}(l_{p},\ldots ,l_{1})\). That is, the first row of G provides the coefficients of the factor \(l(z)\) normalized so that l0 = − 1. Similarly, one finds that \(Re_{1}=-u_{0}^{-1}(u_{p},u_{p-1},\ldots ,u_{1})^{T}\), and \(e_{p-n_{+}+ 1}^{T}R=-u_{n_{+}} {e_{1}^{T}}U_{0}^{-1}\). That is, the first column of R provides the coefficients of the factor \(u(x)\) normalized so that \(u_{0}=-1\). In order to determine the normalizing constant w such that a(z) = u(z)wl(z− 1), it is sufficient to impose the condition \( u_{n_{+}} w l_{0}=a_{n_{+}}\) so that we can choose \(w=-a_{n_{+}}/u_{n_{+}}\).
This argument provides the following algorithm to compute the coefficients of \(l(x)\) and of \(u(x)\) such that a(z) = u(z)wl(1/z), where \(u_{0}=l_{0}=-1\):
-
1.
Assemble the matrices \(A_{-1}, A_{0}, A_{1}\).
-
2.
Determine R and G that solve (1) using cyclic reduction.
-
3.
Compute \(\hat u=Re_{1}\), set \(u=(-1,\hat u_{p},\ldots ,\hat u_{1})\) and \(\hat v={e_{1}^{T}}G\), set \(l=(-1,\hat v_{p},\ldots , \hat v_{1})\).
-
4.
Set \(w=-a_{n_{+}}/u_{n_{+}}\)
Observe that the above algorithm can be easily modified in order to compute, for a given q, the first q coefficients of the triangular Toeplitz matrices \(\mathcal U^{-1}\) ad \(\mathcal L^{-1}\) such that
In fact, the first p coefficients are given by
While the remaining coefficients can be computed by means of the Sieveking-Kung algorithm described in the previous section.
The method described in this section requires the computation of the solutions G and R of (1). One of the most effective methods to perform this computation is the cyclic reduction (CR) algorithm. We refer the reader to [12] for a review of this method and to [11] for the analysis of the specific structural and computational properties of the matrices generated in this way. Here, we provide a short outline of the algorithm, applied to the (1) which we rewrite in the form \(AG^{2}+BG+C = 0\) and \(R^{2}C+RB+A = 0\), respectively. The algorithm CR computes the following matrix sequences:
It is proved that under mild conditions, the sequences can be computed with no breakdown and that \(\lim _{k} -A(\widehat B^{k)})^{-1} =R\), \(\lim _{k}-\widetilde (B^{(k)})^{-1}C=G\). More precisely, the following relations hold
and it can be proved that \(\|(\widehat B^{(k)})^{-1}\|\) and \(\|(\widetilde B^{(k)})^{-1}\|\) are uniformly bounded by a constant and that A(k), \(C^{(k)}\) converge double exponentially to zero. Since the spectral radii of R and of G are less than 1, this fact implies that convergence is quadratic. Moreover, the approximation errors given by the matrices \( (\widetilde B^{(k)})^{-1} A^{(k)}G^{2^{k}}\) and \( R^{2^{k}}C^{(k)}(\widehat B^{(k)})^{-1}\) are explicitly known in a first-order error analysis. In fact, the matrices \( (\widetilde B^{(k)})^{-1}\), \((\widehat B^{(k)})^{-1}\), \(A^{(k)}\), and \(C^{(k)}\) are explicitly computed by the algorithm and G is approximated. This fact allows us to implement effectively the Wiener-Hopf computation required in the inversion procedure described in Algorithm 1 of Section ??.
The cost of cyclic reduction is \(O(p^{3})\) arithmetic operations per step. In [11], it is shown that all the above matrix sequences are formed by matrices having displacement rank bounded by small constants. This fact enables one to implement the above equation with a linear cost, up to logarithmic factors, by means of FFT.
1.2.1 A.2.1 A different approach
Another approach to compute the factor l and u relies on the following property [4].
Theorem A.1
Let\(a(z)^{-1}=h(z)={\sum }_{i=-\infty }^{\infty }h_{i}z^{i}\). Define the Toeplitz matrix of size\(q\ge \max (m,n)\)Tq = (hj−i).Then,\(T_{q}\)isinvertible and its last row and column define the coefficient vectorsof\(l(z)\)and\(u(z)\), respectively up to a normalization constant.
Proof
The relation \(a(z)^{-1}=l^{-1}(z^{-1})u^{-1}(z)\) can be rewritten in matrix form as
Multiply to the right by the infinite vector obtained by completing (l0,…,lq− 1) with zeros. Since the product of \(T(l^{-1})^{T}\) with the latter is a vector with all null components except the first one, equal to 1, considering q components of the result yields
whence we deduce that \((l_{0},\ldots ,l_{q-1})^{T}=T_{q}(h)^{-1}u_{0}^{-1}e_{q}\). Similarly, we do for the last row. □
This property is at the basis of the following computations:
-
1.
Set \(q=\max (m,n)\) compute \(h_{i}\) for \(i=-q,q\) such that \(h(z)a(z)= 1\) by means of evaluation/interpolation.
-
2.
Form \(T_{q}(h)=(h_{j-i})_{i,j = 1,q}\) and compute last row and last column of \(T_{q}(h)^{-1}\).
This algorithm may require a large number of interpolation points when a(z) has some zero of modulus close to 1, in the process of evaluation/interpolation.
1.2.2 A.2.2 Yet another approach
The same property provides a third algorithm for computing \(l(z)\) and \(u(z)\) which relies on a different computation of \(h_{i}\), i = −q,…,q. The idea is described below
Consider the equation
Multiply it by \(a(-z)\) and, since \(a(-z)a(z)=a_{1}(z^{2})\), for a polynomial \(a_{1}(z)\), get
Repeating the procedure k times yields
If \(a(z)\) has roots of modulus different from 1, then \(a_{k}(z)\) quickly converges to either a constant or a scalar multiple of z, since its zeros are the \(2^{k}\) powers of the zeros of \(a(z)\). In this case, \(h(z)\) can be computed by means of a product of polynomials with the same degree (independent of the iterations).
1.2.3 A.2.3 Newton’s iteration
Newton’s iteration can be applied to the nonlinear system a(z) = u(z)l(z− 1) where the unknowns are the coefficients of the polynomials \(u(z)\) and \(l(z)\). The Jacobian matrix has a particular structure given in terms of displacement rank which can be exploited to implement Newton’s iteration at a low cost. Details in this regard are given in the papers [16] and [15].
Rights and permissions
About this article
Cite this article
Bini, D.A., Massei, S. & Robol, L. Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox. Numer Algor 81, 741–769 (2019). https://doi.org/10.1007/s11075-018-0571-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-018-0571-6