![[image]](images/bet.gif)
(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.
[16-Aug-1996]