On the final frontiers in computational mathematics
Core problems in computational mathematics include computing spectra of operators, solutions to linear PDEs, convex optimisation problems etc., and these areas have been intensely investigated over the last half century. However, there are still fundamental open problems. For example, despite more than 90 years of quantum mechanics, it is still unknown whether it is possible to compute spectra of Schrodinger operators with bounded potentials. Moreover, how to compute minimisers of linear programs (LP) with rational inputs has been known since the 1950s, however, what happens if the input is irrational? Can one accurately compute minimisers of LPs if, as in compressed sensing, the matrix has rows from the discrete cosine transform? Furthermore, do there exist algorithms that can handle all linear Schrodinger PDEs? And, if not, which can be handled and which can never be solved? We will discuss solutions to many of these open problems and provide some potentially surprising results. For example, despite being open for decades, the problem of computing spectra of Schrodinger operators with bounded potentials is not harder than computing spectra of diagonal infinite matrices, the easiest of computational spectral problems. Moreover, for LPs with irrational inputs we have the following phenomenon. For any integer K > 2 there exists a class of well conditioned inputs 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.