What is the residual defined in eigs?

I try to use to solve a generalized eigenvalue problem, , for the few smallest eigenvalues in modulus and corresponding eigenvectors. The claims the eigenpairs returned have converged in tol=1e-13, but when I examine the residual by , the residual is still around 1e-3. What is happening? Is the residual defined in being so much different from the one I use causes this problem?. I have read the official document of , but no details about the residual defined in .

Answer 1

[Sudarsanan A K]

Hi 俞而 陈,

The "eigs" function in MATLAB is designed for efficiently solving eigenvalue problems by leveraging the ARPACK library, which is:

• A collection of Fortran subroutines optimized for large-scale eigenvalue challenges.
• Utilizes the Arnoldi process, an iterative method for approximating eigenvalues and eigenvectors of large sparse matrices.

In the context of eigs, it is important to distinguish between:

• Residuals: Stem from the Arnoldi process and serve as an estimate of the approximation error in the eigenvalues, reflecting the quality of the computed eigenpairs and their adherence to the problem's requirements. The residual is calculated using a formula that compares the left-hand side and right-hand side of the generalized eigenvalue problem, providing information about the quality of the computed eigenpairs.
• Tolerance ("tol"): Dictates the convergence threshold for the iterative process, ensuring computed eigenvalues closely match actual values. "Tol" is a parameter that specifies the tolerance for convergence of the eigenvalues, determining how close the computed eigenvalues need to be to the actual eigenvalues to be considered converged. It does not directly relate to the residual calculation.

Therefore, the residual is a measure of the accuracy of the computed eigenpairs, while "tol" is a parameter that controls the convergence of the eigenvalues.

https://www.mathworks.com/help/matlab/ref/eigs.html#References

I hope this helps!

[俞而 陈]

Thanks for your answer. Does that means, the convergence criterion of depends on the residual in the sense ritz other than the residual of eigenpair?

I test the ritz residuals, which substitude for the numerator. They achieve 1e-11. Though it still not less than the Tolerance, but not so far. I still don't now the exact formula in math for what Tolerance works on [cry].

[俞而 陈]

I find the Tolerance's meaning in convergence in ARPACK use-guide, it is a little complicated than I thought before. But it is true that the convergence of only promises the accuracy of eigenvalues not the eigenvectors.

Answer 2

[Christine Tobler]

The issue is likely that eigs doesn't use the residual as you describe it: The iterative algorithm used inside of eigs when computing the eigenvalues of smallest absolute value is transforming the generalized eigenvalue problem into a simple eigenvalue problem, of which it computes a few eigenvalues of largest absolute value.

So issues with the residual are likely due to the transformations applied to matrices A and B to achieve this. You can find out which simple eigenvalue problem is being solved underneath for your case by using the Display option:

eigs(sprandn(1e3, 1e3, 1e3), sprandn(1e3, 1e3, 1e3), 5, "smallestabs", Display=true)

The display in this case shows the problem being solved underneath as

Find eigenvalues of A\(B*x) = mu*x.

So in this case, the residual being used internally will be norm(A\(B*x) - mu*x) / mu, where mu is the inverse of the eigenvalues being returned.

By the way, eigs doesn't use the ARPACK library anymore, although we still reference it in our documentation since many of the treatments of the various cases are still strongly based on the original implementation of eigs that used ARPACK, and on the recommendations of the ARPACK user's guide.