1
$\begingroup$

I have a tridiagonal matrix (1000×1000) with each element equal to $1$ except {n, n} = 2. It takes 8 hours to give me the eigenvalues?!!

Here is the code I used:

n=1000;

m = SparseArray[{Band[{1, 2}] -> 1, Band[{2, 1}] -> 1, 
    Band[{2, 2}, {n - 1, n - 1}] -> 2 , {1, 1} -> 2, {n, n} -> 
     2 , {1, n} -> 0, {n, 1} -> 0}, {n, n}];

N[Eigenvalues[m]];
$\endgroup$
2
  • $\begingroup$ Your matrix hasn't the form you are describing. Try m//MatrixForm $\endgroup$ Mar 11, 2015 at 23:18
  • $\begingroup$ FWIW mma v9 actually throws a warning that clearly provides the answer to this question. ...consider using N on the matrix ... $\endgroup$
    – george2079
    Mar 12, 2015 at 19:00

3 Answers 3

8
$\begingroup$

The way you've written things, you're passing an exact matrix to Eigenvalues and then finding a numerical approximation afterwards, so Mathematica is trying to compute an exact answer algebraically. For a 1000 × 1000 matrix, this obviously takes a while. In order to get an answer more quickly, find the numerical approximation first and then find the eigenvalues, like so:

Eigenvalues[N[m]];

On my computer, this takes less than a second with the matrix specified.

$\endgroup$
2
  • $\begingroup$ It works, Thank you very much $\endgroup$
    – MMA13
    Mar 12, 2015 at 0:09
  • 5
    $\begingroup$ Instead of using the default method, one can utilize the banded structure and use the following command: Eigenvalues[N[m], Method -> "Banded"] $\endgroup$
    – hck
    Dec 25, 2015 at 17:27
5
$\begingroup$

Use N on the matrix itself

n = 1000;
m = SparseArray[{Band[{1, 2}] -> 1, Band[{2, 1}] -> 1, 
    Band[{2, 2}, {n - 1, n - 1}] -> 2, {1, 1} -> 2, {n, n} -> 2, {1, n} -> 0, {n, 1} -> 0}, {n, n}];
AbsoluteTiming[Eigenvalues[N@m]]


 {0.489062, {3.99999, 3.99996, 3.99991, 3.99984, 3.99975, 3.99965, 3.99952, 3.99937, 3.9992,....
$\endgroup$
2
  • $\begingroup$ Thanks a lot. But I got the result with this message : Eigenvalues::arh: Because finding 500 out of the 500 eigenvalues and/or eigenvectors is likely to be faster with dense matrix methods, the sparse input matrix will be converted. If fewer eigenvalues and/or eigenvectors would be sufficient, consider restricting this number using the second argument to Eigenvalues. $\endgroup$
    – MMA13
    Mar 11, 2015 at 23:27
  • $\begingroup$ Yes it is.. Again, thank you very much Nasser! $\endgroup$
    – MMA13
    Mar 11, 2015 at 23:34
5
$\begingroup$

It is known that there are closed forms for the eigenvalues of tridiagonal Toeplitz matrices like the one given in the OP:

n = 1000;
N[4 Sin[π Range[n]/(2 n + 2)]^2]

See the linked paper for more details, as well as closed forms for the eigenvalues of modified tridiagonal Toeplitz matrices.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.