Structure and arithmetic complexity of products and inverses of Toeplitz matrices (Q755830)

The authors derive a formula for the product of two Toeplitz matrices that is similar to the Trench formula for the inverse of a Toeplitz matrix. They then derive upper and lower bounds for the number of multiplications required to compute the inverse or the product of Toeplitz matrices and consider several special cases. The lower bounds for the general case are in agreement with earlier results. The specialized lower and all upper bounds are new. All bounds are \(O(n^ 2)\) and differ only in the lower order terms.