Harnessed Computers Crack Math Puzzle

Jocelyn is a staff writer for Science magazine.

Another devilishly hard computational problem has cracked under the coordinated assault of computers linked by the Internet. The alliance of 2500-some computer processors took just a week to solve "nug30," a problem that had resisted mathematicians' best efforts for 3 decades.

So-called distributed computing has already become a popular alternative to fighting for time on a supercomputer for some researchers. Perhaps the best known example is SETI@home, in which volunteers' PCs comb tiny chunks of data for radio signals from alien life. It was another collaborative effort, called MetaNEOS, that tackled the nug30 quadratic assignment problem. First posed in 1968, nug30 is an optimization problem--akin to the traveling salesman problem where someone tries to visit the state capitals while putting the minimum number of miles on his car.

The MetaNEOS team, based at Argonne National Laboratory in Illinois, solved nug30 in 7 days in June, using up to 1009 processors simultaneously at eight institutions to crunch the numbers. The feat marks perhaps the biggest distributed computing success yet outside of special demos or applications, says participant Miron Livny of the University of Wisconsin, Madison. The 96,000-CPU-hour problem could have been completed as quickly on a 1000-node supercomputer--but only if you could win time on one, says Livny. His goal "is to allow every scientist to do an order of magnitude more computing than they do today."

Related sites
The MetaNEOS Project
SETI@home

Posted in Math