Why is 'eig' slower for tridiagonalized matrices ?

Consider the list of commands below:

>> A = gallery('poisson', 60);

>>

>> tic; [V,D] = eig(full(A)); toc

Elapsed time is 16.074685 seconds.

>>

>> B = hess(full(A)); tic; [V,D] = eig(B); toc

Elapsed time is 28.709543 seconds.

>>

>>

Why does 'eig' take longer on the tridiagonalized version of A ?

This behaviour occurs with other matrices. I'm running MATLAB R2011b.

Answer 1

[Cam Salzberger]

Hello Douglas,

The brief answer is that it isn't anymore. In R2013a, there was an improvement in the handling of tridiagonalized matrices in "eig". Testing on my computer in R2011b and R2015b, I get:

R2011b:
eig(full(A)) - ~9 seconds
eig(B) - ~14.5 seconds

R2015b:
eig(full(A)) - ~3.7 seconds
eig(B) - ~0.6 seconds

I would recommend upgrading to the latest version of MATLAB, if you are able to.

-Cam

[Douglas Gonçalves]

Thanks Cam,

I've just figured out that 'eig' in R2011b is calling DSYEV Lapack's routine. This routine has a scaling preprocessing step in which the input symmetric matrix is scaled based on its maximum absolute entry.

I guess the different scalings are making things harder to the QR algorithm in DSYEV.

The problem doesn't occur when calling DSYEVD Lapack's routine which implements a divide-and-conquer approach.

Thanks again for your answer. I'll try to update my MATLAB.

Douglas