[SnapPea-planning] Dirichlet domains

[Jeff Weeks]

Dear All,

I'm delighted to see the breadth of enthusiasm for bringing
SnapPea up to date, and of course even more delighted that
Nathaniel plans to do something about it.  :-)

On the subject of the Dirichlet domain computation,
I agree that a completely new -- and more robust -- algorithm 
would be ideal.  If that's not possible, though, there's
a simply way to make the existing algorithm more robust.
As you guys know, the root of the problem is that as you
perform successive multiplications on matrices in O(3,1),
the numerical error accumulates exponentially fast.
In effect, if you do too many matrix multiplications you get garbage.
The bad news is that exponential accumulation of error seems 
to be an unavoidable fact of life in hyperbolic space.
The good news is that the effect is far milder in PSL(2,C)
than in O(3,1) -- many orders of magnitude milder.
(If anybody wants to see why, I can send you a very elementary paper
explaining why PSL(2,C) gives better results, and giving 
some estimates of the difference.)

So... a quick-and-easy (well, quick-and-relatively-easy) way
to improve the Dirichlet domain algorithm's robustness would
be to replace the O(3,1) matrix multiplications with
PSL(2,C) matrix multiplications.  (The SnapPea kernel already
includes a MoebiusTransformation structure that extends PSL(2,C)
to handle orientation-reversing isometries.)
The rest of the existing Dirichlet domain algorithm is tied
pretty heavily to the Minkowski space model, so the simplest
way to switch over to PSL(2,C) might be to do it "secretly".
That is, let the rest of the algorithm think it's still working
in the Minkowski space model with O(3,1) matrices, but extend
the definition of an O(3,1) matrix to include a "shadow" PSL(2,C)
matrix.  Then, whenever the main Dirichlet algorithm calls
the function to multiply together two O(3,1) matrices, that function
first secretly multiplies the corresonding shadow matrices in PSL(2,C),
then converts the product to O(3,1) and reports the result.
The downside, of course, is that you incur the overhead 
of the conversion at each step of the way.  The upside is that
you can significantly improve the algorithm without undertaking
the more massive task of rewriting the whole thing in the context
of PSL(2,C).

Of course, in the face of exponentially accumulating errors,
that sort of trick merely postpones the inevitable loss of precision
to larger Dirichlet domains, it doesn't eliminate the problem completely.
So if Nathaniel (or any of you guys) can come up with
a fundamentally better algorithm, that would be the ideal solution.

Best wishes to all of you,
Jeff