Algorithms in the Service of Science
John Bell and Phillip Colella, applied mathematicians at Lawrence Berkeley National Laboratory and long-time NERSC users, were named co-recipients of the 2003 SIAM/ACM Prize in Computational Science and Engineering, awarded by the Society for Industrial and Applied Mathematics (SIAM) and the Association for Computing Machinery (ACM).
According to SIAM President Mac Hyman, the prize “is awarded in the area of computational science in recognition of outstanding contributions to the development and use of mathematical and computational tools and methods for the solution of science and engineering problems.” This is the first year the prize has been awarded.
Algorithms developed by Bell, Colella and their research groups at Berkeley Lab are used for studying complex problems arising in fluid mechanics and computational physics. The mathematical concepts, models, and methods they have developed have been applied in such diverse areas as shock physics, turbulence, astrophysics, flow in porous media, and combustion.
Bell is head of the Center for Computational Sciences and Engineering (CCSE), while Colella heads the Applied Numerical Algorithms Group (ANAG), both within Berkeley Lab’s Computational Research Division. Both groups are participants in the SciDAC Applied Partial Differential Equations Center (APDEC).
In 2003, CCSE has been modeling turbulent reacting flow in methane flames, and applying some of the information gleaned in those experiments toward supernova research and modeling. ANAG has been involved in developing more sophisticated geometric tools for its Chombo software toolkit, and applying it in areas such as beam dynamics in accelerator designs, gas jets in laser-driven plasma-wakefield accelerators, simulations of fusion reactors, and biological cell modeling.
In order to deal with problems in such diverse and complex sciences, CCSE and ANAG create customized software components that are able to translate scientific ideas and empirical insights into precise, 3D models that can be represented on a computer. This involves computational research that bridges the gap between mathematical, physical and computational sciences. By breaking up each problem into its fundamental mathematical parts, and designing optimal algorithms to handle each piece, they are able to model a wide range of scientific phenomena.
In describing the cell modeling work he recently started with Berkeley Lab biologists, Colella explained that “in order to get better predictive models, you have to keep trying things out. The process becomes a very experimental, empirical activity, and that’s why the software tools are so important here.”
The software tools are based on adaptive mesh refinement (AMR), a grid-based system that uses partial differential equations to describe information in the most efficient manner possible—applying a fine mesh, and maximum computing power, to the areas of most interest, and a coarse mesh to areas where data is not as significant. AMR is particularly useful in problems where there is a wide range of time scales, and adaptive methods must be used to track movements in the mesh over time.
One of Bell and CCSE’s main projects in 2003 has been creating 3D simulations of turbulent methane combustion with swirling flow, which has produced the first detailed simulations in this area of combustion science (Figure 1). In the course of the project, two things have been of primary interest: how turbulence in the fuel stream affects the chemistry, and how emissions are formed and released. By studying the reacting flow of turbulent flames, CCSE has been able to develop computational models that dissect the detailed chemical reactions occurring in the flame. The group has also developed predictive models that can be used to analyze flame properties and characteristics of turbulence. Even with a simple fuel like methane, there are some 20 chemical species and 84 reactions involved; the reaction zone, where the adaptive mesh is concentrated, occurs in an area that is 150 microns, while the whole grid consumes 12 centimeters. All of this creates a problem size that demands some hefty computing power.
In order to create the flame visualizations, computations were performed on 2,048 processors of NERSC’s IBM SP, “Seaborg.” CCSE has created its own data analysis framework with specific algorithms to reformulate equations and accelerate the computations. The result is a computational cost that is reduced by a factor of 10,000 compared with a visualization using a standard uniform-grid approach.
 |
Figure 1 |
While a fundamental goal of the project is a better understanding of turbulence in flames, it could also have practical ramifications, as in engineering new designs for more efficient turbines, furnaces, incinerators, and other equipment held to strict emission requirements. A side benefit of the project is that it is stretching the group’s software to the limit, putting new demands on the algorithmic and geometric elements of the toolset.
“The methane flame happens to be the one application that encompasses most of the pieces of the software. They are all folded into this application,” said Marc Day, a staff scientist at CCSE. “You have to have applied math and computing hardware, together with good computational science, in order to accomplish what we have. Without any one of those pieces, it doesn’t work.”
The methane flame project falls into a class of problems called “interface dynamics,” where something happens to cause an instability in an interface between two fluids of different chemicals and density. This instability causes the interface to grow and change form. The modeling goal then becomes to track the evolution of the new interface. AMR is able to tackle these types of problems, where sophisticated and powerful tools are needed to scale and quantify the complicated energy dynamics. Equally important is a skilled, dedicated group of researchers to frame and calculate the problems.
To a great degree, CCSE and ANAG rely on their own computational scientists to apply the software to new projects and problem sets. But one of their goals has been to develop software components that other scientists can utilize more easily.
“We really want to support geometry and we need to support lots of different applications in different ways,” said Colella. “So how can we re-factor the software to do that? For one, we’re learning a lot about software engineering and managing the development process, using a ‘spiral design’ approach. When we add a new capability and develop applications in it, we get it out there for review. As we get feedback, we make changes to the software and repeat the process over again, so it becomes an ongoing spiral.”
Another one of the group’s goals in software development is to create algorithmic tools for doing computations in complex geometries. So if a problem demands hyperbolic, elliptic, and parabolic solver components, each of those pieces can be integrated while preserving the integrity of the model as a whole.
Both groups’ software development is an ongoing process, and new capabilities are constantly being added to make them more flexible and applicable in broader arenas of science.
Computational biology is one of the major growth areas, said Colella. Current research is creating enormous amounts of data on how the development and behavior of cells is governed by a complex network of reacting chemical species that are transported within a cell and among cellular communities. ANAG is working with the Arkin Laboratory in Berkeley Lab’s Physical Biosciences Division and UC Berkeley’s Bioengineering and Chemistry departments to develop the software infrastructure to turn this data into quantitative and predictive models. These models will contribute to a deeper understanding of cellular regulation and development, more efficient discovery of cellular networks, and a better ability to engineer or control cells for medical, agricultural, or industrial purposes.
The California Department of Water Resources has also asked for ANAG’s help in creating high-quality simulation software for modeling water flows from the Sacramento Delta to the San Francisco Bay (Figure 2). These models are valuable for researchers interested in better understanding fresh water flows, and other environmental and water quality issues.
  |
Figure 2 |
One of the reasons these mathematical software tools are so unique and powerful is that they can be applied to a wide array of scientific research, in a remarkably flexible fashion.
After analyzing the results of the methane flame project, for instance, CCSE scientists started to apply some of this newfound knowledge toward supernova research. Scientists have long been interested in fluid dynamics and energy transfers in supernovae, and trying to determine how and why they burn out. Using algorithms developed during its flame turbulence project, CCSE created 3D models of supernovae that shed new light on this problem, and have produced insights into the various stages of supernova explosions.
“You wouldn’t think that supernovae have anything in common with Bunsen burners, but algorithmically they were very similar,” said Day. “There was just a small number of pieces that we had to change out in order to make the chemical combustion turn into a nuclear flame. So we were able to make significant progress over a short period of time in the area of supernova physics because we already had this stuff laying around.”
All of this makes you wonder what else CCSE and ANAG have lying around, and where it might lead them next.
Research funding: ASCR-MICS, SciDAC, NASA, CDWR