It's only fair that a puzzle have only one solution, right? That's the great thing about a crossword or one of those Sudoku number games that the lifestyle pages can't stop talking about right now. There's only one way to fill in the boxes and get a complete answer.

Well, nobody said science was always fair. In what are known as ill-posed problems, there is no unique solution. A slight change in the data fed into the system of functions that rule a given ill-posed problem can produce a large, unpredictable change in the results.

“In the late 1800s, a scientist named Hadamard proposed that ill-posed problems didn't exist [or those that did weren't scientifically significant]. He was totally wrong. They're everywhere,” says Rebecca Hartman-Baker, who recently completed her PhD in computer science at the University of Illinois at Urbana-Champaign.

They're found, for example, in medical imaging, financial modeling, environmental modeling, and astronomy. Though Hartman-Baker's PhD thesis focused on an ill-posed problem found in the field of geoprospecting, the approach applies to any of those fields.

“Any ill-posed problem for which you have an educated guess of where to start could use this,” says Hartman-Baker, now a post-doc at Oak Ridge National Laboratory. “As a scientific computing type, the thing that brings me the most joy is to contribute to real-world scientific problems through my little thing. I want to get people who didn't know they needed to be involved in computer science to be in it.”

Making hundreds of runs on NCSA's Platinum and Tungsten clusters, she developed a selection method for choosing the parameters that go into the problem and an optimization method for finding the ideal result among a sea of solutions.

Geoprospecting typically involves placing transmitters and receivers deep in the earth. The transmitter projects electromagnetic energy, or in some cases sound, that is picked up by the receiver miles away. The electromagnetic energy is altered in transit, based on the conductivity of the rock, water, oil, or other materials in the ground. From the data collected by the receiver, researchers can deduce what lies between it and the transmitter.

The challenge is — and this is where the ill-posed problem comes in — that different sizes, shapes, and orientations of underground deposits can produce the same data profile.

“Basically, you're trying to find the size and shape of an ellipse [that represents the deposit that a geoprospector might be targeting, such as oil]. Where the center is at. The rotation or orientation. How you do that is really indirect — kinda backhanded,” Hartman-Baker says.

The traditional method of solving this sort of ill-posed problem, known as Tikhonov regularization, gives a blurry picture of this ellipse. It stabilizes the problem around a single solution by adding things like smoothness constraints to the functions. But in situations like this, researchers tend to prefer distinct boundaries. To get these boundaries, Hartman-Baker proposed another class of stabilizing, known as selection methods. With selection methods, the solution is limited to some reasonable set of possible solutions, and the parameters fed into the problem are reduced to a manageable number (about 10 in the case of Hartman-Baker's work). These decisions limit the computational expense of solving the problem and provide a distinct ellipse.

“We're bringing selection methods back into the world. People have forgotten about them,” she says. In her numerous runs on NCSA's systems, she tested the viability of the approximate quasisolution method.

The selection method reduces the number of parameters and shrinks the size of the solution space, but the optimal solution still has to be found. To do so, researchers make an educated guess of the input that will produce the optimal solution, run a simulation using that input, and compare the output to real-world data. They repeat the process until they find the input that most closely resembles the real-world output. In the example used by Hartman-Baker, that reveals the shape of the ellipse that produces the output.

To find the output that most closely resembled the real world, Hartman-Baker's example required finding the global minimum for a system of mathematical functions. After again trying several different methods, she settled on the diffusion equation method (DEM), which finds local minima and then traces back through a series of those local minima to the global minimum. Hartman-Baker compares this process to finding the lowest point in Kentucky. It's easy to find the lowest point in a region; you just head downhill until you are forced to start uphill again. But there are a lot of regional low points spread about, so ensuring that you've found the lowest of the low is no small task. DEM blurs the function “so that at first you just see overall trends, but not all the details. Then as it progresses, you unblur the function more and more until the full features [of the global minimum that you homed in on] are visible,” she explains.

As part of her thesis work and again using time at NCSA, Hartman-Baker discretized this involved method so that it can be parallelized and can use multiple processors at the same time. Currently, the evaluation of a function can be run on eight processors and takes about a minute. This has to be done several thousand times to solve a single optimization problem in geoprospecting.

This research was supported by the National Computational Science Alliance and, more recently, the UIUC computer science department's Fulton Watson Copp Endowed Chair held by Professor Michael Heath.

—–

Source: Access Online, NCSA