Abstract:

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.

Key words: circulant matrix;DFT;GPU;GLSL