Eigs Performance SA vs. SM

I have a question about the MATLAB function eigs.

Recall that if A and B are both square, symmetric, positive definite matrices of the same size, then the set of generalized eigenvalues of the pencil (A,B) are all positive (and hence, real). When computing some of the pencil's extremal eigenvalues (let's say the smallest k), one can call either

eigs(A,B,k,'SA');   %(SA := smallest algebraic)

or

eigs(A,B,k,'SM');   %(SM := smallest magnitude)

and expect to get the same results. When I run my code, I notice that using the SM option is faster than the SA option, and sometimes significantly so. Can anyone offer an explanation as to why this is the case? I have a written a modest benchmark program that clocks the performance of eigs for both options (in this setting, k = 1; we are computing the smallest eigenvalue of the pencil (A,B)). Below is the code that I ran. Note that one can increase the value of the parameter num (but still keep it less than n) to exaggerate the results of experiment.

clc;
close all;
clear all;

symm = @(X) (X+X')/2;

sqn = 100; n = sqn^2;
A =  gallery('poisson',sqn);
num = 2; density = num/n; rc = 0.1; 
B = sprandsym(n, density, rc, 1); 
A = symm(A); B = symm(B);

fprintf('Running eigs script.\n\n');
if norm(A - A',1)==0
    fprintf('A is symmetric ');
else
    fprintf('A is not symmetric ');
end
if eigs(A,1,'SA')>0
    fprintf('and positive definite.\n');
else
    fprintf('but not positive definite.\n');
end
if norm(B - B',1)==0
    fprintf('B is symmetric ');
else
    fprintf('B is not symmetric ');
end
if eigs(B,1,'SA')>0
    fprintf('and positive definite.\n\n');
else
    fprintf('but not positive definite.\n\n');
end 

k = 1;
tic; e1 = eigs(A,B,k,'SA'); t1 = toc;
tic; e2 = eigs(A,B,k,'SM'); t2 = toc;
fprintf('The smallest (algebraic) eigenvalue of the matrix pencil (A,B) is %f. Elapsed time: %f.\n',e1,t1);
fprintf('The smallest (magnitude) eigenvalue of the matrix pencil (A,B) is %f. Elapsed time: %f.\n',e2,t2);

[jgg]

I've noticed based on a prior thread you can actually run the profiler when calling eigs. This might help you get some more insight. It would make sense to me that sa would be slower, since it would have to verify the output is algebraic, which is a lot easier than just computing the magnitude.

[Frankie Camacho]

What would be the best way to find out what is going on under the hood (as in a detailed analysis) of eigs? Are there any good references that people can recommend? I'm looking through the eigs m-file and the ARPACK user guide. That being said the answer already given is very useful.

Answer 1

[Christine Tobler]

The reason is that eigs uses very different algorithms for the two versions. Here's what each algorithm does

'lm': This is the simplest case: eigs does a smarter version of the power iteration, which is just

for i=1:N
    x = A*x;
    x = x / norm(x);
end

The trick is that the component of x pointing in the direction of the largest eigenvector will grow. The smarter algorithm used in eigs keeps the vectors x in memory, and returns the best linear combination of vectors instead.

'sm', numerical shift sigma: This algorithm uses the shift-and-invert method, which consists in doing (A - simga*I)\x instead of A*x. For 'sm', sigma = 0.

'sa', 'la', 'sr', 'lr', 'si', 'li': These methods do not solve a linear system with A. Instead, they use the power iteration, but choose the linear combination of all vectors that best satisfies the condition given by the input flag.

For your symmetric positive definite problem, the algorithm used in 'sm' will often have faster convergence, while the algorithm used in 'sa' does not require factorization of the matrix A. Which is faster depends on the problem, my personal favorite would be 'sm'.

[Frankie Camacho]

Great, thanks for explanation.