A fast algorithm for block Toeplitz systems with tensor structure

摘要

We study the solution of block Toeplitz system Tx = b by the preconditioned conjugate gradient (PCG) method where T = T(1) ⊗ T(2) ⊗ … ⊗ T(m) and T(i), i = 1, 2, …, m, are n × n Toeplitz matrices. The preconditioner C̃ is a matrix that preserves the tensor structure of T and is close to T in Frobenius norm. With a fast algorithm, we show that C̃ is a good preconditioner for solving block Toeplitz systems with tensor structure. Only O(mnm log n) operations are required for the solution of the preconditioned systems. An application is given here.