Spectral radius of matrix?

In order to find the spectral radius of a matrix, I commonly use

max(abs(eig(A)))

that computes all the eigenvalues. Is there a faster way? I'm interested only on the spectral radius, and don't need anything else..

Answer 1

[Steven Lord]

Ask the eigs function to return the largest magnitude eigenvalue.

% Generate a vector of eigenvalues suitable for the 'randcorr' option of the gallery function
x = rand(1, 100);
x = 100*x./sum(x);

% Generate a matrix whose eigenvalues are the elements of x
A = gallery('randcorr', x);

% Compute the largest magnitude eigenvalue
largest = eigs(A, 1, 'lm')

% Check: this should be small
largest - max(x)

If you're using release R2017b or later, you might want to use 'largestabs' instead of 'lm' in the eigs call. The old options are still accepted, but 'largestabs' is more descriptive of what it's doing than 'lm'.

[Jan]

X = rand(1000, 1000);
tic; e1 = max(abs(eig(X))); toc
tic; e2 = eigs(A, 1, 'lm'); toc
e1, e2

 Elapsed time is 0.733548 seconds.
 Elapsed time is 0.069295 seconds.
 e1 =
  499.5490
 e2 =
  499.5490

+1.

[David Goodmanson]

Since we are just using rand for a test case,

 X = rand(1000, 1000);
 tic; e1 = max(abs(eig(X))); toc
 tic; e2 = eigs(X, 1, 'lm'); toc
 tic;
 n = rand(1000,1);             % line added per comment below
 for k = 1:4
   n = X*n/max(abs(n)); 
 end
 e3 = mean(X*n./n);
 toc

 e1, e2, e3

 Elapsed time is 1.426244 seconds.
 Elapsed time is 0.021678 seconds.
 Elapsed time is 0.004378 seconds.

 e1 = 499.6231
 e2 = 499.6231
 e3 = 499.6231

 :)

[Jan]

@David: What is n initially?

[David Goodmanson]

Hi Jan,

I forgot that line. The initial n is rand(1000,1), so I addended the comment.

The code was not a serious suggestion since it does not contain a tolerance check to stop the iteration, which might have slowed it down too much. But I found that for the special case of the random matrix it takes surprisingly few iterations to get a pretty accurate result.

[Joseph Moore]

eigs(X, 1, 'lm') will give negative answers