Moore's law squared

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:

A brief note on Moore’s law

Tagged with:
Posted in Computing
7 comments on “Moore's law squared
  1. Dan says:

    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…

  2. John says:

    Just a coincidence. I’m no relation to William Cook as far as I know.

  3. 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!

  4. John says:

    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.)

  5. fbahr says:

    Martin Grötschel even stated that progress in algorithms beats Moore’s Law [cf 1="" language="."][/cf]. PS: And don’t miss Brian Borchers’ comment on this post >

  6. TallDave says:

    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.

8 Pings/Trackbacks for "Moore's law squared"
  1. [...] 1. Moore’s law squared? [...]

  2. [...] Moore’s law squared Queste cose si sanno, magari non ci si pensano ma si sanno. Però a me fanno impressinone, tanta da non potersi dire: è quella che mi spinge a postare il link ::: The Endeavour [...]

  3. [...] top law-enforcement officer. A model that might have taken a year to solve 10 years ago can now solve in less than 30 seconds. Of course, any muppet with a word processor can publish a digital book but Apple could be [...]

  4. [...] The Race Against the Machine [...]

  5. [...] posts contrasting the macro performance improvements in numerical optimization see Noam Nisan and John Cook, It probably makes sense to bookmark Nisan’s blog  Turing’s Invisible Hand long term [...]

  6. [...] Moore’s law squared [...]