In a review of linear programming solvers from 1987 to 2002, Bob Bixby says that solvers benefited as much from algorithm improvements as from Moore’s law.
Three orders of magnitude in machine speed and three orders of magnitude in algorithmic speed add up to six orders of magnitude in solving power. A model that might have taken a year to solve 10 years ago can now solve in less than 30 seconds.
Source: In Pursuit of the Traveling Salesman
Related post:
{ 7 trackbacks }
{ 7 comments… read them below or add one }
Dan 01.01.12 at 18:10
John – any relation to author William Cook, or just a coincidence?
Author is a math professor with the last name “Cook”… sounds familar for some reason…
John 01.01.12 at 18:18
Just a coincidence. I’m no relation to William Cook as far as I know.
gwern 01.01.12 at 18:51
An Amazon link? One can do better than that: http://www.gwern.net/Aria%27s%20past,%20present,%20and%20future#fn3
Peter Grogono 01.02.12 at 07:04
Unfortunately, I do not remember the details, but some years ago I read a piece about the development of some algorithm (FFT?) from the 40s to the 90s. The improvement factors were about 10^6 for hardware and 10^6 for software, or 10^12 overall. If I can find the reference, I will post it. Best for 2012!
John 01.02.12 at 07:37
Peter, I’ve seen something similar for numerical linear algebra, but I can’t find the reference either. This overlaps with Bixby’s observation, since much of the improvement in LP solvers came from advances in linear algebra.
These kind of comparisons implicitly depend on a certain problem size. For example, if you improve an algorithm from O(N^3) to O(N^2), the amount of increase in speed depends on the problem size N. Hardware improvements speed up all methods more or less uniformly(*). But it’s safe to say that for sufficiently large linear systems with exploitable structure, algorithms have contributed more than hardware to solution speed.
(Hardware improvements might not benefit all methods quite the same since some parts of hardware, e.g. CPU, have improved at a faster rate than others, e.g. memory. But since we’re waving our hands here anyway, we can assume that Moore’s law has been a rising tide that lifts all boats roughly the same amount.)
fbahr 01.04.12 at 17:39
Martin Grötschel even stated that progress in algorithms beats Moore’s Law [/cf]. PS: And don’t miss Brian Borchers’ comment on this post > http://agtb.wordpress.com/2010/12/23/progress-in-algorithms-beats-moore%E2%80%99s-law/#comment-4099
TallDave 01.05.12 at 11:46
Yes, as a programmer I’ve noted before that the Singularity will bootstrap not no much when machines start designing better machines, as when algorithms start writing better algorithms.