Ames Laboratory,
Department of Energy,
ISU,
Ames, Iowa
Ames Laboratory,
Department of Energy,
ISU,
Ames, Iowa
Call it instinct, or call it intuition: it's that odd ability to deliberately cross circuits and produce a strange new spark.
The human mind has a knack for this process, for producing insights and ideas whose origins cannot be traced back to logical patterns of thought. The computer, on the other hand, isn't noted for such accomplishments. But by using the tremendous information processing abilities of today's most advanced supercomputers, Ames Lab researchers have developed a computer algorithm that can mimic achievements of this kind by human mathematicians.
The new algorithm has also reached beyond human accomplishments a time or two and may help researchers improve the tools they use to increase the efficiency of computer programs.
The Lab's algorithm searches for math shortcuts, methods that reduce the number of multiplications, additions or other operations necessary to solve a particular mathematical task.
"These shortcuts sometimes don't seem to proceed from any general theory, but instead jump into existence as recipes that work," says John Gustafson, an Ames Lab computational scientist and an Iowa State University (ISU) associate adjunct professor of computer science.
"Often, no one knows how people come up with tricks like these," continues Srinivas Aluru, a lab graduate assistant who worked with Gustafson on the Lab's new algorithm. "They may publish a paper describing their result, but what went through their brain is unknowable."
Gustafson felt that the incredible processing speeds of supercomputers might make it possible to imitate these bursts of human mathematical insight in a computer program. The key, he felt, was to program the computer to construct and investigate every possible shortcut for a given math problem, while giving the computer certain guidelines to prevent it from wasting time exploring hopeless or already tested possibilities.
Aluru explains that completely exploring the potential shortcuts for the simple problem of taking the square of one number, a, and subtracting the square of another number, b, makes it necessary for the computer to investigate 15,552 potential solutions.
"There were too many possibilities to explore, so we started to develop rules to eliminate certain expressions that definitely wouldn't get us to the answer," says Aluru.
Gustafson and Aluru developed two sets of rules for stopping the investigation of dead ends. Rules in the first group, known as the conservative pruning rules, are mathematically proven. Gustafson and Aluru are certain that these rules cannot eliminate a potentially valid shortcut.
Rules in the second set, known as the aggressive pruning rules, are not mathematically proven. "These aggressive rules are based on common sense, and we believe that they are correct, but we are not able to prove them as of now," explains Aluru.
For simpler math tasks where Gustafson and Aluru want to find definitive answers, they run the algorithm using only the conservative rules. To make investigations of more complicated math tasks possible, they give the computer both the conservative and the aggressive rules to work with, but sacrifice some of their ability to call their findings definitive.
Gustafson and Aluru first tested the algorithm on a classical math problem: developing the quickest routes to the powers of a number. For example, x4 to x100) in 1.5 minutes.
The researchers then applied the program to other, more complicated math problems. Included were finding the product of complex numbers, the cross-product of three-dimensional vectors, and the produce of two-by-two matrices.
For the vector problem, the computer found a new solution method. This new method trims the number of multiplications needed from six to five. The new method also increases the number of additions.
"But which would you rather do: multiply two fifteen-digit numbers or add them?" Gustafson asks, pointing out that multiplication often involves more work than addition.
After trying out and refining the new algorithm on increasingly complex problems, Gustafson and Aluru compared the algorithm's abilities to those of optimizing compilers. Compilers are software that transform a program from programming language into computer code; an optimizing compiler both transforms the program and tries to remove any unnecessary steps from it. It is designed to help a program run more quickly and efficiently.
"On many tasks, we can do twice as well as the best optimizers in the world," says Gustafson, who envisions parallel supercomputers devoted solely to the task of searching for programming shortcuts to be used on other computers.
As computer speeds increase, the algorithm will be able to handle more complex problems that can't be tackled now, problems that would tie up today's computers for years or even centuries.
The critical issue, according to Gustafson, is whether enough brute force is available in the form of computing power.
"At some point, enough speed starts to look like smarts," he concludes. "It's like the old question about monkeys and Shakespeare: if you lined up enough monkeys in front of typewriters and gave them enough time to bang away on them, wouldn't they eventually produce the entire works of Shakespeare? That's what we've started to do here. We've taught the monkeys some basic English, and we've lined enough of them up to produce the first line of Shakespeare."
Published by Inquiry, winter 1993
Contact:
John Gustafson
Gus@SCL.AmesLab.gov
The URL for this page is: http://www.scl.ameslab.gov/Publications/Inquiry/Inquiry,summer1993.html
Pages prepared by Maria E. Blanco.