Operator Theory: Advances and Applications, Vol. 1, 1{12 c 2007 Birkhauser Verlag Basel/Switzerland

ces using Newton iteration and tensor-displacement structure Vadim Olshevsky, Ivan Oseledets and Eugene Tyrtyshnikov Abstract. A fast approximate inversion algorithm is proposed for two-level Toeplitz matrices (block Toeplitz matrices with Toeplitz blocks). It applies to matrices that can be suciently accurately approximated by matrices of low Kronecker rank and involves a new class of tensor-displacement-rank struc-tured (TDS) matrices. The complexity depends on the prescribed accuracy and typically is o(n) for matrices of order n. Mathematics Subject Classication (2000). 15A12; 65F10; 65F15