Generators of $H_1(\Gamma_{h},\mathbbZ)$ for Triangulated Surfaces: Construction and Classification

Ralf Hiptmair, Jörg Ostrowski

SIAM Journal on Computing · 2002 · 38 citations · 9 references

Concepts

Abstract

We consider a bounded Lipschitz-polyhedron $\Omega\subset\mathbb{R}^3$ of general topology equipped with a tetrahedral triangulation that induces a mesh $\Gamma_h$ of the surface $\partial\Omega$. We seek a maximal set of surface edge cycles that are independent in $H_1(\Gamma_h,\mathbb{Z})$ and bounding with respect to the exterior of $\Omega$. We present an algorithm for constructing suitable 1-cycles in $\Gamma_h$: First, representatives of a basis of the homology group $H_1(\Gamma_h,\mathbb{Z})$ are constructed, merely using the combinatorial description of the surface mesh $\Gamma_h$. Then, a duality pairing based on linking numbers is used to determine those combinations that are bounding with respect to $\mathbb{R}^3\setminus\Omega$. This is the key to circumventing a triangulation of the exterior region $\mathbb{R}^3\setminus\Omega$ in the computations. For shape-regular, quasi-uniform families of meshes, the asymptotic complexity of the algorithm is shown to be O(N2 ), where N is the number of edges of $\Gamma_h$. The scheme provides an essential preprocessing step for all boundary element methods for eddy current simulation, which rely on discrete divergence-free vectorfields and their description through stream functions.

References

9