COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > On the Solvability Complexity Index (SCI) hierarchy - Establishing the foundations of computational mathematics

## On the Solvability Complexity Index (SCI) hierarchy - Establishing the foundations of computational mathematicsAdd 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 info@newton.ac.uk. GCS - Geometry, compatibility and structure preservation in computational differential equations 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:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsTanner Lectures Cambridge Institute for Language Research events Neuroscience## Other talksPaediatric Cancer Programme Meeting Nov 2019 Repeated Measures and Mixed Model ANOVA The roots of change: global change and mycorrhizal symbiosis through the Phanerozoic Souriau Symplectic Structures of Lie Group Machine Learning on Statistical Drone Doppler/Kinematic Signatures Is dispersion a stabilizing or destabilizing mechanism? Some examples in fluid mechanics Ethics for the working mathematician, lecture 8: Looking into the future, what more can mathematicians do? |