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

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

• Anders Hansen (University of Cambridge)
• Tuesday 26 November 2019, 15:05-16:05
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact INI IT.

This talk has been canceled/deleted

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. 

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.