Berkeley Lab's Math Department Crosses, Stretches Boundaries
June 23, 1997
When it comes to boundaries, Berkeley Lab’s Mathematics Department usually straddles them, often blurs them and frequently stretches them to new levels.
For example, the group has one foot planted firmly on the Hill in the Computing Sciences organization and the other on the UC Berkeley campus.
The nature of the math department’s work comes down firmly in both the camps of mathematics and scientific computing. And in carrying out their applied math research, members of the department regularly cross back and forth from the theoretical to the very practical side. The group’s staff also covers a wide range, being made up of Lab scientists, UC professors, post-docs, graudate students and visiting members.
Finally, the tangible results of their work done on large-scale scientific problems are often translated into applications to improve day-to-day processes as internal combustion, medical imaging and manufacturing.
The Department of Energy’s Mathematical, Information and Computational Sciences Division has determined that many energy-related scientific questions are either too difficult, too dangerous or too expensive to tackle exclusively through experimentation. Instead, computer simulations can be used to generate much of the desired data. To get there, scientists rely on algorithms — mathematical formulae designed to solve complex problems. That’s where the Lab’s Mathematics Department figures into the equation.
“Our focus is often on cracking the hardest problems,” says James Sethian, head of the department. “The work we do is often driven by fundamental questions and the need for algorithms to study problems in fluid mechanics, material science and quantum mechanics. This leads to applications ranging from robotics to plastics and polymers, semiconductor manufacturing to image processing.”
According to Sethian, many of the most interesting — and challenging — problems occur at boundaries, or interfaces. For instance, turbulence is one of the hardest problems to solve in physics, Sethian says because of the constant and erratic changes. The most interesting physics of turbulence, as well as other scientific problems, occur at the interfaces between affected materials.
One section of the Mathematics Department, and much of Sethian’s own work, touches on these interfaces and their propagation. Research in this area leads into such fields as meteorology, mixing of materials, movement of pollutants and flame propagation and combustion. Combustion research offers a number of problems, including flame stability, swirling fluids, ignition and dispersion. Not surprisingly, Sethian points to a boundary — the one between burned and unburnt materials — as an area where the mathematics group and Sethian himself have applied their talents.
Unhappy with existing algorithms for analyzing combustion, Sethian and others set out to find better ways to track precisely what happens when fuel and oxygen are mixed, compressed and ignited. A better approach was found not in conventional numerical analysis, but in differential geometry (numerical schemes for compressible gas dynamics), specifically the theory of partial differential equations.
“Most of the time, algorithms come from the existing body of knowledge,” Sethian said. “In our group, our hallmark is to involve a spectrum of topics, from pure math to physics modeling and scientific computing to come up with new algorithms. We’re very attuned to what works — and what doesn’t work — in the world of scientific computing.”
One of the algorithms that has gained much attention are the “Level Set Methods” developed by Sethian and others over the past 15 years. Not surprisingly, the level set methods are algorithms designed to accurately and efficiently track the evolution of a propagating interface. Although such interfaces can be found in such familiar settings as a cold drink with melting ice cubes or waves breaking on a beach, Sethian offers the examples of medical imaging, semiconductor manufacturing and robotic navigation as applications where the Level Set Methods can have a profound effect.
Level set methods can be used to find interface solutions in either two or three dimensions. In an xy plane, the interface is a simple, closed curve (a loop that doesn’t cross over itself). In three dimensions, the interface is a closed surface. In either case, the interface propagates by moving in the normal direction at each point.
According to Sethian, most numerical techniques rely on markers, which try to track the motion of the boundary by breaking it up into buoys that are connected by pieces of rope. The idea is to move each buoy along with the changing interface, and rely on the connecting ropes to track the interface in a hopefully accurate manner.
Unfortunately, he explains, things get pretty dicey if the buoys try to cross over themselves, or if the shape tries to break into two; in these cases, it is very hard to keep the connecting ropes organized. In three dimensions, following a surface like a breaking ocean wave is particularly tough.
Rather than follow the interface as it propagates, the level set approach instead takes the original curve and treats it as a surface. As the interface moves over time, so does the set of points defining that surface. The interface is then identified by the set of points at a single level (imagine using a saw to slice out one level segment of a three dimensional object), hence the “level set” name.
Here’s how Sethian describes the method: “Think of the level set function as a topographic hiking map that gives surface elevations. The level set methods use a map on which sea level always corresponds to the edge (or edges) of the tracked interface, with oceans inside the boundary and mountains outside the boundary.
“We must figure out how to the change the height of the surface in time to match the evolution of the interface. The objective is to let the level set function expand, rise and fall — essentially doing all the work — so that we can find out where the interface is at any time by simply cutting the surface at zero height.”
While it might seem crazy to take the problem of a moving curve and trade it in for a moving surface, Sethian says, the approach is valuable because the level set will always be "nice" and mathematically well behaved, while the moving front can get wildly contorted.
“For once, a sports analogy is a very good way to explain a complex situation,” Sethian said. “The buoy, or marker particle, methods are like man-to-man coverage in basketball, while level set methods are a zone defense. It’s more effective and more efficient.”
Level set methods also provide researchers with a common language to solve a wide range of interface problems. In an article published in the May-June 1997 issue of “American Scientist,” Sethian explains how the level set methods can aid robotic navigation, medical imaging and electronics manufacturing.
The key to robotic navigation is finding the shortest route within various constraints, a problem easily solved by level sets. Sethian uses an example of moving across a parking lot dotted with patches of ice and parked cars. In such a situation, a straight path may not be the fastest. By allowing the propagating interface to move at different speeds (i.e. faster over clear areas, slower over ice and stopping at cars), and tracing the route backwards from the end point, the shortest route can be determined. Sethian likes to demonstrate the viability of the model by making the problem more complex—giving the person navigating the lot a ladder to maneuver through the obstacles.
Level set methods can also make it easier for non-experts to read medical images, such as those produced by X-rays and magnetic-resonance imaging. Such images often contain lot of “noise,” or non-essential data. A level set approach can be used, with the speed of the propagating front adjusted by changes in the density of the image. Such density changes indicate boundaries, the edge of an artery imaged in an angiogram, for example.
Finally, level set methods could be used to improve the manufacture of components for computers on which the algorithms are run. Manufacturing integrated circuits involves the cutting and shaping of silicon wafers. As components get smaller and computers more powerful, this process becomes even more precise — and expensive. Tracking the profile of these silicon components to ensure they meet specifications is a problem that can be addressed with level sets, Sethian says.
The current applications are the latest stage in the evolution that began in 1982. Through the rest of the decade, Sethian and others refined the level set methods and looked for areas where the algorithms could be put to use. In the 1990s, the group has been applying the methods to different areas, such as those described above.
But the Mathematics Department doesn’t actually produce the software applications of the algorithm. Rather, the results of the work is published in the public domain for use by anyone.
“You can put our work in context by understanding our philosophy — we invent new algorithms, build prototypes and then work to get it out there and working in the real world,” Sethian said. “To do this, we’re constantly refining and advancing our techniques.”
About Computing Sciences at Berkeley Lab
The Computing Sciences Area at Lawrence Berkeley National Laboratory provides the computing and networking resources and expertise critical to advancing Department of Energy Office of Science research missions: developing new energy sources, improving energy efficiency, developing new materials, and increasing our understanding of ourselves, our world, and our universe.
Founded in 1931 on the belief that the biggest scientific challenges are best addressed by teams, Lawrence Berkeley National Laboratory and its scientists have been recognized with 13 Nobel Prizes. Today, Berkeley Lab researchers develop sustainable energy and environmental solutions, create useful new materials, advance the frontiers of computing, and probe the mysteries of life, matter, and the universe. Scientists from around the world rely on the Lab’s facilities for their own discovery science. Berkeley Lab is a multiprogram national laboratory, managed by the University of California for the U.S. Department of Energy’s Office of Science.
DOE’s Office of Science is the single largest supporter of basic research in the physical sciences in the United States, and is working to address some of the most pressing challenges of our time. For more information, please visit energy.gov/science.