|
Computer Science meets Rocket Science Michael Heath
Despite a busy schedule as an administrator, teacher, and textbook author, Professor Michael Heath still finds time to collaborate with students and colleagues on some exciting research. His administrative role is as Director of both the Computational Science and Engineering (CSE) Program and the Center for Simulation of Advanced Rockets (Rocket Center). He is also currently writing a new textbook on parallel numerical algorithms, complementing his earlier textbook on scientific computing. Heath's research in both of these fields often intersects other areas of computer science, such as computational geometry. The Rocket Center, now in its ninth year, does "virtual prototyping" of solid propellant rocket engines, simulating their behavior and performance from first principles using computers. The materials and processes in a rocket engine are described by mathematical equations that are solved numerically using high performance parallel supercomputers. "Rocket simulation requires a multidisciplinary combination of physics, chemistry, mathematics, engineering, and computer science," says Heath. "The Rocket Center has been a fertile source of interesting problems in computer science, as well as an industrial strength test bed for the products of the resulting research." For instance, Professor Marianne Winslett's Panda library for parallel I/O (input /output) and Professor Laxmikant Kale's Charm++ parallel programming environment are both used extensively in the Rocket Center, which has been mutually beneficial to both the developers and the users of these software packages. Additional research in computer science spawned by the Rocket Center includes mesh generation and adaptation, computational geometry, and graphical visualization. A specific example is the need to exchange data between software modules representing distinct physical components in a multi-component system, such as fluid-solid interaction. Such exchanges between separately developed and independently meshed components are not only a software engineering challenge, but they also must be numerically accurate and obey relevant physical laws, such as conservation of mass, energy, and momentum. Previous methods for such data transfers typically have sacrificed either accuracy or conservation in favor of the other. A better approach is to treat the problem as a constrained optimization, minimizing error subject to exact conservation. The key to expressing conservation as a constraint turned out to be the "common refinement" of the two surface meshes of the source and target components; that is, a third surface mesh that is finer than either of the input meshes but commensurate with both. Thus, cracking a previously unsolved problem in "pure" computational geometry turned out to be crucial for a very practical problem in rocketry, as well as many other applications. Heath and his PhD student Jim Jiao (now a faculty member at Georgia Tech) developed efficient and elegant algorithms for computing the common refinement as well as the accompanying data transfer, and implemented them in practical software that works well even on massively parallel computers. Another of Heath's PhD students, Bill Cochran, is developing intelligent meshes that know how to partition themselves onto a parallel computer and that can solve systems of equations directly, without having to generate separate matrix data. A mesh can be partitioned either topologically (based on the connectivity of the nodes) or geometrically (based on the locations of the nodes in space). Neither of these approaches is ideal: topological partitioning tends to yield jagged pieces, whereas geometric partitioning may yield disconnected pieces. To obtain the best of both approaches, a new hybrid approach is under development in which the medial axis (or more accurately, the medial surface in three dimensions) is used to perform an initial partitioning into roughly convex pieces, each of which can then be effectively partitioned geometrically. Unfortunately, existing algorithms for computing the medial surface are computationally expensive and far from foolproof, so an important part of Cochran's thesis research has been to develop a robust algorithm for approximating the medial surface. Again there is a strong connection to computational geometry. A project recently completed by Heath's PhD student Rebecca Hartman-Baker involved magneto-telluric geoprospecting, in which electromagnetic waves are passed through the earth (much like sound waves in seismology), and the emerging waves are analyzed to reveal underground formations such as ore deposits. This "inverse problem" led in turn to an optimization problem: How can you find the global minimum of a function having many local minima? Using the diffusion equation method, the solution involved diffusing the surface being optimized and seeking the lowest point in each of a succession of diffused surfaces. One way to think of this is like a roller coaster, which has ups and downs of all sizes. Ignoring physics and considering just the shape of the curve, we want to find the lowest point during the ride. Using a traditional local search method, we might go up a hill then down into a valley and conclude that the valley is the lowest point, without knowing what lies ahead. Now diffuse the ride by stretching it out, so that the shallow valleys disappear. Keep stretching until only one valley remains, and that will be the lowest, although the stretching may have changed its location somewhat. One can then backtrack through the sequence of stretched configurations to find the true location of the global minimum in the original configuration. Although conceptually simple, implementation of this approach requires a substantial amount of computation, which fortunately turns out to be very efficiently done on a parallel computer. Written by Judy Tolliver, June 1, 2006
|
|