MATHICSE Technical Report : Quasi-Toeplitz matrix arithmetic : a Matlab toolbox

A Quasi Toeplitz (QT) matrix is a semi-infinite matrix of the kind $A = T(a) + E$ where$T(a) = (aj-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|_j$ 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{QT}} = \alpha\|a\|_{\mathcal{W}} + \|E\|_{2}, for$\alpha \geq (1 + \sqrt{5})/2$,are a Banach algebra with the standard arithmetic operations. We provide an algorithmicdescription of these operations on the finite parametrization of QT-matrices, and we developa MATLAB toolbox implementing them in a transparent way. The toolbox is then extended toperform arithmetic operations on matrices of finite size that have a Toeplitz plus low-rankstructure. This enables the development of algorithms for Toeplitz and quasi-Toeplitz matriceswhose cost does not necessarily increase with the dimension of the problem.Some examples of applications to computing matrix functions and to solving matrix equa-tions are presented, and confirm the effectiveness of the approach.