BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Cambridge Analysts' Knowledge Exchange
SUMMARY:The Computational Spectral Problem and a New Class
ification Theory: Novel Algorithms\, Impossibility
Results and Computer Assisted Proofs - Matthew Co
lbrook (University of Cambridge)
DTSTART;TZID=Europe/London:20181024T160000
DTEND;TZID=Europe/London:20181024T170000
UID:TALK113005AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/113005
DESCRIPTION:We will discuss and extend the Solvability Complex
ity Index (SCI) hierarchy\, which is a classificat
ion hierarchy for all types of problems in computa
tional mathematics that allows for classifications
determining the boundaries of what computers can
achieve in scientific computing. The SCI hierarchy
captures many key computational issues in the his
tory of mathematics including Smale's problem on t
he existence of iterative generally convergent alg
orithm for polynomial root\, the computational spe
ctral problem\, inverse problems\, optimisation\,
numerical solution of PDEs etc.\, and also mathema
tical logic. Perhaps surprisingly\, many of the cl
assifications in the SCI hierarchy do not depend o
n the model of computation used (e.g. BSS\, Turing
) and in some sense the hierarchy seeks to bridge
the gap between numerical analysts (who deal with
the continuum) and computer scientists (who deal w
ith the discrete). Informally we classify the numb
er of successive limits (SCI index) of algorithms
needed to solve a problem.\nThe study of the non-c
omputable is needed for several reasons. It is cru
cial in the field of rigorous numerical analysis a
nd in fact many everyday problems turn out to be n
ot computable. Moreover\, the SCI hierarchy helps
classifying problems suitable for computer assiste
d proofs. In particular\, undecidable or non-compu
table problems are used in computer assisted proof
s\, where the recent example of the resolution of
Kepler's conjecture (Hilbert's 18th problem) is a
striking example. However\, only certain classes o
f non-computable problems can be used in computer
assisted proofs\, and the SCI hierarchy helps dete
cting such classes. Finally\, the construction of
several limits of algorithms can help tell us what
information within the problem is needed to lower
the index and provide a numerical procedure.\nThe
SCI hierarchy allows for solving the long standin
g computational spectral problem\, and reveals pot
ential surprises. For example\, the problem of com
puting spectra of compact operators\, for which th
e method has been known for decades\, is strictly
harder than the problem of computing spectra of Sc
hrodinger operators with bounded potentials\, whic
h has been open for more than half a century. We p
rovide an algorithm for the latter problem\, thus
finally resolving this issue. We also provide the
first algorithm that can compute spectra without s
pectral pollution. The method also provides error
control on the output and we provide cutting edge
numerical examples showing it to be competitive wi
th state of the art methods (which do not converge
in general). The SCI hierarchy also allows one to
prove that detecting the problem of spectral poll
ution is strictly harder than computing the spectr
um itself. Other problems such as point spectra\,
and fractal dimension of spectra will also be disc
ussed. These problems are samples of what is likel
y to be a very rich classification theory.
LOCATION:MR14\, Centre for Mathematical Sciences
CONTACT:Simon Becker
END:VEVENT
END:VCALENDAR