摘要
将Toeplitz矩阵分解为一个循环矩阵和一个下三角Toeplitz矩阵之和,以及一般卷积向循环卷积的转化,借助快速Fouier变换(FFT),导出了一种计算两个n阶Toeplitz矩阵乘积的新快速算法,其算法复杂性为2n^2+(63/4)nlog_2 n-15n-34次实乘运算,4n^2+(63/2)nlog_2 n-18n+23次实加运算,与已有的优化算法相比,在实乘次数有所降低的同时,实加次数降低了近1/3,是目前复杂性最小的一种算法。
A new fast algorithm for the product of two Toeplitz matrices is presented, based on a new decomposition of a Toeplitz matrix into a cyclic matrix and a lowtriangle Toeplitz matrix. Convolution is converted to cyclic convolution, and also FFT is employed to calculate cyclic convolution. Its arithmetic complexity is 2n^2＋63/4nlog2 n-15n-34 real multiplication and 4n^2＋63/2nlog2n-18n＋23 real addition. However, its multiplicative complexity reduces 1/3 compared to the optimized algorithm. It is a little, additive complexity reduces by nearly the algorithm that owns the lowest complexity.
出处
《数值计算与计算机应用》
CSCD
2008年第3期207-216,共10页
Journal on Numerical Methods and Computer Applications
基金
江苏省自然科学基金(BK99113)
