Iterative inversion of structured matrices (Q598225)

A class of matrices is said to be displacement structured with respect to a fixed matrix operator \(\nabla\) if \(\nabla (A)\) has low rank for any matrix \(A\) in this class. One of the most prominent examples are Toeplitz matrices, for which rank(\(\nabla(A))\leq 2\) with, e.g., \(\nabla(A) = ZA-AZ\) where the entries of \(Z\) are ones on the first subdiagonal and zeros everywhere else. Under certain conditions on \(\nabla\), the matrix \(A\) can be completely represented in terms of (typically skinny) matrices \(F\) and \(G\) satisfying \(\nabla(A) = FG^T\); in this case \(F\) and \(G\) are called generators for \(A\). Displacement structured matrices admit more efficient algorithms for several linear algebra operations including matrix inversion, matrix-vector multiplication and the (least-squares) solution of linear systems of equations. This paper is concerned with efficient variants of Newton-based iterations for matrix inversion such as \(X_{i+1} = X_i (2I + AX_i)\), which converges locally quadratic to \(-A^{-1}\). This iteration preserves displacement structured matrices in the sense that if the rank of \(\nabla (X_i)\) is \(k\) then the rank of \(\nabla (X_{i+1})\) is at most \(3k\). This allows to rewrite the iteration in terms of generators for the iterates. The use of such an approach is somewhat limited by the fact that the displacement rank may grow exponentially with the number of iterations. To overcome this limitation, this paper describes three different compression strategies to restrict the rank growth. Numerical examples demonstrate that a compression strategy based on a certain least-squares criterion is very effective for randomly generated Toeplitz matrices.