A parallel path for speedy solutions.

A parallel path for speedy solutions

Meteorologists sometimes joke that it takes three days of computer time to figure out tomorrow's weather. The equations are so complicated that a long sequence of computations is needed to come up with an accurate forecast. But the time required to solve such equations may be shortened with the recent invention of a simple method that, with the right kind of computer, substantially speeds up the process.

The new algorithm, developed by mathematicians Victor Pan of the State University of New York at Albany and John Reif of Harvard University, involves solving systems of linear equations. The simplest such system consists of two equations, each expressed in terms of two variables, x and y. Solving this system requires finding values for x and y that satisfy both equations at the same time. Linear systems that arise in weather forecasting, aerodynamic design or economic modeling often involve thousands of equations and thousands of variables.

Efficient computer methods already exist for finding solutions to these equations, but the size of many linear systems overwhelms computers that must perform each step in order, one at a time. The answer is to divide and conquer --by using a multiprocessor computer that simultaneously performs many computations in parallel. Pan and Reif found a method that, by taking advantage of parallel processing, reaches the answer in less time.

Their method involves systems of linear equations expressed as blocks of numbers called matrices. Each matrix has as many rows as there are equations and an equal number of columns. Solving the equations is equivalent practically to finding the inverse of the original matrix.

But finding a matrix inverse is a thorny problem. The key discovery was an efficient way of computing an "approximate matrix inverse,' which is used as a starting point for an interative method that, step by step, brings the approximate matrix closer to the "true' answer.

What surprises Pan and Reif is how simple the scheme turns out to be. The basic method had been discovered about 50 years earlier, but until they came along, no one knew of a simple way to find an approximate matrix inverse.

"It was the missing step that we didn't know how to do before,' says computer scientist Ronald L. Rivest of the Massachusetts Institute of Technology. "It was an exciting, nice result.'

With only one computer processor, the method the mathematicians developed is about as speedy as any algorithm now available. But as the number of processors used increases, their method proves to be significantly faster. For a system of n linear equations, the algorithm is at its best when n3 processors are used. Although very few computers now available have a sufficiently large number of parallel processors, within the next few years several companies are planning to introduce machines with as many as 64,000 processors.

In addition, Pan and Reif developed a faster way of handling "sparse' matrices, in which most of the numbers are zeros. Almost all systems of linear equations encountered in fluid dynamics or other physical situations generate matrices of this type. Their new algorithm helps because several steps involve computing matrix inversions.

Recently, Pan and Reif also found that their algorithm for matrix inversion may be useful in speeding up some of the steps in a new linear programming method developed by Narendra Karmarkar of AT&T Bell Labs in Murray Hill, N.J. (SN: 12/22 & 29/84, p. 408). This improvement could give Karmarkar's algorithm a decided edge among the competing methods used to solve these problems.

With the theoretical work done, it's now up to computer programmers to implement and test the Pan-Reif algorithm. "I don't see any practical problems for implementation because the code is very simple,' says Pan. "Most of the complications in the work were to find it and to justify it, to prove things.'