Structure and arithmetic complexity of products and inverses of Toeplitz matrices

We derive a formula for the product of two Toeplitz matrices that is similar to the Trench formula for the inverse of a Toeplitz matrix. We then derive upper and lower bounds for number of multiplications required to compute the inverse or the product of Toeplitz matrices and consider several special cases, e.g., symmetry, as well. The lower bounds for the general cases are in agreement with earlier results, but the specialized lower bounds and all the upper bounds are new. Both upper and lower bounds are O(n2) and differ only in lower order terms.


Published in:
Linear Algebra and its Applications, 145, 159-175
Year:
1991
Laboratories:




 Record created 2005-04-18, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)