We describe a new fast Fourier transform (FFT)-based algorithm to expedite matrix-vector multiplies involving multilevel block-Toeplitz (BT), or T{sup}M{sub}f, 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 sob-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, but uses less memory sod is more general in implementation.
展开▼