# A Sparse Algorithm for Computing the DFT Using Its Real Eigenvectors
## 7 Number of Operations
### Using the Sparsity of the Eigenvectors
#### 7.2.3 Zeros in Eigenvectors of Even Length  
The middle element of the eigenvectors corresponding to the eigenvalues \(\pm j\) are zero, if the eigenvectors are of even length. Thus, if \(N\) is the length of the eigenvector, then the \((N/2+1)^{\rm th}\) element will be \(0\) if \(N\) is even. For example, \(v=\left[\begin{array}{cccccccc}0&a_{1}&a_{2}&0&-a_{2}&-a_{1}\end{array}\right]\) is a possible configuration of such an eigenvector. Note that in this example, the first element is \(0\) because the vector is odd symmetric.  
Using this new information the number of multiplications \(\Xi_{\tilde{X}}(N)\) and additions \(\Phi_{\tilde{X}}(N)\) required for calculating \(\tilde{X}\) is  
\[\Xi_{\tilde{X}}(N) =(m_{1}-1)\bigg{(}\left\lfloor\frac{N}{2}\right\rfloor-\frac{m_{ 1}-2}{2}\bigg{)}+2\] \[\quad+(m_{-1}-1)\bigg{(}\left\lfloor\frac{N}{2}\right\rfloor- \frac{m_{-1}-2}{2}\bigg{)}+2\] \[\quad+m_{j}\bigg{(}\left\lfloor\frac{N-1}{2}\right\rfloor-\frac {m_{j}-1}{2}\bigg{)}\] \[\quad+m_{-j}\bigg{(}\left\lfloor\frac{N-1}{2}\right\rfloor-\frac {m_{-j}-1}{2}\bigg{)} \tag{30}\]  
\[\Phi_{\tilde{X}}(N) =m_{1}N-m_{1}(m_{1}-1)-1\] \[\quad+m_{-1}N-m_{-1}(m_{-1}-1)-1\] \[\quad+2m_{j}\left\lfloor\frac{N-1}{2}\right\rfloor-m_{j}^{2}\] \[\quad+2m_{-j}\left\lfloor\frac{N-1}{2}\right\rfloor-m_{-j}^{2} \tag{31}\]  
For the matrix multiplication \(W=V\tilde{X}\), the number of scalar multiplications required is \(\Xi_{W}(N)=\Xi_{\tilde{X}}(N)\). The number of scalar additions required for adding the columns vectors of \(W\) is  
\[\Phi_{W}(N) =m_{-1}^{2}+(m_{1}+m_{-1}-1)\bigg{(}\left\lfloor\frac{N}{2} \right\rfloor+1-m_{-1}\bigg{)}\] \[\quad+m_{j}^{2}+\big{(}m_{j}+m_{-j}-1\big{)}\bigg{(}\left\lfloor \frac{N-1}{2}\right\rfloor-m_{j}\bigg{)} \tag{32}\]From (30), (31) and (32) the total number of multiplications and additions required using [PERSON] method is  
\[\Xi(N) =\Xi_{\widehat{X}}(N)+\Xi_{W}(N)\] \[=2\Xi_{\widehat{X}}(N) \tag{33}\] \[\Phi(N) =\Phi_{\widehat{X}}(N)+\Phi_{W}(N) \tag{34}\]  
If \(N\) is very large, the number of multiplications and additions required using [PERSON]'s DFT eigenvectors is approximated:  
\[\Xi(N) \approx\frac{3}{4}N^{2} \tag{35}\] \[\Phi(N) \approx\frac{9}{8}N^{2} \tag{36}\]  
If the input is even or odd symmetric, the number of multiplications and additions can be further reduced. In contrast to (33) and (34), brute force computation of the DFT for a real input requires \(2(N-1)^{2}\) real multiplications and an equal number of additions. Thus, the method proposed here performs better when compared to the brute force DFT computation. Using the Matveev eigenvectors, our method also outshines the DFT calculated using the \(N/2\)-point DFT. Moreover, unlike most FFT algorithms, our method does not require that \(N\) be highly composite. One can combine our approach with deconstructive algorithms like the Cooley-Tukey algorithm or the prime factor algorithm to yield efficient algorithms for computing the DFT of large sequences. This approach is certainly effective when the length \(N\) is not an integer power of 2. Figure 4 shows the number of multiplications required for computing the DFT using various methods.