摘要
利用快速傅立叶变换 (FFT) ,给出了 n阶循环矩阵开平方的一个快速算法 ,计算循环矩阵的同型平方根矩阵 (平方根矩阵也是循环矩阵 ) ,证明了同型平方根矩阵的个数为 2 n ,它是关于 n的指数函数 ;计算一个同型平方根矩阵的时间复杂性为 O(nlog2 n) ;计算全部同型平方根矩阵的时间复杂性为 O(n2 n) .
By the fast fourier Tranform (FFT), this paper presents a fast algorithm (RDCT algorithm )for radication of circulant matrix of order n computation radical similar matrices.It proves that the number of all radical similar matrices is 2\+n , which is exponential function on n ; It also proves that the computation time complexity is O(n log \-2n ) for calculating one radical similar matrix and O(n2\+n ) for calculating all radical similar matrices.
出处
《杭州师范学院学报（自然科学版）》
CAS
2003年第4期1-4,共4页
Journal of Hangzhou Teachers College(Natural Science)
基金
国家自然科学基金 (编号 99710 2 4)
浙江省自然科学基金 (编号 1990 47)资助项目
关键词
n阶循环矩阵
快速算法
开平方
同型平方根矩阵
时间复杂性
circulant matrix of order n
fast algorithm
radication
radical similar matrix
time complexity
