skip to content

On the Solvability Complexity Index (SCI) hierarchy - Establishing the foundations of computational mathematics

Presented by: 
Anders Hansen
Tuesday 26th November 2019 - 15:05 to 16:05
INI Seminar Room 1
There are four areas in computational mathematics that have been intensely investigated over more than half a century: Spectral problems, PDEs, optimisation and inverse problems. However, despite the matureness of these fields, the foundations are far from known. Indeed, despite almost 90 years of quantum mechanics, it is still unknown whether it is possible to compute the spectrum of a self-adjoint Schrodinger operator with a bounded smooth potential. Similarly, it is not known which time dependent Schrodinger equations can be computed (despite well posedness of the equation). Linear programs (LP) can be solved with rational inputs in polynomial time, but can LPs be solved with irrational inputs? Problems in signal and image processing tend to use irrational numbers, so what happens if one plugs in the discrete cosine transform in one's favourite LP solver? Moreover, can one always compute the solutions to well-conditioned infinite-dimensional inverse problems, and if not, which inverse problems can then be solved? In this talk we will discuss solutions to many of the questions above, and some of the results may seem paradoxical. Indeed, despite being an open problem for more than half a century, computing spectra of Schrodinger operators with a bounded potential is not harder than computing spectra of infinite diagonal matrices, the simplest of all infinite-dimensional spectral problems. Moreover, computing spectra of compact operators, for which the method has been known for decades, is strictly harder than computing spectra of such Schrodinger operators. Regarding linear programs (and basis pursuit, semidefinite programs and LASSO) we have the following. For any integer K > 2 and any norm, there exists a family of well conditioned inputs containing irrational numbers so that no algorithm can compute K correct digits of a minimiser, however, there exists an algorithm that can compute K-1 correct digits. But any algorithm producing K-1 correct digits will need arbitrarily long time. Finally, computing K-2 correct digits can be done in polynomial time in the number of variables. As we will see, all of these problems can be solved via the the Solvability Complexity Index (SCI) hierarchy, which is a theoretical program for establishing the boundaries of what computers can achieve in the sciences. 

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons