Opened 9 years ago

Closed 9 years ago

#16101 closed enhancement (fixed)

Python backend for Polyhedra

Reported by: vbraun Owned by:
Priority: major Milestone: sage-6.3
Component: geometry Keywords: days57
Cc: dimpase, nthiery, jkeitel Merged in:
Authors: Volker Braun Reviewers: Dima Pasechnik, Leif Leonhardy, Frédéric Chapoton, Jan Keitel
Report Upstream: N/A Work issues:
Branch: 595710d (Commits, GitHub, GitLab) Commit: 595710dcc79df80fa147ec6ff8ef1b574a2a9955
Dependencies: Stopgaps:

GitHub link to the corresponding issue

Description (last modified by vbraun)

This ticket implements polyhedra over every exact subfield of the reals in Sage:

    sage: triangle = Polyhedron([(0,0), (1,0), (1/2, sqrt(3)/2)], base_ring=AA)
    sage: triangle.Hrepresentation()
    (An inequality (-1, -0.5773502691896258?) x + 1 >= 0, 
     An inequality (1, -0.5773502691896258?) x + 0 >= 0, 
     An inequality (0, 1.154700538379252?) x + 0 >= 0)

Change History (53)

comment:1 Changed 9 years ago by vbraun

Branch: u/vbraun/double_description

comment:2 Changed 9 years ago by git

Commit: b4e3bdef53301f3acababba5fbf0e4f5d6e63487

Branch pushed to git repo; I updated commit sha1. New commits:

9fb1025finished Hrep2Vrep
456dc07Vrep2Hrep for the case of no lines
b4e3bdestart generic polyhedra backend

comment:3 Changed 9 years ago by git

Commit: b4e3bdef53301f3acababba5fbf0e4f5d6e634874e30ec04eef43fb081941e28c0e3ef1fdc28c227

Branch pushed to git repo; I updated commit sha1. New commits:

30ab4edtowards full docstring coverage
86bd35afull doctest coverage
4e30ec0add to geometry reference manual

comment:4 Changed 9 years ago by git

Commit: 4e30ec04eef43fb081941e28c0e3ef1fdc28c2273e33f0b01abf6ae8005e89d7f94e3dbc201a8861

Branch pushed to git repo; I updated commit sha1. New commits:

3e33f0bclean up docs

comment:5 Changed 9 years ago by vbraun

Authors: Volker Braun
Cc: dimpase nthiery added
Component: PLEASE CHANGEgeometry
Description: modified (diff)
Status: newneeds_review
Summary: double_descriptionPython backend for Polyhedra
Type: PLEASE CHANGEdefect

comment:6 Changed 9 years ago by vbraun

Type: defectenhancement

comment:7 Changed 9 years ago by dimpase

Wow, cool! Have you written your own double description in P/Cython?

comment:8 Changed 9 years ago by vbraun

Keywords: days57 added

Python for now. It first has to be correct, then we can make it faster ;-) This is work done last week during Sage Days 57 in Cernay.

comment:9 Changed 9 years ago by vbraun_spam

Milestone: sage-6.2sage-6.3

comment:10 Changed 9 years ago by rws

Status: needs_reviewneeds_work
Work issues: rebase

comment:11 Changed 9 years ago by jkeitel

Cc: jkeitel added

comment:12 Changed 9 years ago by jkeitel

Branch: u/vbraun/double_descriptionu/jkeitel/double_description
Commit: 3e33f0b01abf6ae8005e89d7f94e3dbc201a8861e69a5a76973d95147a4acac330a62d2b14c9478f
Work issues: rebase

Last 10 new commits:

9ba55ceinitial implementation of double description algorithm
d13fc16finished double description implementation
9fb1025finished Hrep2Vrep
456dc07Vrep2Hrep for the case of no lines
b4e3bdestart generic polyhedra backend
30ab4edtowards full docstring coverage
86bd35afull doctest coverage
4e30ec0add to geometry reference manual
3e33f0bclean up docs
e69a5a7Merged 6.3.beta1

comment:13 Changed 9 years ago by jkeitel

Status: needs_workneeds_review

comment:14 Changed 9 years ago by git

Commit: e69a5a76973d95147a4acac330a62d2b14c9478f78ecff2eb30855c0847a6022e4409fa2fe14d8f0

Branch pushed to git repo; I updated commit sha1. New commits:

78ecff2Trivial changes to double description patch.

comment:15 Changed 9 years ago by jkeitel

I've rebased the branch and made a few very minor changes (almost all formatting). I'd like to review the patch, but since

  • there's still a DEBUG=True
  • I don't know much about polyhedra

that's probably not the best idea. The code looks good though.

comment:16 Changed 9 years ago by vbraun

Branch: u/jkeitel/double_descriptionu/vbraun/double_description

comment:17 Changed 9 years ago by vbraun

Commit: 78ecff2eb30855c0847a6022e4409fa2fe14d8f0ceb86379dd6bed17514279827b73399550b0b7c5

I renamed DEBUG into VERIFY_RESULT. Just a less scary name. The rationale for defaulting to true (for now) is explained in the comment above it.


New commits:

ceb8637rename DEBUG -> VERIFY_RESULT

comment:18 Changed 9 years ago by git

Commit: ceb86379dd6bed17514279827b73399550b0b7c592290e2f9cd2e4293add0544e763873a4b33fe8f

Branch pushed to git repo; I updated commit sha1. New commits:

92290e2Merge branch 'develop' into t/16101/double_description

comment:19 Changed 9 years ago by leif

Is it intentional that one .verify() uses assert while the other prints "incorrect!" (along with the differences) but doesn't raise an exception?

comment:20 Changed 9 years ago by vbraun

Yes

comment:21 Changed 9 years ago by dimpase

Can we have in Examples a nontrivial example of a polytope with irrational vertices, e.g. the 600-cell ?

comment:22 Changed 9 years ago by vbraun

All examples that can't be defined over QQ should be moved to the new backend, but thats for another ticket.

comment:23 in reply to:  22 Changed 9 years ago by dimpase

Replying to vbraun:

All examples that can't be defined over QQ should be moved to the new backend, but thats for another ticket.

For this ticket any serious examples/tests are lacking; that's why it would be great to have something substantially bigger than a triangle.

comment:24 Changed 9 years ago by vbraun

Really big examples probably need some further improvements to the implementation. But I'm obviously not going to work on these until the base implementation is in Sage. We can of course wait years/forever until everything is perfect and only then merge it with Sage. Or we can release early, and release often.

comment:25 in reply to:  24 Changed 9 years ago by dimpase

Replying to vbraun:

Really big examples probably need some further improvements to the implementation. But I'm obviously not going to work on these until the base implementation is in Sage. We can of course wait years/forever until everything is perfect and only then merge it with Sage. Or we can release early, and release often.

I don't think that 600-cell is a big example; it is a 4-dimensional polytope with 120 vertices! If about the only example the new codepath is checked on is a plane triangle, then I say no, this needs work...

Would you like me to construct this test?

comment:26 Changed 9 years ago by chapoton

There is already some code for the vertices of the 120 and 600-cell in graphs.Cell600 and graphs.Cell120. Not a very fast code, alas. But maybe that could help to build the polytope.

comment:27 Changed 9 years ago by jkeitel

I just tried constructing it by simply passing the list of 120 vertices and after 12 minutes and 9 GB of consumed RAM, I killed the computation.

comment:28 Changed 9 years ago by vbraun

You'd have to use QQ[phi] instead of AA as the base field, otherwise its going to blow up for sure.

comment:29 Changed 9 years ago by vbraun

PS: There are many higher dimensional tests for the double description implementation, so saying that "only the triangle is tested" is completely wrong.

comment:30 in reply to:  28 ; Changed 9 years ago by leif

Replying to vbraun:

You'd have to use QQ[phi] instead of AA as the base field, otherwise its going to blow up for sure.

... which could be seen as an argument to add that example (properly). ;-)

comment:31 in reply to:  30 Changed 9 years ago by vbraun

Replying to leif:

... which could be seen as an argument to add that example (properly). ;-)

Feel free to open a ticket for your feature request.

Also, even if it were fast enough for a doctest, the 600-cell would be a terrible way to test the functionality. Field arithmetic is tested elsewhere, so for *testing* you should use examples over QQ where you actually have something to compare to...

comment:32 Changed 9 years ago by jkeitel

In any case, although using QQ[phi] helps enormously with the RAM usage, two hours of runtime still haven't produced a result for me.

However, I do believe that Volker is making a reasonable point. While it would be desirable to have a fast implementation, at least the proposed patch is adding functionality that could eventually be made faster.

comment:33 Changed 9 years ago by leif

Or add the example with AA (and an explanation) and # don't try this at home (aka # not tested).

comment:34 in reply to:  32 Changed 9 years ago by dimpase

Replying to jkeitel:

In any case, although using QQ[phi] helps enormously with the RAM usage, two hours of runtime still haven't produced a result for me.

However, I do believe that Volker is making a reasonable point. While it would be desirable to have a fast implementation, at least the proposed patch is adding functionality that could eventually be made faster.

absence of a sizeable example with irrational numbers suggests that there could be memory leaks which only manifest themselves on such an example; you might make the example a bit smaller by only taking the 96 vertices with irrational coordinates, constructing the snub 24-cell.

comment:35 in reply to:  33 ; Changed 9 years ago by vbraun

Replying to leif:

Or add the example with AA (and an explanation) and # don't try this at home (aka # not tested).

I'd rather spend my time improving things than documenting what currently doesn't work. Of course feel free to add it yourself if you really want it.

comment:36 in reply to:  35 ; Changed 9 years ago by dimpase

Replying to vbraun:

Replying to leif:

Or add the example with AA (and an explanation) and # don't try this at home (aka # not tested).

I'd rather spend my time improving things than documenting what currently doesn't work. Of course feel free to add it yourself if you really want it.

Well, it would be OK adding a line in the docs saying that this is a prototype implementation, and might be painfully slow on largish examples. This would be better than a impression that things work great already.

comment:37 in reply to:  36 ; Changed 9 years ago by vbraun

Replying to dimpase:

Well, it would be OK adding a line in the docs saying that this is a prototype implementation, and might be painfully slow on largish examples. This would be better than a impression that things work great already.

How about "this is the world's fastest code for polyhedra over degree > 2 extensions". Because, as far as I know, there is nothing else. IMHO it does work great.

Also, nothing in the computation really knows about whether a number is rational or not. There might be memory leaks, or really all kinds of bugs, in the underlying field implementation. In fact, since there is a whole load of different fields in Sage it is quite certain that there is a bug in at least one of them. But whats the point of trying to test field implementations in the polyhedra module?

comment:38 Changed 9 years ago by chapoton

Some pyflakes warnings in the new files:

src/sage/geometry/polyhedron/backend_field.py:24: 'QQ' imported but unused
src/sage/geometry/polyhedron/backend_field.py:24: 'ZZ' imported but unused
src/sage/geometry/polyhedron/backend_field.py:25: 'LCM_list' imported but unused
src/sage/geometry/polyhedron/backend_field.py:26: 'matrix' imported but unused

comment:39 Changed 9 years ago by chapoton

and some pep8 comments also:

1       E201 whitespace after '['
8       E225 missing whitespace around operator
1       E231 missing whitespace after ':'
2       E301 expected 1 blank line, found 0
4       E303 too many blank lines (3)
70      E501 line too long (80 characters)
27      W291 trailing whitespace
46      W293 blank line contains whitespace
1       W391 blank line at end of file

comment:40 in reply to:  39 Changed 9 years ago by vbraun

This is consistent with our written whitespace policy.

Replying to chapoton:

and some pep8 comments also:

1       E201 whitespace after '['
8       E225 missing whitespace around operator
1       E231 missing whitespace after ':'
2       E301 expected 1 blank line, found 0
4       E303 too many blank lines (3)
70      E501 line too long (80 characters)
27      W291 trailing whitespace
46      W293 blank line contains whitespace
1       W391 blank line at end of file

comment:41 Changed 9 years ago by git

Commit: 92290e2f9cd2e4293add0544e763873a4b33fe8f1f64cdf1c6add12c8925967132bf1eb9440c7985

Branch pushed to git repo; I updated commit sha1. New commits:

1f64cdfremove unused imports

comment:42 Changed 9 years ago by chapoton

Well, ok, I understand that it is better not to touch whitespaces to avoid conflicts, but maybe you could still make the effort to remove blanks (pep8 errors W***) in the new files that you introduce ?

comment:43 in reply to:  37 Changed 9 years ago by dimpase

Replying to vbraun:

Replying to dimpase:

Well, it would be OK adding a line in the docs saying that this is a prototype implementation, and might be painfully slow on largish examples. This would be better than a impression that things work great already.

How about "this is the world's fastest code for polyhedra over degree > 2 extensions".

well, this will work, if you add :-) (or 8-)) at the end :-)

comment:44 in reply to:  42 ; Changed 9 years ago by vbraun

Replying to chapoton:

Well, ok, I understand that it is better not to touch whitespaces to avoid conflicts, but maybe you could still make the effort to remove blanks (pep8 errors W***) in the new files that you introduce ?

If you care about trailing whitespace then write a commit hook. But I don't have any intention of removing inconspicuous trailing whitespace by hand. If you want to talk about whitespace policies then bring it up on sage-devel.

comment:45 Changed 9 years ago by chapoton

Branch: u/vbraun/double_descriptionpublic/ticket/16101
Commit: 1f64cdf1c6add12c8925967132bf1eb9440c7985595710dcc79df80fa147ec6ff8ef1b574a2a9955

I did the whitespace removal for you, plus found a few other very minor typos.


New commits:

595710dtrac #16101 cosmetic pep8 clean-up and minor details

comment:46 in reply to:  44 Changed 9 years ago by nthiery

Replying to vbraun:

... But I don't have any intention of removing inconspicuous trailing whitespace by hand.

M-x delete-trailing-whitespace :-)

comment:47 Changed 9 years ago by vbraun

Its still worth less than nothing to go around and try to hold up tickets until Frederic Chapoton gets around to detect and fix trailing whitespace. At a rate of about one a day we'll have finally tackled the evils of trailing whitespace in just about 5 years. Seriously, we'll never possibly lose as much developer time over the tiny annoyance of [End] moving you past the last non-whitespace character of the line. If you care about this then you need to develop a process, anything else is just bullshit.

In any case, I'm still waiting for a review.

comment:48 in reply to:  47 ; Changed 9 years ago by dimpase

Replying to vbraun:

In any case, I'm still waiting for a review.

I am ready to give it a positive review, provided that the comment about the code speed you agreed to add gets :-) attached at the end.

comment:49 in reply to:  48 ; Changed 9 years ago by leif

Replying to dimpase:

Replying to vbraun:

In any case, I'm still waiting for a review.

I am ready to give it a positive review, provided that the comment about the code speed you agreed to add gets :-) attached at the end.

Write a commit hook that automatically augments such sentences.

comment:50 in reply to:  49 Changed 9 years ago by dimpase

Status: needs_reviewpositive_review

Replying to leif:

Replying to dimpase:

Replying to vbraun:

In any case, I'm still waiting for a review.

I am ready to give it a positive review, provided that the comment about the code speed you agreed to add gets :-) attached at the end.

Write a commit hook that automatically augments such sentences.

I will file this as a git-trac issue...

comment:51 Changed 9 years ago by vbraun

Reviewers: Dima Pasechnik, Leif Leonhardy

comment:52 Changed 9 years ago by vbraun

Reviewers: Dima Pasechnik, Leif LeonhardyDima Pasechnik, Leif Leonhardy, Frédéric Chapoton, Jan Keitel

comment:53 Changed 9 years ago by vbraun

Branch: public/ticket/16101595710dcc79df80fa147ec6ff8ef1b574a2a9955
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.