search

sagemath / sage

Main repository of SageMath. Now open for Issues and Pull Requests.
https://www.sagemath.org
Other
1.09k stars 394 forks source link

hyperbolic geometry #9439

Closed videlec closed 9 years ago

videlec commented 13 years ago

Implementation of two conformal models of hyperbolic geometry (half plane, disc) and actions of their isometry groups.

The actual file is almost complete for working with the hyperbolic plane as the following will plot a hyperbolic triangle

sage: HH
Hyperbolic half plane
sage: HH(0)
Boundary point 0
sage: p = HH.polygon([CC(0), CC(1), CC(2,2)])
sage: p.plot(face_color='red').show(aspect_ratio=1)

There are more examples in the file.

Apply:

CC: @kcrisman @pjbruin

Component: geometry

Keywords: hyperbolic geometry, Poincare disc, upper half plane, Beltrami-Klein, hyperboloid model, sd35, days64

Author: Vincent Delecroix, Martin Raum, Greg Laun, Travis Scrimshaw

Branch: 82cf89e

Reviewer: Johan Bosman, Travis Scrimshaw, Greg Laun, Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/9439

videlec commented 13 years ago

Attachment: trac_9439-hyperbolic geometry.py.gz

draft of hyperbolic geometry space

videlec commented 13 years ago

Attachment: trac_9439-hyperbolic_geometry.patch.gz

this patch contains the previous one

videlec commented 13 years ago

Description changed:

--- 
+++ 
@@ -1,9 +1,14 @@
-Implementation of three conformal models for hyperbolic geometry (half plane, disc, hyperboloid) with actions of their isometry groups.
+Implementation of two conformal models of hyperbolic geometry (half plane, disc) and actions of their isometry groups.

 The actual file is almost complete for working with the hyperbolic plane as the following will plot a hyperbolic triangle

-sage: HH.polygon(CC(0), CC(1), CC(2,2)).plot(face_color='red') +sage: HH +Hyperbolic half plane +sage: HH(0) +Boundary point 0 +sage: p = HH.polygon([CC(0), CC(1), CC(2,2)]) +sage: p.plot(face_color='red').show(aspect_ratio=1)

 There are more examples in the file.
1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago
comment:3

ping :)

Are you planning on finishing this? It would be very good to have an upper half plane implementation.

There are a few things that need to be improved though. Accessing attributes directly (e.g. with spam._value) is not good. Please use accessor methods instead (i.e. a method named value() that returns _value); this improves the separation of interface and implementation.

Near the real line, the hyperbolic distance becomes become HUGE compared to the Euclidean distance. Representing a point as a complex number thus leads to numeric instability. It is therefore better to implement a point by a pair of a matrix ((a,b),(c,d)) and a complex number z (thus representing (az+b)/(cz+d)).

1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago

Description changed:

--- 
+++ 
@@ -11,8 +11,3 @@
 sage: p.plot(face_color='red').show(aspect_ratio=1)

There are more examples in the file.

- -Depandancy:

-* #9076: plot arc of circles

videlec commented 12 years ago
comment:4

Are you planning on finishing this? It would be very good to have an upper half plane implementation.

Yes. But if you have time and motivation, go on. But there are problems (see below)

There are a few things that need to be improved though. Accessing attributes directly (e.g. with spam._value) is not good. Please use accessor methods instead (i.e. a method named value() that returns _value); this improves the separation of interface and implementation.

Can be done.

Near the real line, the hyperbolic distance becomes become HUGE compared to the Euclidean distance. Representing a point as a complex number thus leads to numeric instability. It is therefore better to implement a point by a pair of a matrix ((a,b),(c,d)) and a complex number z (thus representing (az+b)/(cz+d)).

I agree on the fact that near the real line it is unstable but disagree on the fact that we need a 5 dimensional object (an element of SL(2,R) and a complex number) to record a 2 dimensional object (a point in the half plane). The best option would be to store only the SL(2,R) matrix m such that the point is the image by z of the point i. Two matrices give the same point iff they are congruent modulo SO(2).

Problems

1) The main problem with that project is about of action by matrices. It would be natural that matrices act on the upper half plane. But there are many instances

2) In the actual implementation, the geodesics that pass to infinity in the half plane model have an arbitrary maximum height. I did not find a good way to draw them depending on what is asked in the final .show(). In the same veine, a circle with radius 1 very near the boundary should not be drawn as it is less than one pixel...

1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago
comment:5

Replying to @videlec:

I agree on the fact that near the real line it is unstable but disagree on the fact that we need a 5 dimensional object (an element of SL(2,R) and a complex number) to record a 2 dimensional object (a point in the half plane). The best option would be to store only the SL(2,R) matrix m such that the point is the image by z of the point i. Two matrices give the same point iff they are congruent modulo SO(2).

Okay. Another possibility is to have the matrix ((a, b), (c, d)) in SL_2(ZZ) and the complex number z in the standard fundamental domain for this group. Or use both representations (and allow oneself to convert between them).

18d65770-dc1e-4813-89a9-4828e4aae4a9 commented 12 years ago

Attachment: trac_9439-hyperbolic_2space.patch.gz

A sketch for hyperbolic 2-space implementation.

1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago

Attachment: trac_9439-hyperbolic_2space.2.patch.gz

Same patch with .py~ files removed

1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago

Changed keywords from hyperbolic geometry, Poincare disc, upper half plane to hyperbolic geometry, Poincare disc, upper half plane, sd35

18d65770-dc1e-4813-89a9-4828e4aae4a9 commented 12 years ago

Attachment: trac_9439-hyperbolic_upper_half_plane.patch.gz

implementations of geodesics, triangles, and polygons

1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago

Attachment: trac_9439_with_points.patch.gz

Contains (and thus replaces) previous patch

1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago
comment:7

The patch I've just uploaded makes Sage import HH at startup. I propose that we clean up all the mess first (including all the doctest failures) before we add further functionality.

1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago

Attachment: trac_9439_with_points.2.patch.gz

Second attempt; hopefully the point file is added. :).

1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago

Apparently not, so let's just upload the file. :P.

18d65770-dc1e-4813-89a9-4828e4aae4a9 commented 12 years ago

Attachment: upper_half_plane_point.py.gz

18d65770-dc1e-4813-89a9-4828e4aae4a9 commented 12 years ago
comment:8

Attachment: trac_9439_hyperbolic_space.tar.gz

I simply uploaded all current files, because I messed up my HG status.

I couldn't fix the problem with conversion into CC, which is now #12216. I replaced it by the method toCC.

I haven't checked whether triangles work, but I am exhausted. Plotting polygons works and it should be easy to fill in the tests, that are all stubs for the moment.

roed314 commented 11 years ago
comment:9

This looks neat: I just wanted to encourage you guys to keep working on it. I just had a request for plotting fundamental domains of congruence subgroups....

kcrisman commented 11 years ago

Reviewer: Johan Bosman

kcrisman commented 11 years ago

Changed author from vdelecroix to Vincent Delecroix, Martin Raum

videlec commented 11 years ago
comment:11

Replying to @roed314:

This looks neat: I just wanted to encourage you guys to keep working on it. I just had a request for plotting fundamental domains of congruence subgroups....

I just notice that it is yet possible to draw fundamental domain for congruence subgroups using Farey symbols (#11709, integrated since sage-5.0).

sage: FareySymbol(Gamma(3)).fundamental_domain()
2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 11 years ago
comment:12

I have a working implementation of hyperbolic two-space in sage that includes the upper half plane, Poincare disk, Klein disk, and hyperboloid model. For each model, geodesics, points, and isometry groups are implemented.

Conversion between each model to another is implemented*, as are a number of useful calculation routines. For example, geodesics can compute the corresponding reflection, two geodesics can compute their common perpendiculars, isometries can factor themselves into products of reflections.

The code originated as a series of Mathematica notebooks from Bill Goldman's lab at UMD. We had some students port it to a sage script, which was then fleshed out. I have refrained from publishing it here because I'm completely refactoring into something resembling readable code. It's taken me a few month longer than I thought it would to refactor, so I wanted to write a note here so that efforts aren't redoubled.

Is there a best course of action as far as posting code goes? I think that merging the patches posted here and my code won't be too bad. Should I finish refactoring my code first, and then post it? Should I post the original script? In the original code, there are lots of test and all tests pass, so it's usable. Should I post the bit of refactoring I've done so far?

*Actually, not quite. I don't have a great way to go from SO(2,1) to SL(2,R). So this makes converting from the hyperboloid model to the other models somewhat tricky.

videlec commented 11 years ago
comment:13

Hi Greg,

You should either post your code here or provide a link. If your code does work, we will definitely use it !

Note that several things should be merged

Best, Vincent

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 11 years ago
comment:14

Okay great. I'll post it by the end of the week. That should be enough time to clean up the remaining refactoring (which will greatly improve the ability to merge the code).

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 11 years ago
comment:15

Obviously it's been longer than a week. I had to attend a long conference and then hurricanes etc. It will be at the very least another week before I get it up.

fchapoton commented 11 years ago

Description changed:

--- 
+++ 
@@ -11,3 +11,6 @@
 sage: p.plot(face_color='red').show(aspect_ratio=1)

There are more examples in the file. + +Apply: +* attachment: trac_9439-hyperbolic_geometry.patch

fchapoton commented 11 years ago
comment:16

What a mess ! can some of you say what patches have to be applied and in which order ?

Let me try with just one patch:

apply trac_9439-hyperbolic_geometry.patch

fchapoton commented 11 years ago
comment:17

A review patch, so that tests pass. But there lacks a lot of documentation !

fchapoton commented 11 years ago

Description changed:

--- 
+++ 
@@ -14,3 +14,4 @@

 Apply:
 * [attachment: trac_9439-hyperbolic_geometry.patch](https://github.com/sagemath/sage-prod/files/10649983/trac_9439-hyperbolic_geometry.patch.gz)
+* [attachment: trac_9439-hyperbolic_geometry_review_fc.patch](https://github.com/sagemath/sage-prod/files/10649991/trac_9439-hyperbolic_geometry_review_fc.patch.gz)
fchapoton commented 10 years ago
comment:19

50% coverage

fchapoton commented 10 years ago
comment:20

Attachment: trac_9439-hyperbolic_geometry_review_fc.patch.gz

77% coverage

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago

Attachment: hyperbolic_space.patch.gz

alternative implementation of hyperbolic space

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago

demonstration of the hyperbolic geometry functionality

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago
comment:21

Attachment: hyp_demo.sage.gz

I atteched the long-overdue patch that I mentioned 9 months ago. Sorry for the delay. The patch has the following positive properties:

videlec commented 10 years ago
comment:22

Replying to @greglaun:

I atteched the long-overdue patch that I mentioned 9 months ago. Sorry for the delay. The patch has the following positive properties:

Great! Good job!

Also note the following negative things:

  • Points are not yet implemented as (point, isometry) pairs as suggested in Comment 3.

This was a bad suggestion! It's great that you avoid it.

  • My handling of numerical computations could probably be significantly improved, as can the overall organization. There may be features that are unnecessary or are vestigial from earlier versions.

I will have a look as soon as possible.

  • Symbolic computations can take an incredibly long time. I'm not sure if this is my fault (e.g. I should write functions to deal with this) or simply a drawback of allowing symbolic computations. I intend to comb through the previously attached patches and merge what I can. I have also attached a filecalled hyp_demo.sage that demos the functionality of the implementation.

idem.

Two points:

I suggest that we open two new tickets for those features.

Thanks again for your work on this. I am starting the review and will be back with more technical remarks shortly.

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago
comment:23

Two points:

  • an important feature that you seem to avoid is the unit tangent bundle of the hyperbolic plane which is isomorphic to PSL(2,R). One great thing would be to have another object TangentVector (with a matrix as data). The action of PSL(2,R) on the unit tangent bundle is then just matrix multiplication.
  • your example worksheet should definitely be a thematic tutorial for the Sage documentation

Thanks, I'll look into both of these soon. I have some code for working in Minkowski (2,1) space that I want to use to implement the hyperboloid model in the Lie algebra sl(2,R) since that's what I use in my own research. Several of the functions are for working in SL(2,R)/PSL(2,R). I can take a look at that and see what can be appropriated for use in a TangentVector object.

videlec commented 10 years ago
comment:24

Hi Greg,

There are many nice features in the patch but I did not start to play with. You should start by a big clean:

1) there should be no trailing whitespace

2) the organization of each file should be a header which consists of a string with authors the copyright statement and then the code. There should not be several headers and copyright statements.

3) all methods and functions should be commented and doctested. Running sage -coverage gives

SCORE hyperbolic_object.py: 10.0% (1 of 10)

Missing documentation:
     * line 40: def to_model(self, model)
     * line 49: def to_UHP(self)
     * line 52: def uhp_representation(self)
     * line 55: def model_representation(self)
     * line 58: def representation_in_model(self, model=None)
     * line 96: def to_model(self, model, **options)
     * line 108: def graphics_options(self)

Missing doctests:
     * line 33: def __init__(self, args, **graphics_options)
     * line 88: def __init__(self, args, **graphics_options)

4) the files should be properly included in the sage documentation

Now, more serious issues

5) the objects from your module must be lazy imported and not imported in the global namespace (in order to not slow down sage startup)

6) the method show should not return a graphics object but should rather shows it! You could rename it plot.

7) I agree that it is misleading but CC in Sage is not the set of complex number! In particular the test x in CC does not answer to the question "does my object x modelizes some complex number ?". Precisely CC is the set of floating point complex number with 53 bits of precision. But is it on purpose that you want x in CC as coordinates for a point in the upper half plane ?

8) The string representation "Hyperbolic point whose representation in the Upper Half Plane is +Infinity" is definitely too long! Why not "Point in HH +Infinity".

And finally a design question (which perhaps should be thought of first)

9) I think that the fact of being conformal or bounded etc is not a property of a HyperbolicObject but rather a property of the underlying model. You decided to not design a class for each model, was it on purpose? Such a class may contain all these property. As you see, in my initial patch, it was possible to write

sage: HH
Hyperbolic plane
sage: HH(0)
Boundary point 0

I would prefer to have a dedicated class for each model and be able to construct point/geodesic/polygons from the class (via for example HH.point(data), HH.geodesic(data), etc). You may also move the random_element methods and the various conversions between the models into this parent class.

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago
comment:25

Thanks for the feedback! I didn't know exactly what to do about tests in what was intended to be an abstract class (hyperbeolic_object) that shouldn't be instantiated. I see now that there are other abstract classes in sage and they all have poper doctests, so I'll go ahead and add those in. That should be very simple, as should the rest of the cleanup.

The other issues you mentioned are all things I thought might be problems, so I've given them all a little bit of thought already

Replying to @videlec:

4) the files should be properly included in the sage documentation

Okay, will do.

Now, more serious issues

5) the objects from your module must be lazy imported and not imported in the global namespace (in order to not slow down sage startup)

Okay, I will change this.

6) the method show should not return a graphics object but should rather shows it! You could rename it plot.

I'm actually not quite sure what the difference is. Do you mean that show should make a system call to the default viewer? Is it not sufficient to call a method that makes that call for me? I've noticed in one other module that plot() is implemented and show() is an alias for plot. Would this be a workaround?

7) I agree that it is misleading but CC in Sage is not the set of complex number! In particular the test x in CC does not answer to the question "does my object x modelizes some complex number ?". Precisely CC is the set of floating point complex number with 53 bits of precision. But is it on purpose that you want x in CC as coordinates for a point in the upper half plane ?

This is a hack. I wanted a function that returned True for things that can be converted into floating point complex numbers and "2 + I in CC" returns True even though "2 + I" is a symbolic expression. I didn't want to test more explicitly for symbolic complex numbers because I don't know the symbolic system well enough to be sure to catch all possible cases. And I didn't want to have a test condition that relied on the symbolic apparatus because via profiling I found many cases in which calling functions that were in the symbolics library slowed everything to a crawl. So "x in CC" quickly checks whether something is the right type of object to have "imag()" called on it sensibly. I more than welcome suggestions on how to solve this problem more elegantly without slowing down code. As an example, the functions _clean_points and _shorten_symbolic are both very ugly to my tastes, but I wrote each to address specific issues that arose in profiling and their impact is significant. In a similar way, I find 'x in CC' to be unfortunate but useful.

8) The string representation "Hyperbolic point whose representation in the Upper Half Plane is +Infinity" is definitely too long! Why not "Point in HH +Infinity".

The long strings were a request, and I agree they're much too long. I'll go ahead and change them. I'd like them to contain information about the model, though so that there is less confusion when performing conversion.

And finally a design question (which perhaps should be thought of first)

9) I think that the fact of being conformal or bounded etc is not a property of a HyperbolicObject but rather a property of the underlying model. You decided to not design a class for each model, was it on purpose? Such a class may contain all these property. As you see, in my initial patch, it was possible to write

sage: HH
Hyperbolic plane
sage: HH(0)
Boundary point 0

I would prefer to have a dedicated class for each model and be able to construct point/geodesic/polygons from the class (via for example HH.point(data), HH.geodesic(data), etc). You may also move the random_element methods and the various conversions between the models into this parent class.

I think your way of doing it sounds much better than mine. I had actually been planning on looking more closely at your structure and applying it to mine as a next step. I'll look into this starting tomorrow.

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago
comment:26

Hi Vincent,

I've addressed issues 1-4, and I was hoping you wouldn't mind giving me some guidance about how to handle the remaining issues. Specifically, I have the following questions:

1) Should I post a patch for the fixes of 1-4? Or should I wait until I fix the remaining issues? More generally, should I err on the side of posting more patches (so more people can help) or posting only ones that seem more significant?

2) I like the structure of your code, and I aim to emulate it. Does it make sense for me to combine your class structure with the features in mine and post it in skeletal form before fixing all of the functions? For example, I could post a class diagram, or just an outline of the modules with the guts removed. Or is this step likely to be more work with little payoff? I would ideally like the structure to be as democratically decided as possible.

3) I find your usage of HyperbolicPlane for the upper half plane to be confusing since the HyperbolicDisc is also topologically a plane. I'm used to referring to both as the hyperbolic plane, and I typically differentiate them by specifying which model of the plane. I have been using the abbreviations UHP, PD, KM, and HM which were just decided by fiat to be short and convenient. Is there anything you dislike about this approach to naming? I worry that HyperbolicUHP is too cryptic, but HyperbolicUpperHalfPlane is too long.

videlec commented 10 years ago
comment:27

Hi,

Replying to @greglaun:

I've addressed issues 1-4, and I was hoping you wouldn't mind giving me some guidance about how to handle the remaining issues. Specifically, I have the following questions:

1) Should I post a patch for the fixes of 1-4? Or should I wait until I fix the remaining issues? More generally, should I err on the side of posting more patches (so more people can help) or posting only ones that seem more significant?

Not necessarily. You can fold your two patches into one and post only the update version of your previous patch (to fold two patches hg qfold).

2) I like the structure of your code, and I aim to emulate it. Does it make sense for me to combine your class structure with the features in mine and post it in skeletal form before fixing all of the functions? For example, I could post a class diagram, or just an outline of the modules with the guts removed. Or is this step likely to be more work with little payoff? I would ideally like the structure to be as democratically decided as possible.

Your code definitely contains much more material than mine. If you like better the structure I drafted you are free to reuse it. If you post anything on trac it is always better that it is working code.

In my opinion, as you are currently working on that project, you may choose the datastructure you prefer and indicate clearly in the documentation the concept, why did you choose that design and why did you discard the other ones.

3) I find your usage of HyperbolicPlane for the upper half plane to be confusing since the HyperbolicDisc is also topologically a plane.

I agree. It was just because I always find HH and DD in textbooks and did not ask myself more questions.

I'm used to referring to both as the hyperbolic plane, and I typically differentiate them by specifying which model of the plane. I have been using the abbreviations UHP, PD, KM, and HM which were just decided by fiat to be short and convenient. Is there anything you dislike about this approach to naming? I worry that HyperbolicUHP is too cryptic, but HyperbolicUpperHalfPlane is too long.

I like better UHP, PD, KM and HM but I think they should not be imported in the standard namespace as such (because it is not clear how the user may find them). What about something like:

sage: hyperbolic_geometry.upper_half_plane()
The upper half plane
sage: hyperbolic_geometry.UHP
The upper half plane
etc

That way, we may use tab completion. But perhaps, "hyperbolic_geometry" is a bit too long. If somebody want it in the global namespace it is still possible to do

sage: from sage.XXX.hyperbolic_geometry import *
sage: UHP
The upper half plane

Vincent

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago
comment:28

Hi, just to give an update, I've completely revamped the class and module structure in a way that I like much better. Right now only the basics of the classes are implemented, but those basics are tested and everything is in working order. I'm now starting to add more functionality.

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago

Updated hyperbolic space implementation.

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago
comment:30

Attachment: trac_9439_hyperbolic_space.patch.gz

I just attached a new version. This one allows things like UHP.point(0) or KM.point((1/2, 1/2)), and similarly UHP.geodesic([start, finish]), and UHP.isometry(some_matrix).

The class structure is somewhat complicated, but it's designed to make it easy to implement new models of 2D and 3D geometry. Here's how it works:

To implement another 2D model, one mainly has to put the model information in hyperbolic_model and write down maps to all of the other models. To implement a 3D model, one also has to implement hyperbolic_methods for at least one model (say the upper half space model). In both cases there is a tiny amount of book keeping that must also be done in updating the factory and other modules with one or two lines of code.

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago

Updated demo of hyperbolic space.

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago
comment:31

Attachment: hyp_demo.2.sage.gz

I had occasion yesterday to use my most recent patch for actual computations that involve a lot of model changing, and I realized it's shamefully buggy/nonfunctioning. I fixed a few of the obvious bugs but I'll add more tests before I repost to make sure that I haven't introduced other bugs.

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago

Bug fixes and some new features.

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago

Branch: u/glaun/ticket/9439

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago
comment:32

Attachment: trac_9439_10_03_2013.patch.gz

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago

Changed keywords from hyperbolic geometry, Poincare disc, upper half plane, sd35 to hyperbolic geometry, Poincare disc, upper half plane, Beltrami-Klein, hyperboloid model, sd35

2122803f-ba3a-447c-8835-6d6f4f43e3a5 commented 10 years ago

Changed author from Vincent Delecroix, Martin Raum to Vincent Delecroix, Martin Raum, Greg Laun