We describe a new fast Fourier transform (FFT)-based algorithm to expedite matrix-vector multiplies involving multilevel block-Toeplitz (BT), or T/sub f/ /sup M/ matrices. Matrices of this class often occur in electromagnetic scattering applications because of the convolutional nature of the Green's function. Multilevel BT matrices are also associated with the autocorrelation of a 2-D discrete random process and with many problems involving symmetries based on cubic meshes. The algorithm presented here applies to multilevel BT matrices with blocks and sub-blocks which are themselves BT and in general asymmetric. The algorithm also provides for the last, M/sup th/ level sub-block to be a square, dense, not necessarily Toeplitz matrix. This method has a similar purpose to that of Goodman, Draine and Flatau (1991), but uses less memory and is more general in implementation.
展开▼
机译：我们描述了一种新的基于快速傅立叶变换（FFT）的算法，以加快涉及多级块Toeplitz（BT）或T / sub f / / sup M /矩阵的矩阵矢量乘法。由于格林函数的卷积性质，此类矩阵经常出现在电磁散射应用中。多级BT矩阵还与二维离散随机过程的自相关以及与涉及基于立方网格的对称性的许多问题有关。这里介绍的算法适用于具有块和子块的多层BT矩阵，这些块和子块本身就是BT，通常是不对称的。该算法还提供了最后一个M / sup / level子块为正方形，密集且不一定是Toeplitz矩阵。此方法的目的与Goodman，Draine和Flatau（1991）的目的类似，但使用的内存较少，实现起来更通用。
展开▼
