摘 要: | 1.引言在数学以及应用科学中的许多问题都与周期性有关,从而导致一类特殊形式的TOeelitZ系统,即r一循环线性系统的求解,其计算复杂性为O(N”)[’j或渐近复杂性O(NlogZN)p].由于循环矩阵与离散富里时变换之间的关系,我们也可通过快速富里叶变换(**n来求解r一循环线性方程组,计算复杂性降为O(NlogZN)[‘,’].事实上,到目前为止所有与厂循环矩阵有关问题的快速算法全部建立在富里叶变换某础之卜IZ,9,10,17,19,20]但另一方面富里叶交换定义在复数域上,而实际问题中的数据大多为实数,因此用FFT快速求解r…
|