Contrarian Minds: Bill Walster

The mother of all paradigm shifts.

By Al Riske

27.May.04--Sometimes the best way to start a complicated story is with a simple statement, so here goes. Computers do lousy math.

That's a bit shocking to those of us who always thought computers were better at arithmetic than we were, but it's true. Computers routinely round off fractions, so you get inaccurate results.

No big deal. Rounding errors are small, right? Not if you're trying to intercept an incoming missile. Then a tiny miscalculation -- a single rounding error compounded over time -- can be fatal.

Most people see these computing errors as regrettable (and sometimes tragic) but also inevitable, despite some clever workarounds designed to catch errors. Not Bill Walster.

The Sun research engineer wants to replace the flawed floating-point math of today's computers with something called interval arithmetic. It's so accurate, Walster says, that computer simulations using this technique could reduce, and one day even eliminate, the need for independent physical verification.

No more crash-test dummies? That's putting a lot of trust in your results. For Walster, it's just a glimpse of where interval arithmetic could take us.

"Computing with intervals is as big a paradigm shift in computing, science, and technology -- and even in mathematics -- as has ever occurred in these fields," he says.

Essentially, intervals trap the right answer within a set of possible values. This prevents inaccuracies from going unnoticed and snowballing out of control.

"If you can prove mathematically the right answer is between this answer and that answer, you can restore mathematical rigor to computing," says John Gustafson, a Sun principal investigator working on the DARPA-funded supercomputer project.

The DARPA project is also Walster's chief focus these days.

"Computing with intervals is the only approach that lets you reliably scale up some parallel computations to 100,000 processors and beyond," he says. "You can't get there with floating-point arithmetic alone."

Why not?

"With floating-point, you sometimes get different answers on parallel machines, because the order in which floating-point operations are performed matters. When this happens, you don't know whether the differences in successive runs of the same problem are due to rounding and its consequences, or the result of a software error or a hardware flaw," Walster says.

"With intervals, I am guaranteed that the value I'm computing is contained in the interval result. It's a mathematical guarantee, a numerical proof."

The details of interval arithmetic are difficult to explain to the untrained, and even some highly trained people simply refuse to listen. "That's impossible," they say. "Can't be done."

Walster, a truly persistent contrarian, has been battling this perception for years -- even at Sun, a company that generally nurtures contrarian ideas. He takes comfort in the fact that history is replete with cases -- Galileo, Pasteur, Lister -- where paradigm shifts were greeted with hostility.

"This is the kind of thing we're talking about -- the visceral reaction people have to something that's really new," Walster says.

Are intervals really on the same scale of importance as these other paradigm shifts? Time will tell. Walster believes they are and is working to validate his belief.

"I call intervals the mother of all paradigm shifts," he says. "Not only are they a paradigm shift in computing, applied mathematics, and numerical analysis, but they might also create paradigm shifts in physics, chemistry, biology, the life sciences, and cosmology."

Walster didn't invent interval arithmetic. That distinction goes to Ramon E. Moore, who came up with the concept back in 1957. But Walster has contributed to it.

"Interval analysis, the way Moore formulated it, starts with real numbers and defines intervals in terms of them. As a consequence, Moore inherited the limitation of real arithmetic. No division by zero," Walster says.

A former university professor, steeped in theorems, postulates, and corollaries, Walster advanced the study of intervals with a key concept: set theory.

"If you lay the foundation for interval arithmetic, not on real numbers, but on sets -- set theory -- then, since an interval is a set, you can develop a closed system in which there are no undefined computations," he says.

If you were able to follow that, you might want to pick up a copy of Global Optimization Using Interval Analysis, the book Walster coauthored with Eldon Hansen, a longtime associate from his days at Lockheed. It spells out the details of containment set theory and much more.

The thing about intervals that excites Walster most is the ability to solve problems thought to be unsolvable.

"Many people continue to believe that it is impossible to numerically solve nonlinear problems," he says. "Not true. You can with intervals."

Walster says Hansen was the first to figure out how to use the fundamental theorem of interval analysis to solve nonlinear optimization problems.

"The design of anything -- a connecting rod or a valve spring or a supercomputer -- is an optimization problem. You're trying to do as good as you can at something," Walster says. "To complicate matters, you also typically have constraints -- a heat constraint, a weight constraint, a power constraint, and/or a cost constraint -- that you can't violate."

So, given a particular design problem, whether it's on a circuit board, power plant, or turbine blade, how do you find the best design?

"People have argued that this problem is, in principle, numerically unsolvable on a computer," Walster points out. The reason: "If what you're looking for is not representable, like pi (an infinite sequence of digits), then you're prevented from getting to it on a finite machine."

However, with intervals, the right answer is always captured within a machine-representable interval, he says.

"The trick," Walster says, "is to develop fast interval algorithms that narrow the width of computed intervals to produce the degree of accuracy needed to solve real problems."

While the inner workings of interval arithmetic are beyond the scope of this article, we can be sure of this much: Intervals work -- amazingly well. Walster uses fighter jets as a real example.

"You don't want the pilot to punch the throttle and have the engine flame out," he says, "so you have a whole set of electronics to monitor everything and not allow things to happen that will damage the engine or cause it to lose power."

The trouble is the feedback loops on all those electronics can sometimes "go chaotic," as Walster puts it. So to avoid disaster, the underlying control algorithms need to be robust.

"With intervals you can prove they're robust," Walster says.

In this example, more accurate equipment can mean safer planes for pilots.

"One F-16 control mechanism was altitude sensitive, so they originally had three different non-interval algorithms, derived heuristically. Trial and error. This one worked from 0 to 10,000 feet, the next one from 10,000 to 20,000 feet, and the third one from 20,000 to 30,000 feet," Walster says. "Then, in India, they developed an interval algorithm -- one algorithm for the full altitude range -- and at every altitude it was better than the other three."

Imagine the implications of this one example for product liability alone. Should a product fail and injure someone, the plaintiffs lawyer will want to know how it was designed -- using flawed floating-point arithmetic or demonstrably superior, commercially available interval analysis?

With intervals, Walster says, "Sun has at least as big an opportunity to gain a technological advantage as any company has ever had in history of science and technology. Period."

"Intervals have the potential to change the rules of the computing game," he says. "The new rules are: 'All your floating-point speed doesn't count any more. It's just not relevant. The only speed that matters is interval speed."