Infinite dimensional spectral computations and linear algebra: Extending the QR algorithm to infinite dimensions

Add to your list(s) Download to your calendar using vCal

• Matt Colbrook (University of Cambridge)
• Wednesday 30 May 2018, 16:00-17:00
• MR14, Centre for Mathematical Sciences.

If you have a question about this talk, please contact Andrew Celsus.

Spectral computations of infinite-dimensional operators are notoriously difficult, yet ubiquitous in the sciences. Indeed, despite more than half a century of research it is still unknown which classes of operators allow for computation of spectra and eigenvectors with convergence rates and error control. Recent progress in classifying the difficulty of spectral problems into complexity hierarchies has revealed that the most difficult spectral problems are so hard that one needs three limits in the computation and no convergence rates nor error control is possible. This begs the question: which classes of operators allow for computations with convergence rates and error control?

In finite dimensions, the QR algorithm seeks to calculate the eigenvalues and eigenvectors of a matrix. The basic idea is to perform a QR decomposition, writing the matrix as a product of an orthogonal matrix and an upper triangular matrix, multiply the factors in reverse order, and iterate. This algorithm has been hailed as one of the top ten influential algorithms of the 20th century and works exceedingly well in practice even though rigorous results for non-normal operators are scarce.

In this talk I shall extend the QR algorithm to infinite dimensions and discuss theorems on convergence to spectra and eigenvectors. The infinite dimensional case is more difficult for two reasons. First, the existence of essential spectra stops the algorithm computing all of the spectrum – it only computes the extremal parts. This is naturally understood through a link with power iterations. Second, it is impossible to use shifts to speed up convergence (this is crucial in the implementation of the finite dimensional case, increasing linear convergence to cubic convergence). Nevertheless, I shall link the QR algorithm to computational hierarchies, showing how it can solve/classify spectral problems and be executed on a finite machine. Numerical examples will also be demonstrated where it outperforms standard approaches that are notorious for providing false solutions. Finally, I shall discuss some exciting new developments for a cousin of the QR algorithm – the QL algorithm, which may help solve the shift problem. This talk is based on joint work with Anders Hansen.

This talk is part of the Cambridge Analysts' Knowledge Exchange series.

This talk is included in these lists:

• All CMS events
• CMS Events
• Cambridge Analysts' Knowledge Exchange
• DAMTP info aggregator
• Interested Talks
• MR14, Centre for Mathematical Sciences
• My seminars
• bld31

Note that ex-directory lists are not shown.