On the Solvability Complexity Index (SCI) hierarchy - Establishing the foundations of computational mathematics
55 mins 35 secs,
198.57 MB,
WebM
640x360,
30.0 fps,
44100 Hz,
487.76 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Hansen, A
Tuesday 26th November 2019 - 15:05 to 16:05 |
|---|
| Created: | 2019-11-26 16:04 |
|---|---|
| Collection: | Geometry, compatibility and structure preservation in computational differential equations |
| Publisher: | Isaac Newton Institute |
| Copyright: | Hansen, A |
| Language: | eng (English) |
| Distribution: |
World
(downloadable)
|
| Explicit content: | No |
| Aspect Ratio: | 16:9 |
| Screencast: | No |
| Bumper: | UCS Default |
| Trailer: | UCS Default |
| Abstract: | 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.
|
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.92 Mbits/sec | 800.90 MB | View | Download | |
| WebM * | 640x360 | 487.76 kbits/sec | 198.57 MB | View | Download | |
| iPod Video | 480x270 | 512.46 kbits/sec | 208.56 MB | View | Download | |
| MP3 | 44100 Hz | 249.75 kbits/sec | 101.77 MB | Listen | Download | |
| Auto | (Allows browser to choose a format it supports) | |||||