Peter Alfeld, --- Department of Mathematics, --- College of Science --- University of Utah

A Mathematical Bet between Peter Alfeld and Nick Trefethen

The note [image] (click to get a full picture) documents a bet Peter Alfeld made with Nick Trefethen on June 25, 1985. It reads:

25 June 1985

L.N. Trefethen hereby bets Peter Alfeld that by December 31, 1994, a method will have been found to solve Ax=b (n x n linear system of eqs) in O(n**(2+epsilon)) operations for any epsilon > 0. Numerical Stability is not required.

The winner gets $100.- from the loser. signed: Peter Alfeld, Lloyd N. Trefethen Witnesses: Per Erik Koch, S.P. Norsett.

Norsett added the note (This is an A-stable problem) .

Nick paid up in February 1996. We renewed the bet for another 10 years, and another $100 will change hands on January 1, 2006. On February 13, 1996, we amended the bet as follows: If one of the contestants settles the matter prior to January 1, 2006 (by Peter Alfeld showing that no O(n^2) method exists, or Nick Trefethen constructing an O(n^2) method) the loser will pay the winner $200 at that time.

The best known exponent for linear algebra problems is currently 2.376, thanks to an algorithm due to Coppersmith and Winograd in 1987.