Digging up FOSLS

If you’ve ever unknotted a gnarled garden hose to let water flow freely, you may have an elementary feeling for Tom Manteuffel’s job. Manteuffel, a University of Colorado professor, and his fellow applied mathematicians unravel complex equations, making them easier for computers to solve.

The technique, called first-order system least-squares (FOSLS), can help accelerate computer simulations of physical phenomena. In one case, FOSLS, combined with a high-speed solution technique, ran a computer simulation of blood flowing through vessels significantly faster than a commercial computer code.

FOSLS could make faster, better models of cardiovascular systems so medical device companies can do tests more cheaply and quickly than they can when using human or animal subjects.  Surgeons could develop better techniques without actually operating.

FOSLS itself, however, is not a computer application, but a tool with broad uses.

“We’re developing a methodology for approaching a wide variety of applications and computing a solution more effectively and efficiently – and that includes not just computer time, but human time,” Manteuffel says.

It all starts with partial differential equations (PDEs).  These complex formulas describe continuous processes that are distributed in space and time, such as fluid flow, electrodynamics, and the propagation of heat or sound.

PDEs are the core of many computer simulations.  But computers can’t solve PDEs until the equations are converted to systems of algebraic equations.  In essence, mathematicians must convert models of continuous processes – such as waves – into equations describing a series of discrete points a digital computer can calculate.

‘We’re not interested in making a pretty equation on the wall. We’re interested in solving something on the computer.’

PDEs involve derivatives – mathematical expressions describing the rate of change of a quantity. “If I know the distance an object travels over time, its velocity is the first derivative,” Manteuffel says. “Acceleration is the second derivative.”

“We try to write almost all these physical models as a system of equations only involving first derivatives,” he adds – thus, a first-order system.

Many applications start that way, but mathematicians looking for a simple way to write complex equations often used higher-order derivatives – second, third and beyond, Manteuffel says.  “Sometimes equations got all tied up in knots,” he adds.

“We’re unraveling them back. We’re saying we’re going to write them back as first-order because we’re not interested in making a pretty equation on the wall. We’re interested in solving something on the computer.”

Reducing PDEs to first-order systems makes them easier to solve using a fast solution technique called multigrid methods.

“What we’ve been doing is recasting partial differential equations in a way that the … systems that result are amenable to this very fast solution technique” on massively parallel high-performance computers, Manteuffel says.

“We’re changing things over here so when they come out the bottom you have a solution technique that will solve them rapidly.”

Manteuffel’s group, working with a doctor at Children’s Hospital in Denver, used FOSLS and multigrid methods to run computer models of blood flow.  In one case, they compared their method with a commercial computational fluid dynamics code.

The commercial code took a little over an hour to run one blood flow model. When the size of the problem doubled, the computing time tripled.

The FOSLS-multigrid solver took about 42 minutes to solve the simple model.  When the problem size doubled, computing time also doubled.  That’s an indication of the method’s efficiency, because computing time increased at the same rate as the problem’s size.

That’s called linear growth.  Solution techniques are “optimal” if their computing time grows linearly as problems get bigger in size – and they always get bigger, either because there is more to model or because more accuracy is required.

Manteuffel has worked with other researchers to apply FOSLS to a computer model of surgery to correct a congenital heart defect.  The model could make the operation more effective, giving patients a better life.

They’ve also worked on a “virtual eye” to better understand the pressure increase that causes glaucoma.  Manteuffel and his fellow researchers are still working.  They want to make multigrid methods adaptive, so they’re applicable to a wider variety of problems.

“So far, we’ve been very pleased to be able to solve problems we never thought we could in this very economical fashion,” he adds.