
TODAY’S supercomputers allow researchers to simulate largescale physical phenomena with a level of detail previously impossible to achieve. These simulations are increasingly important in exploring fundamental scientific issues, particularly when experiments are prohibitively expensive or simply not feasible, as in studying global climate change or stellar evolution.
Livermore’s hypre library of linear solvers makes possible larger, more detailed simulations by solving problems faster than ever before. The hypre development team, which received initial funding from Livermore’s Laboratory Directed Research and Development Program, won an R&D 100 Award for their innovative software.
A solver is an algorithm for calculating the solution to a set of mathematical equations. A linear solver works on a system of linear equations, such as those found in a high school algebra textbook. Unlike the equations in high school algebra, however, the linear systems that arise in scientific simulations often have millions or billions of equations. Computer scientist Rob Falgout, who leads the hypre team, says, “When it comes to efficiently processing huge sets of linear equations, not all systems are created equal. Some are fairly easy to solve, while others require specialized algorithms.”
The physical world can be described by complicated sets of mathematical equations. To translate these equations into something suitable for a computer, scientists restrict a problem to a grid and assign one or more physical characteristics to each grid point, a process called discretizing. In a groundwaterflow simulation, for example, the grid points represent discrete locations underground. The characteristics describing these locations might include the concentration of chemical contaminants and the direction and speed of contaminant travel.
The main goal of a simulation is to assign meaningful values to the physical properties at each point. In a largescale simulation, the most timeconsuming component in determining these values is often processing the solution for a huge system of linear equations. Hypre’s linear solvers make quick work of the equations and are effective on systems that define a variety of physical phenomena. For example, Livermore researchers applied hypre’s structured solvers in simulations of inertial confinement fusion experiments, reducing the calculation time by as much as 30 times that required by other linear solvers. They are also using the hypre library to improve the detail and reduce computational time of simulations such as elastic deformation in explosive materials, explosively driven magnetic flux compression generators, and molecular dynamics.

The hypre library of linear solvers helps speed up calculations for a range of simulations. (a) A simulation predicting the results of a maxillofacial surgery compares well with the patient’s postoperative computedtomography scan. (Image courtesy of C&C Research Laboratories, NEC Europe, Ltd.) (b) Results from a Livermore calculation of the hydrodynamic stress caused by large currents in pulsedpower experiments show the transient magnetic field and eddy currents occurring in a helical coil with two sidebyside wires. 
The Challenge of Scalability
Although many software packages include parallel linear solvers, not all of them are scalable. Scalability—the ability to use additional computational resources effectively—is both a challenge and a necessity in designing parallel algorithms. Falgout’s team developed the algorithms in hypre with scalability in mind.
Hypre’s solvers are based on an iterative multilevel approach. An iterative solver begins with a “guess” of the solution and then uses an algorithm to generate an improved guess. This procedure repeats until the iterations converge with the solution. The multilevel solvers in hypre accelerate the iterative process by using a sequence of smaller linear systems, each associated with a smaller, or coarser, grid. The coarsegrid system enables hypre to significantly improve each successive guess with little added computational expense because the calculations primarily involve small problems.
Most importantly, the computational cost with a multilevel approach is proportional to the number of equations. Thus, a large problem can be solved in the same time as a smaller one by proportionally increasing the number of processors working on the calculation. Hypre’s algorithms facilitate scalability on current supercomputers, with tens of thousands of processors, and are expected to operate just as effectively on future systems with hundreds of thousands or even millions of processors. The library’s flexibility also allows researchers to use hypre on a laptop computer or individual workstation.
Hypre’s specialized algorithms take advantage of easytouse interfaces for scientific software. Most parallel linear solver packages access information only from the equations to be processed. Many hypre solvers, in contrast, work faster by using information from the interface, such as the grid, the type of discretization, or known error components that are slow to converge.
Algorithms range from structured multigrid solvers for simple problems to a fast, adaptive composite solver for problems requiring adaptively refined grids. Hypre’s algebraic multigrid solver can process complex problems requiring arbitrary unstructured grids and has been scaled up to 125,000 processors. In addition, the library’s unstructured Maxwell solver, AMS, is the first provably scalable solver for semidefinite electromagnetic problems involving general unstructured meshes.

The hypre development team (from left): Van Emden Henson, Rob Falgout, Ulrike Meier Yang,
Tzanio Kolev, Charles Tong, Allison Baker, Barry Lee, Jeffrey Painter, and Panayot Vassilevski. 
Free and Flexible
Hypre is opensource software and is available for free from the project’s Web site (www.llnl.gov/CASC/hypre/). In 2006, scientists in more than 35 countries downloaded it nearly 1,000 times. Research institutions and private companies have used hypre to simulate maxillofacial surgeries, magnetic fusion energy plasmas in tokamaks and stellarators, blood flow through the heart, fluid flow in steam generators for nuclear power plants, and pumping activity in oil reservoirs.
The hypre library offers the most comprehensive suite of scalable parallel linear solvers available for largescale scientific simulation, with some algorithms appearing for the first time in a linear solver library. “The hypre library is the result of nearly nine years of mathematical research and software development,” says Ulrike Meier Yang, a computer scientist on the hypre team. “It was a significant undertaking, but one that is benefiting scientists all over the world.”
—Katie Walter
Key Words: hypre linear solver, opensource software, parallel computing, R&D 100 Award, supercomputing.
For further information contact Rob Falgout (925) 4224377 (falgout2@llnl.gov).
Download a printerfriendly version of this article.
