# A Sparse Algorithm for Computing the DFT Using Its Real Eigenvectors
## 7 Number of Operations  
### Using Generalized Eigenvectors  
At first glance while observing (8), computing \(\tilde{X}\) seems to need \(N\) multiplications and \(N-1\) additions assuming that \(x\in\mathbb{R}^{N}\). However, as briefly discussed in Section 3, it is known that all the eigenvectors of the DFT are either even or odd symmetric sequences [8]. Eigenvectors corresponding to eigenvalues \(1\) or \(-1\) will be even symmetric, and eigenvectors corresponding to eigenvalues \(j\) or \(-j\) will be odd symmetric. Using this property, if an eigenvector \(v_{k}\) is even symmetric, \(\langle v_{k},x\rangle\) in (16) can be computed using \(\lfloor N/2\rfloor+1\) real multiplications and \(N-1\) real additions. If \(v_{k}\) is an odd symmetric eigenvector, the inner product requires \(\lfloor N/2\rfloor\) real multiplications and \(N-2\) real additions because the first element of \(v_{k}\) will be \(0\) in this case. For example, consider an even eigenvector of a 5-point DFT \(v_{ev}=\left[ \begin{array}{cccccc}a_{0}&a_{1}&a_{2}&a_{2}&a_{1}\end{array}  \right]^{\text{T}}\). For an input vector \(x=\left[ \begin{array}{cccccc}x_{0}&x_{1}&x_{2}&x_{3}&x_{4}\end{array}  \right]^{\text{T}}\),  
\[\langle v_{ev},x\rangle =a_{0}x_{0}+a_{1}x_{1}+a_{2}x_{2}+a_{2}x_{3}+a_{1}x_{4}\] \[=a_{0}x_{0}+a_{1}(x_{1}+x_{4})+a_{2}(x_{2}+x_{3}) \tag{24}\]  
The first line requires five multiplications, and the second line requires three multiplications. The number of additions in both cases is 5. Now consider an odd eigenvector of a 5-point DFT \(v_{od}=\left[ \begin{array}{cccccc}0&b_{1}&b_{2}&-b_{2}&-b_{1}\end{array}  \right]^{\text{T}}\). \[\langle v_{od},x\rangle =0+b_{1}x_{1}+b_{2}x_{2}-b_{2}x_{3}-b_{1}x_{4}\] \[=b_{1}(x_{1}-x_{4})+b_{2}(x_{2}-x_{3}) \tag{25}\]  
Here using the symmetry, there are two multiplications and three additions. Similar relationships can be found for even length sequences. We know that the number of even or odd eigenvectors depends on the eigenvalue multiplicity (which in turn depends on \(N\)). The number of even eigenvectors is  
Figure 3: Plot showing the mean square error while computing the IDFT(DFT(\(x\))) using the proposed method. The eigenvectors were calculated using the Matveev method and the Gram–Schmidt method. Since the plot shows the error after the forward and inverse computation, the error in just one of the directions will be slightly less than what is shown here. Note that this error is caused due to the limitations on the machine that was used to calculate the eigenvectors. In practice, the eigenvectors can be pre-computed with high enough precision to eliminate the error shown in this plot. and the number of odd eigenvectors is \(m_{j}+m_{-j}\). Thus, for computing \(\hat{X}\) in (16) the total number of multiplications \(\Xi_{\hat{X}}(N)\) and number of additions \(\Phi_{\hat{X}}(N)\) required are  
\[\Xi_{\hat{X}}(N)=\left(\left\lfloor\frac{N}{2}\right\rfloor+1\right)(m_{1}+m_{- 1})+\left\lfloor\frac{N}{2}\right\rfloor(m_{j}+m_{-j})\]  
\[\Phi_{\hat{X}}(N)=(N-1)(m_{1}+m_{-1})+(N-2)\left(m_{j}+m_{-j}\right)\]  
For large values of \(N\) the eigenvalue multiplicities can be approximated to be equal to each other (which in turn approximately equals \(N/4\)). Thus, \(m_{1}\approx m_{-1}\approx m_{j}\approx m_{-j}\approx N/4\). Therefore for large \(N\),  
\[\Xi_{\hat{X}}(N)\approx\frac{N^{2}}{2}\]  
\[\Phi_{\hat{X}}(N)\approx\frac{N}{2}(2N-3)\approx N^{2}\]  
While multiplying the eigenvector matrix with \(\hat{X}\) in (4) and (8) the eigenvector symmetry can be utilized again. Let \(W=V\hat{X}\). Let the number of multiplications required for computing \(V\hat{X}\) be \(\Xi_{W}(N)\) and the number of additions be \(\Phi_{W}(N)\). So, \(\Xi_{W}(N)=\Xi_{\hat{X}}(N)\) due to the symmetry of the eigenvectors in \(V\). As noted before, the operation \(V\hat{X}\) just changes the magnitude of each eigenvector. Therefore, the columns of \(W\) retain the even or odd symmetries of the eigenvectors.