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

조회 수: 10(최근 30일)
Jeova Farias 2021년 2월 18일
댓글: Christine Tobler 2021년 2월 22일
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!
##### 댓글 수: 1표시숨기기 없음
Jeova Farias 2021년 2월 18일
By the way, please correct if I am wrong, but I am assuming that (1), (2) and (3) output the same eigenvectors.

댓글을 달려면 로그인하십시오.

### 채택된 답변

Christine Tobler 2021년 2월 19일
편집: Christine Tobler 2021년 2월 19일
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.
##### 댓글 수: 5표시숨기기 이전 댓글 수: 4
Christine Tobler 2021년 2월 22일
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.

댓글을 달려면 로그인하십시오.

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by