On the Solvability Complexity Index, the 𝑛-pseudospectrum and approximations of spectra of operators

We show that it is possible to compute spectra and pseudospectra of linear operators on separable Hilbert spaces given their matrix elements. The core in the theory is pseudospectral analysis and in particular the n n -pseudospectrum and the residual pseudospectrum. We also introduce a new classification tool for spectral problems, namely, the Solvability Complexity Index. This index is an indicator of the “difficultness” of different computational spectral problems.