Normal surfaces are a key tool in computational knot theory and 3-manifold
topology, and have featured in significant computational breakthroughs in
recent years. Despite this, there has been little practical progress on
algorithms that use fundamental normal surfaces, which are described in terms
of a Hilbert basis for a pointed rational cone on a high-dimensional integer
lattice. In this paper we develop and implement several algorithms to enumerate
fundamental normal surfaces, by merging domain-specific techniques from normal
surface theory with classical Hilbert basis algorithms.

Normal surface theory is a central tool in algorithmic three-dimensional
topology, and the enumeration of vertex normal surfaces is the computational
bottleneck in many important algorithms. However, it is not well understood how
the number of such surfaces grows in relation to the size of the underlying
triangulation. Here we address this problem in both theory and practice. In
theory, we tighten the exponential upper bound substantially; furthermore, we
construct pathological triangulations that prove an exponential bound to be
unavoidable.

In this paper we develop a new test to help identify whether a closed,
orientable, irreducible 3-manifold is non-Haken. The test builds on work by
Jaco and Oertel, and also incorporates heuristic pruning techniques to test
whether a normal surface is compressible. As an application, we settle
Thurston's old question of whether the Weber-Seifert dodecahedral space is
non-Haken.