Python backend for Polyhedra

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

[git]

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

​9fb1025	finished Hrep2Vrep
​456dc07	Vrep2Hrep for the case of no lines
​b4e3bde	start generic polyhedra backend

[git]

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

​30ab4ed	towards full docstring coverage
​86bd35a	full doctest coverage
​4e30ec0	add to geometry reference manual

[git]

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

​3e33f0b

clean up docs

[dimpase]

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

[vbraun]

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.

[jkeitel]

Last 10 new commits:

​9ba55ce	initial implementation of double description algorithm
​d13fc16	finished double description implementation
​9fb1025	finished Hrep2Vrep
​456dc07	Vrep2Hrep for the case of no lines
​b4e3bde	start generic polyhedra backend
​30ab4ed	towards full docstring coverage
​86bd35a	full doctest coverage
​4e30ec0	add to geometry reference manual
​3e33f0b	clean up docs
​e69a5a7	Merged 6.3.beta1

[git]

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

​78ecff2

Trivial changes to double description patch.

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

[vbraun]

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:

​ceb8637

rename DEBUG -> VERIFY_RESULT

[git]

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

​92290e2

Merge branch 'develop' into t/16101/double_description

[leif]

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

[vbraun]

Yes

[dimpase]

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

[vbraun]

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

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

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

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

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

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

[vbraun]

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

[vbraun]

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

[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). ;-)

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

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

[leif]

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

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

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

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

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

[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

[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

[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

[git]

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

​1f64cdf

remove unused imports

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

[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 :-)

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

[chapoton]

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

---

New commits:

​595710d

trac #16101 cosmetic pep8 clean-up and minor details

[nthiery]

Replying to vbraun:

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

M-x delete-trailing-whitespace :-)

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

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

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

[dimpase]

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