Introduction and Overview
The main goals and important issues in developing parallel algorithms
of unstructured mesh calculations
Introduction
Unstructured meshes are a powerful computational tool used in the numerical
modeling of physical phenomena on complex, irregular domains.
Instead of requiring a uniform distribution of grid points, unstructured
meshes allow grid points to be strategically placed in the computational domain.
Thus, these meshes are particularly effective in modeling irregular
boundaries, multiscale geometries, and rapidly changing solutions.
Much research has been done to design sequential algorithms and techniques
to effectively use unstructured meshes in the solution of large-scale
applications.
Unfortunately, many of these applications cannot take advantage of
the power of parallel computing because of a lack of widely available
software tools on distributed memory architectures.
In addition, no attempt has been made to provide a publicly available
software product that integrates key aspects of unstructured mesh
computation on parallel computers.
The SUMAA3D (Scalable Unstructured Mesh Algorithms and Applications) project
will rectify this situation.
Our expertise in the development of parallel algorithms for
unstructured mesh computation, our experience in distributing and
maintaining software in the public domain, and our commitment to
work with application scientists in a variety of disciplines and
industries will propel this software tool to the forefront of
computational science.
Overview
The SUMAA3D project comprises three primary components (1) algorithmic
design and implementation,
(2)
software development and dissemination, and
(3)
large-scale application solution.
Algorithmic Design and Implementation
The first component is fundamental research into the development of
provably good, provably fast algorithms for all aspects of unstructured
mesh computation on distributed memory architectures.
In particular, we have identified the following basic problems that are
fundamental to massively parallel computation on unstructured domains:
-
Mesh generation:
construction of meshes that satisfy user-specified
properties over complex two- and three-dimensional domains.
For most complex domains, manual mesh generation is
an intractable problem because of the irregularity of the boundary and the
difficulty of visualizing three-dimensional discretizations.
As a consequence, sequential automatic mesh generation tools that
produce high-quality meshes are playing an increasingly important role in
numerical simulations.
Equivalent tools for parallel computers are essential.
To this end, we have begun to develop scalable software capable
of automatically generating consistent, high-quality meshes on
complex geometries in both two and three dimensions.
-
Mesh Smoothing:
adjustment of grid point position to improve the quality of the mesh
according to a user defined measure.
Meshes generated using automatic mesh generation techniques often
contain poorly shaped or distorted elements which result in numerical
difficulties during the solution process.
One approach used to correct these problems is to adjust the mesh
point locations in such a way that element distortion is reduced and
the overall quality of the mesh is improved.
We have developed a new local smoothing algorithm based on nonsmooth
optimization techniques gauranteed to maintain or improve mesh quality.
In addition, we assume that many large scale applications are utilizing
massively parallel computers and cannot maintain the entire mesh on
a single processor.
Therefore new algorithms are required to perform the mesh smoothing
algorithm in parallel, and to meet this need, we have an efficient
parallel mesh smoothing algorithm with a provably fast runtime.
-
Mesh refinement:
adaptive refinement and de-refinement of an initial
mesh to accurately model rapidly changing solutions and multiscale
geometries.
Adaptive mesh refinement techniques have been shown to
be very successful in reducing the computational and storage requirements
for solving many large-scale applications.
We have developed a provably good parallel algorithm for adaptive
mesh refinement in two dimensions.
Our algorithm may be used in conjunction with a variety of
element refinement techniques including h- or p-
refinement for simplicial or nonsimplicial meshes.
Since three-dimensional computer simulations are even costlier,
an equivalent parallel algorithm adaptive refinement for three-dimensional
elements and domains must be developed.
-
Mesh partitioning:
partitioning of graphs/geometries into
equally sized, well-separated regions which are then assigned to
computer processors.
The goal of the partitioning algorithm is to divide the vertices in the
mesh into equal sized groups in such a way that communication costs are
reduced.
Because the mesh is dynamically changing, these partitions cannot
be determined a priori, and a new partitioning must be calculated for
every modification of the mesh.
We have designed a new partitioning heuristic which is inexpensive to
compute and generates provably good partitions for the meshes that
typically arise in the solution of partial differential equations.
- Linear system solution: assembly and solution of the linear
systems generated by general, unstructured mesh problems.
This is often the dominant computational task for many applications.
Therefore, efficient algorithms are required to assemble and solve linear
systems on parallel computers.
We have designed an algorithm based on a very fast, scalable graph coloring
heuristic that is the basic component in our sparse, symmetric,
linear system solver,
BlockSolve95 .
Equivalent software for nonsymmetric systems must be designed and
implemented to expand the utility of the SUMAA3D project to applications
such as fluid flow.
Next: Accomplishements
Back: Unstructured Mesh Home Page
freitag@mcs.anl.gov / jones@cs.utk.edu / plassman@mcs.anl.gov
Argonne National Laboratory / The University of Tennessee