# Research on High-Performance Fourier Transform Algorithms Based on the NPU
## 4 Methods
### Improved Matrix Divide-and-Conquer-Based FFT Algorithm (MV-2 FFT)  
The MV-2 FFT is an NPU implementation of the FFT based on the matrix divide-and-conquer approach [31]. It first divides the input matrix into several minimum block matrices according to the parity of rows. Then, it calculates the DFT for each minimum matrix block. Finally, it iteratively applies Formula (4) via the bottom-up method to obtain the final result. The pseudo-code for the MV-2 FFT is presented in Algorithm 2. The detailed execution process can be described in the following three steps.  
First, the input image matrix data are divided into blocks of even matrices and blocks of odd matrices. The specific calculation process of the DFT result can be represented by two steps: (1) calculating the number of iterations as \(log_{2}^{N}-R\) based on the hyperparameter R and (2) using a recursive algorithm to determine the correspondence between the row numbers of the original input matrix and the smallest block matrices. Based on the results, the corresponding rows are copied into the smallest block matrices.  
Then, the DFT results of minimal blocks are calculated separately. The function FFT_1D is called to compute the DFT results for each of the smallest block matrices.  
Following this, the final transformation results are gradually computed according to Formula (4) through \(log_{2}^{N}-R\) iterations. After obtaining the DFT result matrices of the smallest block matrices, the adjacent two result matrices are substituted into Formula (4) to solve for the high-order DFT results. Repeating this process iteratively eventually yields the final Fourier Transform result of the input image.  
Finally, the results are copied to the output matrix.  
Both the MV-2 FFT algorithm and the Cooley-Tukey algorithm share the fundamental concept of matrix divide-and-conquer, but they differ in the partition details (Figure 2). These distinctions include:  
* The MV-2 FFT algorithm determines the number of iterations and the depth of the matrix partition based on the input hyperparameters. However, the Cooley-Tukey algorithm partitions the matrix to the finest granularity by default, and its iteration time is fixed for \(log_{2}^{N}\), where N is the order of the input square matrix. From an algorithm scheduling perspective, MV-2 FFT is a more streamlined approach;
* During the iterative computation, the MV-2 FFT algorithm operates on matrices, while the Cooley-Tukey algorithm performs butterfly operations on elements of row vectors. The Cooley-Tukey algorithm cannot be implemented on NPUs, as it operates on the element lever, while NPUs can operate only on data blocks. In contrast, the MV-2 FFT algorithm can fully utilize the computation power of matrix units.  
The typical approach of calculating \(D\times B\) in Algorithm 2 is calling on the gemm operator. However, this calculation can be simplified by employing vector multiplication, considering that \(D\) is a diagonal matrix. In detail, the matrix \(D=\begin{bmatrix}1&0&\cdots&0\\ 0&\omega_{N}^{1}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&\omega_{N}^{\frac{N}{2}-1}\end{bmatrix}\)  
in Formula (3) can be converted to the form \(\begin{bmatrix}1&1&\cdots&1\\ \omega_{N}^{1}&\omega_{N}^{1}&\cdots&\omega_{N}^{1}\\ \vdots&\vdots&\ddots&\vdots\\ \omega_{N}^{\frac{N}{2}-1}&\omega_{N}^{\frac{N}{2}-1}&\cdots&\omega_{N}^{ \frac{N}{2}-1}\end{bmatrix}\), which allows us to replace matrix multiplication with vector multiplication.  
Figure 2: Flowchart of the MV-2 FFT algorithm and Cooley-Tukey algorithm: (**a**) MV-2 FFT algorithm and (**b**) Cooley-Tukey algorithm.  
the operating system and applications, while one CPU was dedicated to running AI CPU operators.