Block-Toeplitz structure and FFT acceleration

A square matrix Q of size N x N is called Toeplitz matrix of order N if Qij = Bi-j, i.e. matrix elements on any line parallel to the main diagonal are the same [52], 

In a block-Toeplitz (BT) matrix (of order Nt) elements B, are not numbers, but square matrices of size / x / themselves  

The major practical application of the BT structure is acceleration of matrix-vector product, which is the computational bottleneck of any Krylov-subspace iterative method. Goodman et al. [75] showed that multiplication of 3 level BT matrix G by a vector can be transformed into a discrete convolution  

Both G and x are then regarded as periodic in each dimension fx with period 2n. A discrete convolution can be transformed by FFT to an element-wise product of two vectors, which is easily computed in 0 N) operations. It requires evaluation of a direct and inverse FFT for each matrix-vector product. Each of them is a 3D FFT of 

---