# Time used by Mathematica to calculate tridiagonal matrix

I have a question.

I need to find the eigenvalues and eigenvectors of a tridiagonal matrix of size NxN. Can you tell me how much time does Mathematica need to do that in minutes? for

Size N time for eigenvalues time for eigenvectors

10,000

100,000

1000,000

I use the absolutingtimes , but I do not how use in this case Thanks anyway

• All eigenvalues or only few of the smallest ones. That's crucial. – Henrik Schumacher Jun 1 at 10:27
• All it is possible thanks – Clerk Jun 1 at 10:28
• Seriously: 100000 eigenvalues? Will take forever. With any computing software. You won't be able to store the eigenvalues in memory. Please, be more specific about what you ask. – Henrik Schumacher Jun 1 at 10:58
• Theoretical computational complexity is $O(n^2)$, where $n$ is the matrix order. Some schemes (not implemented in MA) with $O(n\log n)$ complexity are also known. While you might be able to store $10^6$ eigenvalues, you cannot store or compute that many eigenvectors. – yarchik Jun 1 at 12:26

This computes the finite element stiffness A and mass matrix M of the Laplacian on the unit interval and the 10 smallest eigenvalues and their eigenvectors.

For computing only few eigenpairs, it is usually a good idea to use Arnoldi's method. I compute here the eigenfactions of the Laplacian subject to Neumann conditions. Because the first eigenvalue is 0, I apply also a "Shift".

If one limits oneself only to a few relevant eigenpairs, this computations can be performed within a few seconds.

n = 1000000;
A = SparseArray[{
{1, 1} -> 1. n,
{-1, -1} -> 1. n,
Band[{2, 1}] -> -1. n,
Band[{1, 1}] -> 2. n,
Band[{1, 2}] -> -1. n
},
{n + 1, n + 1}, 0.
]; // AbsoluteTiming // First
M = SparseArray[{
{1, 1} -> 1./(3 n),
{-1, -1} -> 1./(3 n),
Band[{2, 1}] -> 1./(6 n),
Band[{1, 1}] -> 2./(3 n),
Band[{1, 2}] -> 1./(6 n)
},
{n + 1, n + 1}, 0.
]; // AbsoluteTiming // First
{\[Lambda], U} = Eigensystem[{A, M}, -10, Method -> {"Arnoldi", "Shift" -> 1.}]; //
AbsoluteTiming // First


6.88233

6.82736

11.3716

It is worth noting that constructing these matrices with Band is very convenient but also not very efficient. In principle, the matrices can be assembled by an order of magnitude faster.