The Computational Spectral Problem and a New Classification Theory: Novel Algorithms, Impossibility Results and Computer Assisted Proofs

Add to your list(s) Download to your calendar using vCal

• Matthew Colbrook (University of Cambridge)
• Wednesday 24 October 2018, 16:00-17:00
• MR14, Centre for Mathematical Sciences.

If you have a question about this talk, please contact Simon Becker.

We will discuss and extend the Solvability Complexity Index (SCI) hierarchy, which is a classification hierarchy for all types of problems in computational mathematics that allows for classifications determining the boundaries of what computers can achieve in scientific computing. The SCI hierarchy captures many key computational issues in the history of mathematics including Smale’s problem on the existence of iterative generally convergent algorithm for polynomial root, the computational spectral problem, inverse problems, optimisation, numerical solution of PDEs etc., and also mathematical logic. Perhaps surprisingly, many of the classifications in the SCI hierarchy do not depend on the model of computation used (e.g. BSS , Turing) and in some sense the hierarchy seeks to bridge the gap between numerical analysts (who deal with the continuum) and computer scientists (who deal with the discrete). Informally we classify the number of successive limits (SCI index) of algorithms needed to solve a problem. The study of the non-computable is needed for several reasons. It is crucial in the field of rigorous numerical analysis and in fact many everyday problems turn out to be not computable. Moreover, the SCI hierarchy helps classifying problems suitable for computer assisted proofs. In particular, undecidable or non-computable problems are used in computer assisted proofs, where the recent example of the resolution of Kepler’s conjecture (Hilbert’s 18th problem) is a striking example. However, only certain classes of non-computable problems can be used in computer assisted proofs, and the SCI hierarchy helps detecting such classes. Finally, the construction of several limits of algorithms can help tell us what information within the problem is needed to lower the index and provide a numerical procedure. The SCI hierarchy allows for solving the long standing computational spectral problem, and reveals potential surprises. For example, the problem of computing spectra of compact operators, for which the method has been known for decades, is strictly harder than the problem of computing spectra of Schrodinger operators with bounded potentials, which has been open for more than half a century. We provide an algorithm for the latter problem, thus finally resolving this issue. We also provide the first algorithm that can compute spectra without spectral pollution. The method also provides error control on the output and we provide cutting edge numerical examples showing it to be competitive with state of the art methods (which do not converge in general). The SCI hierarchy also allows one to prove that detecting the problem of spectral pollution is strictly harder than computing the spectrum itself. Other problems such as point spectra, and fractal dimension of spectra will also be discussed. These problems are samples of what is likely to be a very rich classification theory.

This talk is part of the Cambridge Analysts' Knowledge Exchange series.

This talk is included in these lists:

• All CMS events
• CMS Events
• Cambridge Analysts' Knowledge Exchange
• DAMTP info aggregator
• Interested Talks
• MR14, Centre for Mathematical Sciences
• My seminars
• bld31

Note that ex-directory lists are not shown.