GPU上循环矩阵的快速求逆算法

A Quick Method for Inversing a Circulant Matrix on GPU

循环矩阵是一种特殊类型的Toeplitz矩阵,在很多专业领域尤其是图像和数字信号处理中有广泛的应用。计算其逆矩阵的快速算法由三个步骤组成:(1)使用离散傅立叶变换将矩阵的第一行元素转换到频率空间;(2)计算转换后的频谱中每个幅度的倒数;(3)在调整过的频谱上施加傅立叶反变换,获得逆矩阵的第一行元素,从而构建原始循环矩阵的逆矩阵。此算法的特点是每个数据元素的计算过程完全相同,同时独立于其它元素的计算,因而非常适合在GPU上运行。本文在GPU上实现了上述循环矩阵求逆的快速算法,将其转换为一个正方形的图形绘制。实验结果表明,该算法在GPU上的运行速度比在CPU上提高了大约10倍。

Circulant matrix is a special case of the Toeplitz matrix,which is widely used in many domains of specialization,especially in image and digtial signal processing.Calculating the inverse of this category of matrices consists of the following three steps：（1） transform the first row vector to frequency space by using DFT;（2） calculate the inverse of each amplitude in the spectrum;（3） apply IDFT to the adjusted spectrum to acquire the first row of the inverse matrix,and finally reconstruct it.In this algorithm,the computational process involving each matrix element is entirely identical,and independent of the process of any other element,therefore,it adequately adapts to the modern GPU.This paper implements such a fast algorithm on the GPU,which is transferred to rendering a square.The experimental results prove that the GPU version is ten times faster than the CPU one.