Tyrtyshnikov, Tensor properties of multilevel Toeplitz and related matrices, Linear Algebra

A general proposal is presented for fast algorithms for multilevel structured ma-trices. It is based on investigation of their tensor properties and develops the idea recently introduced by J. Kamm and J. G. Nagy in the block Toeplitz case. We show that tensor properties of multilevel Toeplitz matrices are related to separa-tion of variables in the corresponding symbol, present analytical tools to study the latter, expose truncation algorithms preserving the structure, and report on some numerical results confirming advantages of the proposal. AMS classification: 15A12; 65F10; 65F1