A fast algorithm for block Toeplitz systems with tensor structure (Q1908238)

Consider a block Toeplitz system \(Tx= b\) with \(T= T_1\otimes T_2\otimes\cdots\otimes T_m\), where the \(T_i\) are \(n\times n\) Toeplitz matrices. To solve this system of size \(n^m\) by the preconditioned conjugate gradient method, a tensor product circulant preconditioner \(C= C_1\otimes C_2\otimes\cdots\otimes C_m\) is used, where \(C_i\) is the Chan preconditioner for \(T_i\). This means that \(C_i\) minimizes the Frobenius distance to \(T_i\) among the circulant matrices. To solve the preconditioned system, a sequence of \(m\) simplified systems of the form \((I_n\otimes\cdots\otimes I_n\otimes C^{-1}_k T_k\otimes I_n\otimes\cdots \otimes I_n) y_{k- 1}= y_k\) have to be solved. This can be done in \(O(mn^m\log n)\) operations, which is a fast algorithm. As an application of this kind of systems, an inverse heat problem in \(\mathbb{R}^m\) is described. No numerical results are included.