Discrete differential forms have numerous applications in the computational
sciences. A prominant example is the use of mimetic discretizations, such as
Whitney elements, in solving Maxwell's equations. In this case, preservation of
the differential complex is crucial to numerical stability. Other noteworthy
cases are discrete Hodge decompostions for divergence constraints and
visualization. Lastly, "holes" in the coverage of sensor networks and other
topological properties can be investigated with discrete k-form Laplacians. All
of these applications require the solution of systems of the form (d_k,d_k),
where d_k denotes the exterior derivative for k-forms. The most common cases,
(d_0,d_0) and (d_1,d_1) in Euclidean space, correspond to (grad,grad) and
(curl,curl) respectively.
In general, we seek efficient solutions of
(d_k,d_k) problems on unstructured meshes. While efficient AMG methods have been
developed for 0-forms (scalar) and more recently 1-form (vector) problems, the
higher dimensional problems have received less attention. Such problems arise,
for instance, in determining the presence of coverage gaps in two or three
dimensional sensor networks. In both cases, the null-space of the k-th
combinatorial Laplacian is used to identify potential holes.
Direct
factorization methods, such as the Smith Normal Form, have been the primary tool
in these topological problems. While suitable for small meshes, direct solvers
become prohibitively expensive for large-scale applications. However, in many
cases of interest only approximate solutions (e.g. to null vectors or hodge
decompositions) are required, which combined with the distributed nature of such
problems makes iterative methods more appealing.
In this talk we
highlight recent progress in using AMG for higher-dimensional topological
problems. We offer preliminary numerical evidence in support of this approach
and discuss directions to further extend this methodology to larger sets of
problems.