How does eigs work?

[jw3126]

I am trying to understand how eigs works. I understand that it builds a size (n,n) approximation of the operator and computes eigenvalues of it. What I don't understand is the idea behind pruneeigs. Why do we need to throw away some eigenvectors? And why is it a good criterion to keep only those vectors whose last four components have a small norm? Or do I misunderstand something?

ApproxFun.jl/src/Extras/eigs.jl

Line 53 in 5d84172

if slnorm(V,n-3:n,k)≤tolerance

[dlfivefifty]

Because you want the ∞-dimensional eigenfunctions, not the spurious ones coming from truncation. Checking the norm is of the tail is a convenient proxy for convergence.

[jw3126]

Ok, if the operator A is banded such that it A[i,j] == 0 for |i-j| >= 3 and tolerance=0 and no rounding errors then pruneigs selects exactly those eigenvectors of the truncated operator that are also eigenvectors of A. Is this correct?

[dlfivefifty]

The true eigenfunctions have vectors with an ∞ number of entries, so they are technically different than the finite dimension eigenvectors. But these vectors decay exponentially fast so effectively they are finite-dimensional.

A simple example are eigenfuctions of u'' with Dirichlet conditions using Chebyshev series. These are of course just sine functions, whose Chebyshev coefficients are known explicitly in terms of Bessel functions. They are not polynomial however and so you technically need an infinite number of coefficients.

[jw3126]

Thanks! If you are interested I can turn your explainations into a docstring for eigs. As a naive user my expectation was that the n argument is the number of eigenvectors that the function should return, thats why I started digging.

[jw3126]

Can you point me to some literature that explains why we expect exponential decay of coefficients?

[dlfivefifty]

If you are interested I can turn your explainations into a docstring

Sure! Though long term this should be replaced by an infinite-dimensional implementation of shifted simultaneous iteration, which is why not much effort has gone into this yet.

Can you point me to some literature that explains why we expect exponential decay of coefficients?

This is a fairly standard result that follows since the eigenvectors are in all Sobolev spaces. Roughly, if we have

Ax = λx

and A is a differential operator, then of course A^n*x = λ^n*x and therefore x is infinitely differentiable. Smoothness translates into super-algebraic decay in coefficients by integration-by-parts arguments.