Mathematics Colloquium

Gaussian Elimination as an Iterative Algorithm

Speaker: Lloyd N. Trefethen, Oxford University

Location: Warren Weaver Hall 1302

Date: Monday, December 10, 2012, 3:45 p.m.

Synopsis:

Numerical linear algebra relies on "direct" algorithms, which finish in finite time, and "iterative" ones, which converge toward the solution but may never reach it.

Conjugate gradients, introduced in 1952, is the archetypical iterative algorithm, a core tool of computational science. Yet for the first twenty years of its life, it was generally regarded as a direct algorithm.

Gaussian elimination, whose roots are in antiquity, is the archetypical direct algorithm. Yet this algorithm too can be regarded as an iterative one, in which a general matrix is approximated successively by matrices of rank 1,2,3,.... In recent years this aspect of the elimination process has become important for applications. This talk will review the mathematics and the history, with particular attention to the challenging application of extending Chebfun to higher dimensions, where a continuous analogue of iterative Gaussian elimination comes into play (joint work with Alex Townsend).