# A FEAST Algorithm for the Linear Response Eigenvalue Problem
## 4 Numerical Examples
The numerical results of Algorithm 1 by running four FEAST iterations with \(q\) varying from four to nine are presented in Table 3. It is shown by Table 3 that the trapezoidal rule with 6, 7, or 8 quadrature nodes already achieved satisfactory results._  
_Notice that the wanted eigenvalues are inside the intervals presented in Table 2. The shift and invert strategy is usually not available for LREP since the traditional algorithms to calculate the partial spectrum of LREP, such as the methods proposed in [6; 8], combined with the shift and invert strategy will lose the structure of (2)._  
_In addition, as stated in [17], the FEAST algorithm can be cast as a direct technique in comparison to iterative Krylov subspace-type methods, because it is based on an exact mathematical derivation (5). Therefore, by dividing the whole spectrum of LREP into a number of disjoint intervals, the FEAST algorithm is able to compute all eigenvalues simultaneously on the parallel architectures. From this aspect, as [24], we compared Algorithm 1 with the MATLAB built-in function eig, which was used to compute all eigenvalues of \(H\), and then, the target eigenvalues were selected in this example. Let the number of quadrature nodes \(q=7\) and the convergence tolerance \(\epsilon=10^{-8}\). Table 4 reports the total required CPU time in seconds of Algorithm 1 and eig for test 1, test 2, and test3, respectively. It is clear from Table 4 that Algorithm 1 was much faster than the MATLAB built-in function eig in this example. A similar comparison between the FEAST-type algorithms and the MATLAB built-in function eig in terms of timing can be found in [30; 31]._  
**Example 3**. : _As stated in Section 3, the implementation of Algorithm 1 involves solving several shifted linear systems of the form:_  
\[(\mu_{i}I-KM)X_{i}=Y,\quad\text{for }i=1,2,\ldots,q.\]  
_Direct solvers referring to \(\mathcal{O}(N^{3})\) operations are prohibitively expensive in solving large-scale sparse linear systems. Iterative methods, such as Krylov subspace-type methods [32], are usually preferred for large-scale sparse linear systems. However, Krylov subspace solvers may need a large number of iterations to converge. A \begin{table}
\begin{tabular}{c c c} \hline \hline
**Problem** & **eig** & **Algorithm 1** \\ \hline test 1 & 45.82 & 15.88 \\ test 2 & 159.77 & 37.08 \\ test 3 & 1200.71 & 233.12 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparison of Algorithm 1 and eig for CPU time in seconds. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**Problem** & \(N\) & \(K\) & \(M\) & \((\underline{\omega_{1}},\overline{\omega_{1}})\) & \(s_{1}\) & \((\underline{\omega_{2}},\overline{\omega_{2}})\) & \(s_{2}\) & \((\underline{\omega_{3}},\overline{\omega_{3}})\) & \(s_{3}\) \\ \hline test 1 & 1862 & Na\({}_{2}\) & Na\({}_{2}\) & (0.40,0.50) & 3 & (0.60,0.70) & 3 & (1.50,1.60) & 3 \\ test 2 & 2834 & Na\({}_{4}\) & Na\({}_{4}\) & (0.03,0.04) & 4 & (0.05,0.06) & 4 & (0.32,0.33) & 5 \\ test 3 & 5660 & SiH4 & SiH4 & (0.25,0.30) & 3 & (0.75,0.80) & 6 & (1.75,1.80) & 8 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Test matrices. \begin{table}
\begin{tabular}{c|c c|c c|c c} \hline \hline
**Problem** & \(N\) & \(K\) & \(M\) & \((\underline{\omega_{1}},\overline{\omega_{1}})\) & \(s_{1}\) & \((\underline{\omega_{2}},\overline{\omega_{2}})\) & \(s_{2}\) & \((\underline{\omega_{3}},\overline{\omega_{3}})\) & \(s_{3}\) \\ \hline test 1 & 1862 & Na\({}_{2}\) & Na\({}_{2}\) & (0.40,0.50) & 3 & (0.60,0.70) & 3 & (1.50,1.60) & 3 \\ test 2 & 2834 & Na\({}_{4}\) & Na\({}_{4}\) & (0.03,0.04) & 4 & (0.05,0.06) & 4 & (0.32,0.33) & 5 \\ test 3 & 5660 & SiH4 & SiH4 & (0.25,0.30) & 3 & (0.75,0.80) & 6 & (1.75,1.80) & 8 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Changes of \(\max e(\rho_{j})\) and \(\max r(\rho_{j})\) with the number of quadrature nodes \(q\) varying from 4 to 9.  
way to speed up the FEAST method for LREP is to terminate the iterative solvers for linear systems before full convergence is reached.