BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Computational Spectral Problem and a New Classification Theory
 : Novel Algorithms\, Impossibility Results and Computer Assisted Proofs - 
 Matthew Colbrook (University of Cambridge)
DTSTART:20181024T150000Z
DTEND:20181024T160000Z
UID:TALK113005@talks.cam.ac.uk
CONTACT:Simon Becker
DESCRIPTION:We will discuss and extend the Solvability Complexity Index (S
 CI) hierarchy\, which is a classification hierarchy for all types of probl
 ems in computational mathematics that allows for classifications determini
 ng the boundaries of what computers can achieve in scientific computing. T
 he SCI hierarchy captures many key computational issues in the history of 
 mathematics including Smale's problem on the existence of iterative genera
 lly convergent algorithm for polynomial root\, the computational spectral 
 problem\, inverse problems\, optimisation\, numerical solution of PDEs etc
 .\, and also mathematical logic. Perhaps surprisingly\, many of the classi
 fications in the SCI hierarchy do not depend on the model of computation u
 sed (e.g. BSS\, Turing) and in some sense the hierarchy seeks to bridge th
 e gap between numerical analysts (who deal with the continuum) and compute
 r scientists (who deal with the discrete). Informally we classify the numb
 er of successive limits (SCI index) of algorithms needed to solve a proble
 m.\nThe study of the non-computable is needed for several reasons. It is c
 rucial in the field of rigorous numerical analysis and in fact many everyd
 ay problems turn out to be not computable. Moreover\, the SCI hierarchy he
 lps classifying problems suitable for computer assisted proofs. In particu
 lar\, undecidable or non-computable problems are used in computer assisted
  proofs\, where the recent example of the resolution of Kepler's conjectur
 e (Hilbert's 18th problem) is a striking example. However\, only certain c
 lasses of non-computable problems can be used in computer assisted proofs\
 , and the SCI hierarchy helps detecting such classes. Finally\, the constr
 uction of several limits of algorithms can help tell us what information w
 ithin the problem is needed to lower the index and provide a numerical pro
 cedure.\nThe SCI hierarchy allows for solving the long standing computatio
 nal spectral problem\, and reveals potential surprises. For example\, the 
 problem of computing spectra of compact operators\, for which the method h
 as been known for decades\, is strictly harder than the problem of computi
 ng spectra of Schrodinger operators with bounded potentials\, which has be
 en open for more than half a century. We provide an algorithm for the latt
 er problem\, thus finally resolving this issue. We also provide the first 
 algorithm that can compute spectra without spectral pollution. The method 
 also provides error control on the output and we provide cutting edge nume
 rical examples showing it to be competitive with state of the art methods 
 (which do not converge in general). The SCI hierarchy also allows one to p
 rove that detecting the problem of spectral pollution is strictly harder t
 han computing the spectrum itself. Other problems such as point spectra\, 
 and fractal dimension of spectra will also be discussed. These problems ar
 e samples of what is likely to be a very rich classification theory.
LOCATION:MR14\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR