A note on the fast algorithm for block Toeplitz systems with tensor structure

摘要

We study the solutions of block Toeplitz systems Tmnx=b by using the preconditioned conjugate gradient (PCG) method. Here Tmn=Tm⊗Tn and Ti,i=m,n are Toeplitz matrices. In [X. Jin, Appl. Math. Comput. 73 (1995) 115–124], Jin introduced a fast algorithm for these systems by applying the PCG method. This fast algorithm allows a tensor problem to be reduced to a one-dimensional problem. It was proved that if the mn-by-mn system is well conditioned, then the PCG method converges superlinearly and only O(mnlogmn) operations are required in solving the preconditioned system. However, only well-conditioned systems were considered in Jin, 1995. In this paper, we apply this fast algorithm with the {ω}-circulant preconditioners proposed in [D. Potts, G. Steidl, Preconditioners for Ill-Conditioned toeplitz matrices, BIT, to be appeared] to solve the ill-conditioned systems. Numerical results are included to illustrate the effectiveness of the algorithm for solving the preconditioned systems by using the PCG method. An application in image restoration is also given.