Assignment #4: Iterative Solvers for Linear Systems
Due: Friday, April 5, 1996

:

:

• Most of these problems illustrate different features of the iterative algorithms for solving linear systems of equations. The main examples are taken from the finite difference discretization of an ordinary differential equation (it's also a finite element discretization of the same problem).
• A few of the problems consider possible generalizations of the general theory of iterative solvers.
• The third type of problem is related to conjugate gradient methods.

On June 25, 1985, at the 11th Dundee Biennial Conference on Numerical Analysis, Nick Trefethen, now at Cornell University, and Peter Alfeld of the University of Utah made a bet:

L.N. Trefethen hereby bets Peter Alfeld that by 31 December 1994, a method will have been found to solve Ax=b (an ) linear system of equations) in operations for any . Numerical stability is not required. The winner get $100 from the loser.

The bet was witnessed by Per Erik Koch and Syvert Paul Nørsett.

Trefethen has informed SIAM News that as the best known exponent for linear algebra problems in 2.376, thanks to an algorithm developed by Coppersmith and Winograd in 1987, he has lost the bet and sent a check for $100 to Alfeld. (The year's delay in paying up, he says, is simply a result of faulty memory of the expiration date.) ``I'm still optimistic about the future,'' Trefethen claims, to which Alfeld replies, ``I believe it can't be done, and I challenge you to re-enter the bet for another ten years!''

Trefethen and Alfeld wish to inform SIAM News readers that their bet is hereby renewed and that another $100 will change hands on January 1, 2006.

-- SIAM News, March 1996, p. 6

• About this document ...