EIGS: Why is 'smallestabs' faster than 'largestabs'?

9 views (last 30 days)
Jeova Farias on 18 Feb 2021
Commented: Christine Tobler on 22 Feb 2021
Hi! Let L be the Laplacian matrix of a grid graph of n nodes, D a diagonal matrix of positive values and s a vector of dimension n. I want to find x, such that for the second smallest generalized eigenvalue. I've tried to run (1) "eigs(L, S, 2, "smallestabs")", (2) "eigs(S*L, 2, "smallestabs")" and (3) "eigs(speye(n) - S*L, 2, "largestabs")", where S is an analitical form for inv(D + s*s'), so I don't need to compute the inversion explicitly. It happens that (1) and (2) are faster than (3), and (1) faster than (2). I thought that computing "largestabs" should be faster. Am I wrong about it?
Beyond this question, I'd like to use a function handle instead of an explicit definition of S or L, since S has a lot of structure and S*L*x can be computed very efficiently. However, it seems that I can't accomphish that when I'm using "smallestabs", which in this case I have to find a function that computes A\x, not A*x. Can someone help me go around this problem?
Many thanks!
Jeova Farias on 18 Feb 2021
By the way, please correct if I am wrong, but I am assuming that (1), (2) and (3) output the same eigenvectors.

Christine Tobler on 19 Feb 2021
Edited: Christine Tobler on 19 Feb 2021
Whether 'largestabs' or 'smallestabs' depends on the problem: 'smallestabs' needs to factorize the first input, which can make it slower than 'largestabs'. However, the speed of convergence of the iteration that's done afterwards depends on the spectrum of the matrix used, and sometimes that spectrum is better in the 'smallestabs' case (where we're using the inverse of the original problem), then if the matrix is just shifted. This roughly speaking comes down to how large the ratio between the eigenvalues to be calculated is.
It's usually a good idea to keep a generalized eigenvalue problem in the generalized form, because computing S*L will result in a nonsymmetric matrix, which prevents us from using symmetric methods which are usually faster and more accurate.
The problem here is that D+s*s' will be a dense matrix, so whenever that's computed it will slow down all the computation by a lot.
I'd first try solving the reverse eigenproblem instead, (D+s*s')*x = mu*L*x, where lambda = 1/mu and now you'd want to compute the second largest eigenvalue:
eigs(D+s*s', L, 2, "largestabs")
Here you can then use a function handle to apply S instead of forming the matrix explicitly.
Note I'm assuming here that L is symmetric positive definite. The approach will still work otherwise, but I'm not sure how well convergence will turn out in that case - generalized eigenvalue solvers are usually optimized for the case where the right-hand side matrix is s.p.d., since this is often the mass matrix.
Christine Tobler on 22 Feb 2021
So the first here will return the smallest (lambda, x) s.t.
lambda*D*x - L*x + s*s'*x = 0,
while the second will return the smallest (lambda, x) s.t.
lambda*D*x - L* x + lambda*s*s'*x = 0,
so on the face of it these aren't solving the same problem. However, if you're looking to solve (L - s*s' - D) * x = 0, that's a different question again, and I might try to just compute
eigs(-L + D + s*s', 1, 'smallestabs')
in that case.