4
$\begingroup$

I have written the following code in MATLAB. I also observe the same effect in Arnoldi iteration in ARPACK in C.

N = 4000;
A = rand(N); % Random entries in Uniform[0,1]
tic
AstarA = A.' * A + 5*eye(N);
toc
AstarAinv = inv(AstarA); % Inverse
tic
eigs(AstarA, 1, "smallestreal") % Eigenvalue with smallest real part
toc
tic
eigs(AstarAinv, 1, "largestreal") 
toc
tic 
svds(A, 1, "smallest");
toc

Observations:

  1. eigs(AstarA, 1, "smallestreal") takes about 16s.
  2. eigs(AstarA, 1, "largestreal") takes about 8s.
  3. svds(A, 1, "smallest") takes 6s.

I am perplexed by the result. I do not know what is going on in svds sooooo slow, but for the first two observations, I have implemented Arnoldi iteration in ARPACK in C. I see the same effect - the algorithm converges faster with the inverted matrix.

I could not understand this - if many eigenvalues are very close to zero then surely inverting can help pull clustered eigenvalues apart and speed up convergence. But the smallest eigenvalue of AstarA is about 5, which is far from zero. So why inverting the matrix still helps?

The same effect persists when I change real to abs. You cannot say it is because it is easier to work with largest absolute values than smallest values - "smallestreal" and "largestreal" are fully symmetric concepts.

[Also, although it might not be possible to answer, why is svds faster? Isn't it also using Arnoldi iteration?]

$\endgroup$
0

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.