Research Focus : Differential Equations

Herb Keller (co-director), Andrew White (co-director), Todd Arbogast, Clint Dawson, Joel Dendy, Eusebius Doedel, Donald Estep, David Forslund, Mac Hyman, Phil Keenan, Dan Meiron, Dale Pullin, Steve Roy Karmesin, Jeff Saltzman, Eric Van de Velde, Mary Wheeler, Roy Williams, and Nai- Ying Zhang

Differential equations can be used to model almost any scientific phenomenon. However, scalable parallel implementations of solution algorithms must be implemented to obtain physically realistic solutions of the equations modeling real-world complex problems such as fluid turbulence.
Research on algorithms for the solution of differential equations serves both as an intermediate testbed for work on software and tools and as a toolkit for implementing the specific grand challenge applications that are of interest to the CRPC. These algorithms have applications to problems in combustion, enhanced oil recovery, ocean and atmospheric circulation, and plasma physics. Work on numerical methods in computational fluid dynamics is particularly relevant to simulations in these application areas.
The Differential Equations group develops software and algorithms that facilitate efficient parallel solution of partial differential equations. Over the years, sophisticated algorithms that attempt to maximize accuracy and computational efficiency have been developed on serial computers. These include techniques such as adaptive mesh refinement, irregular meshes for problems in complex geometries, and advanced solvers such as multigrid. A continuing challenge for the group is the efficient implementation of these advanced techniques on present- day parallel supercomputers.
Research has also focused on the solution of three-dimensional problems and the effects of multi-scale and subgrid-scale phenomena in the areas of linear and nonlinear equations, domain decomposition techniques, continuation methods, and discretization methods, particularly those arising in the study of computational fluid dynamics.
The CRPC provides a framework for this group by encouraging interactions between researchers at different sites. The center has also encouraged interdisciplinary collaboration, as shown in several of the projects described below.
Templates for Scientific Computation

In collaboration with the CRPC's Parallel Paradigm Integration group, many of the algorithms developed by the Differential Equations group are being incorporated into programming templates.
Research in regular mesh templates for scientific computation attempts to encapsulate common data distributions and communication patterns that arise in diverse scientific applications. The goal is to allow users to write portable deterministic code. This approach shows promise for a wide variety of applications, including spectral methods in two and three dimensions for the equations of fluid motion as well as other partial differential equations, finite difference methods on regular grids, and large-scale molecular orbital calculations. Each of these applications displays a typical data distribution and communication pattern. If a particular application shares this pattern, then conversion of a serial algorithm to a parallel one using the appropriate template becomes straightforward. At present, the group has implemented all templates under development in Fortran M, a small extension of Fortran 77 developed by the Parallel Paradigm Integration group that provides facilities for both task and data parallelism. However the templates can also be implemented using standard Fortran 77 and any of the popular message-passing libraries such as PVM or P4. So far, the group has completed the development of several templates and ported them to different architectures. Future plans include implementing these templates on heterogeneous networks of workstations using PVM or P4.
Also under investigation is the extension of the template concept to much more sophisticated algorithms such as the fast particle methods for astrophysical N-body calculations developed by CRPC researchers John Salmon and Michael Warren. These fast particle methods can be used, for example, to implement fast panel methods as a way of computing fluid flow over complex three- dimensional bodies. The Salmon-Warren algorithm has recently been re-designed using a new parallel data structure, the hashed oct-tree, and several calculations have been completed using this new approach. The research group will investigate implementation of this algorithm as a template in CC++, another parallel language developed by the Parallel Paradigm Integration group that provides parallel extensions to the C++ language and thus allows for the design of classes that encapsulate parallel computation.
Several of the templates being developed are potential candidates for use in the CRPC's PCE-Tech program.
Object-oriented Approaches

Research in the application of an object-oriented approach to parallel computation has as its objective the development of class libraries for parallel structured mesh computations that are compatible across serial, vector, and parallel machines. These libraries facilitate the design, for example, of portable hydrodynamics codes that utilize adaptive mesh refinement. Researchers from the group have to date developed serial array class libraries in C++ for structured mesh computations. The array libraries may be used in the PCE-Tech program. Plans are underway to include parallel objects for array operations and to develop adaptive mesh refinement for specific applications like steady and transient problems.
Other object-oriented research focuses on parallel particle-in-cell simulations for plasma physics (see the separate work-in-progress article, page 11) and concurrent adaptive methods for reaction diffusion equations. For the latter project, software is being developed for concurrent computations using dynamically adaptive triangular meshes. This is an interdisciplinary collaboration involving methods in concurrent computation, linear algebra, and numerical error estimation.
Adaptive Mesh Refinement and Computational Fluid Dynamics

The group is planning to investigate reduction of the communications costs in adaptive mesh refinement (AMR) by using a data structure that requires only fast communications. AMR techniques for finite difference methods have resolved approximate solutions of partial differential equations of high speed fluid flow without requiring a fine lattice or a small time step in every part of the field. Use of AMR, however, can lead to load imbalances and a large communications overhead if not carefully implemented.
Computational fluid dynamics projects concerning vortex reconnection and chemically reacting hypersonic flows also play an important part in the group's plans. The goal here is to implement the template ideas described above to these grand challenge applications and to use large- scale parallel simulations to answer key questions on the nature of small-scale structures in fluid flow.
Domain Decomposition

Domain decomposition can be used to impose a structure on the code that advantageously restricts the amount and type of interprocessor communication required to solve the problem. The Differential Equations group is developing codes for parallel domain decomposition and multigrid for large nonlinear systems of coupled elliptic and parabolic partial differential equations. Other research areas include the development of operator-based averaging techniques for rough coefficient problems, local mesh refinements near localized heterogeneities or singularities (such as around horizontal and vertical wells), and extensions of the algorithms to unstructured grids. Major difficulties that arise in these models include load balancing, time-step constraints, the definition of effective preconditioners for solving the interface problem that connects the subdomains, and the ability to follow interacting reactive and advective flows.
Homotopy and Continuation Methods

Research in continuation and homotopy methods for solving nonlinear problems will emphasize parallel algorithms and implementations. A basic class of model problems to which the new techniques should be applicable is the discretization of the steady-state Navier-Stokes equations in two or three dimensions. New procedures for stabilization of steady states in time-evolution methods will be applied to handle general fixed-point iterations, stiff systems, periodic solutions, and other areas where possible.
Multilevel Methods

Algorithms involving nested grids have proven to be particularly useful in scientific computation. However, they have usually not performed optimally on distributed-memory parallel architectures because of problems with data structures and locality. The Differential Equations group is concentrating on multilevel algorithms in four areas: discretized algebraic equations, segment relaxation, nonlinear equations, and homogenization.
New Directions
Research in parallel I/O will become more important to this group in the future. This will be an interdisciplinary effort focusing on Fortran M and CC++. Support from research initiatives in scalable I/O and from the NSF HPCC community has been obtained for this work. In the long term, the group plans to deploy and evaluate many of the software technologies under development on selected grand challenge applications.
Editor's note: The CRPC has five major research thrusts. Each issue of Parallel Computing Research will highlight one of these thrusts through an in-depth "Research Focus" article.
Table of Contents

News | From the Director | Parallel Profile | Research Focus | Work in Progress | Education / Outreach | Resources | Calendar | CRPC Home