[SnapPea-planning] Dirichlet domains

[Bill Thurston]

Dear All,
	This is probably getting ahead of ourselves, but it's hard to  
resist!  Jeff, your idea sounds like a good interim measure,
as long as we're not dealing with truly huge manifolds. My thought,  
probably naive, for a conceptually robust algorithm if arbitrary- 
precision arithmetic does not work well: to compute the distance  
functions from images of the base point recursively simplex-by- 
simplex. For each simplex, the length of a homotopy class of paths to  
the base point can be recorded by a vector and a distance from a point  
in the center of each simplex. It's easy to transport this information  
one simplex to its neighbors, and the computations should involve  
modest size nuimbers and little rounding error unless some of the  
simplices are nearly degenerate. This data for a bounded number of  
paths is enough to describe the Dirichlet domain.
	Bill
On Nov 7, 2008, at 12:13 PM, Jeff Weeks wrote:

> 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
>
>
>