William F. Mitchell, ACMD
The numerical solution of partial differential equations (PDEs) is often the most computationally intensive part of solving mathematical models of physical phenomena important to industry. For this reason, much research has been performed to find faster methods to solve PDEs at higher resolution. A recent development involves the combination of solution-adapted unstructured grids, to provide higher resolution only where it is needed, with multi-level (multigrid) linear system solution techniques, which have the smallest possible asymptotic operation counts.
We have been investigating methods of this type for several years. As part of this research, a new method was developed and implemented in an experimental code called MGGHAT (MultiGrid Galerkin Hierarchical Adaptive Triangles) for linear steady-state problems on polygonal 2D domains. This program has been released to the public, and is seeing widespread use. MGGHAT has had over 1500 accesses at netlib, which is only one of the locations from which it can be obtained.
During the past year, MGGHAT was enhanced to make it more useful for practical industrial problems. The original version was written as a research code to test the new method and is capable of solving a single linear steady-state equation. The program was modified to handle practical problems which typically involve systems of equations, nonlinear equations, and time dependent equations. It was also enhanced with an improved user interface, including graphical displays (see Figure 18). Version 1.1 was made available to the public in June 1994 through the netlib mathematical software repository and the Multigrid Network ( mgnet) ftp site at Yale University.
Figure 18: MGGHAT display of solution and adaptive grid
In addition to the software, an on-line user's guide was developed in the hypertext markup language (HTML), and made available to users of the World Wide Web (WWW) through the GAMS server at NIST. This document was accessed over 600 times between June 1994 and February 1995.
In collaboration with NIST scientists, MGGHAT has been used on realistic problems with industrial application. These problems include:
As part of NIST's efforts in High Performance Computing and Communications (HPCC), we are in the process of implementing the methods of MGGHAT in a new Fortran 90 program, PHAML (Parallel Hierarchical Adaptive MultiLevel), with modifications to make the methods more amenable to parallel computation. Explicit parallelism is expressed through message passing between processors using standard libraries, initially PVM (Parallel Virtual Machine) and MPI (Message Passing Interface). Testing at NIST is performed using networks of workstations and the IBM SP2 parallel computer.
For an algorithm to make effective use of parallel processors, it is important that the amount of work assigned to each processor is nearly equal (load balancing), and that the amount of communication between the processors is minimized. For adaptive grids, this partitioning problem is nontrivial and must be solved quickly so that the time for partitioning does not dominate the time for solving the PDE. A new fast partitioning algorithm has been developed under this project and has been incorporated into PHAML. This partitioning algorithm differs from existing algorithms in that it uses information obtained during the adaptive refinement process to very quickly determine a perfectly balanced partition. Existing algorithms typically solve an optimization problem using only information contained in the final grid, and are much slower.