A lot of polytope constructors are broken #18213

videlec · 2015-04-15T21:42:33Z

A lot of polytopes constructors in sage.geometry.polyhedron.library. For example

The Rhombicuboctahedron does not return what it should (as Python division was thought as Sage integer divisions). There is in the code

verts = [ [-3/2, -1/2, -1/2], [-3/2, -1/2, 1/2], [-3/2, 1/2, -1/2],
...

The great_rhombicuboctahedron is defined over QQ but it should be defined over QQ[sqrt(2)]! There are in two places rough approximation of sqrt(2) in the code

v1 = QQ(131739771357/54568400000)   # ~ sqrt(2) + 1 but actually 2 due to Python division
v2 = QQ(104455571357/27284200000)   # ~ 2 sqrt(2) but actually 3 due to Python division

Instead, we should use the base_ring argument (with appropriate defaults) and use base_ring(2).sqrt() instead.

The functions unrelated to construction of Polytopes are moved out of the class Polytopes:
- Polytopes.orthonormal_1, Polytopes.project_1 will be renamed respectively zero_sum_projection and project_points
- the one line Polytopes._pfunc is just removed

While we're at it, remove the deprecations from #11634.

During the process I discovered two annoying bugs:

Bug in volume computation of polyhedron #18214 Bug in volume computation of polyhedron
disallow non exact fields for the 'field' backend #18220 Bug when creating a polyhedron with coefficients in RR
Moreover, we can get a great speed up with the following because many polytopes have now coordinates in a quadratic number fields:
Huge speed up for hash of quadratic number field elements #18215: Huge speed up for hash of quadratic number field elements
Native _mpfr_ method on quadratic number field elements #18226: Native _mpfr_ method on quadratic number field elements

Depends on #18211

CC: @nathanncohen

Component: geometry

Author: Vincent Delecroix

Branch/Commit: a58da00

Reviewer: Nathann Cohen

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

The text was updated successfully, but these errors were encountered:

videlec · 2015-04-16T09:13:06Z

Author: Vincent Delecroix

videlec · 2015-04-16T09:13:06Z

comment:3

I have a big commit to push in few minutes...

videlec · 2015-04-16T14:33:54Z

New commits:

`5110cc9`	`Trac 18211: use LattE to compute the Ehrhart polynomial`
`cf2a10f`	`Trac 18211: another example using Birkhoff_polytope`
`ca8da5a`	`Trac 18211: fixed spelling LattE integrale`
`d52053c`	`Trac 18211: check error + options`
`0f5122b`	`Trac 18211: fix command line arguments`
`b877932`	`Trac 18211: fix arguments + doctests + cwd=SAGE_TMP`
`3b30bc8`	`Trac 18213: rewrite the polyhedron library`
`e598e28`	`Trac 18123: fix doctests`

videlec · 2015-04-16T14:33:54Z

Branch: u/vdelecroix/18123

videlec · 2015-04-16T14:33:54Z

Commit: e598e28

nathanncohen · 2015-04-16T14:34:43Z

comment:5

Depends on #18211?

videlec · 2015-04-16T14:35:31Z

Dependencies: #18211

videlec · 2015-04-16T14:35:31Z

comment:6

Replying to @nathanncohen:

Depends on #18211?

Yes

New commits:

`c44b53e`	`Trac 18213: fix doctests`

videlec · 2015-04-16T14:35:31Z

Changed commit from e598e28 to c44b53e

videlec · 2015-04-16T14:35:31Z

Changed branch from u/vdelecroix/18123 to u/vdelecroix/18213

sagetrac-git · 2015-04-16T15:36:59Z

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

`6e7cf21`	`trac #18211: Seealsos`

sagetrac-git · 2015-04-16T15:36:59Z

Changed commit from c44b53e to 6e7cf21

sagetrac-git · 2015-04-16T17:15:14Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`227e14a`	`Trac 18213: Seealsos`
`eef42af`	`Trac 18213: documentation`

sagetrac-git · 2015-04-16T17:15:14Z

Changed commit from 6e7cf21 to eef42af

jdemeyer · 2015-04-16T20:56:29Z

comment:11

The golden_ratio() can obviously be defined in terms of sqrt(5), so I don't see the need for that. I'm also really wondering whether you need the custom sqrt() function, doesn't QuadraticField(n) work?

videlec · 2015-04-16T22:13:32Z

comment:12

Replying to @jdemeyer:

The golden_ratio() can obviously be defined in terms of sqrt(5), so I don't see the need for that. I'm also really wondering whether you need the custom sqrt() function, doesn't QuadraticField(n) work?

Right. The problem of embedding should be done elsewhere (my version embedds in QQbar whereas the generic QuadraticField(n) embedds into RLF).

videlec · 2015-04-16T22:40:20Z

comment:13

Replying to @videlec:

Replying to @jdemeyer:

The golden_ratio() can obviously be defined in terms of sqrt(5), so I don't see the need for that. I'm also really wondering whether you need the custom sqrt() function, doesn't QuadraticField(n) work?

Right. The problem of embedding should be done elsewhere (my version embedds in QQbar whereas the generic QuadraticField(n) embedds into RLF).

Here is one reason. The generator name of QuadraticField(2) is a and it better be sqrt2 in this case. For the golden ratio, the advantage is that its get printed as phi. In particular you have

sage: polytopes.icosahedron().volume()
5/6*phi + 5/6

The answer 5/6*a + 5/6 would have been terrible here. I have nothing against using phi = (sqrt5+1)/2. So I will at least remove this one. For the quadratic fields, one option is to globally make this change in another ticket. What do you think?

sagetrac-git · 2015-04-17T07:14:32Z

Changed commit from eef42af to c1804d5

sagetrac-git · 2015-04-17T07:14:32Z

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

`c1804d5`	`Trac 18213: (review) remove sqrt/golden_ratio + doc`

nathanncohen · 2015-04-17T21:46:23Z

comment:35

        OUTPUT: 

        EXAMPLES::

videlec · 2015-04-17T21:46:47Z

comment:36

Replying to @nathanncohen:

Funny. There is no automorphism_group function for polytopes O_o

Yes! This is very sad... But you have to be careful about what it means. There is the combinatorial automorphism group and the isometry group. I have no idea how to implement the latter efficiently.

nathanncohen · 2015-04-17T21:54:04Z

comment:37

Most probably the ugliest thing I ever saw

sage: Sequence([Graph()]).universe()
<class 'sage.graphs.graph.Graph'>
sage: Sequence([Graph(),1]).universe()
Category of objects
sage: Sequence([1]).universe()
Integer Ring

nathanncohen · 2015-04-17T21:55:34Z

comment:38

HMmmmmmmm... I don't exactly know what the isometry group is, but let's try anyway: what about defining a complete graph on your points, in which each edge has a color associated to its length. Wouldn't the automorphism group of that be what you want?

nathanncohen · 2015-04-17T21:58:13Z

comment:39

Okayyyyyyyyyyyyyy. End of the review. Nothing else to add ;-)

Very good job. This code needed to be cleaned, and it is much better now.

But please, next time: smaller patches. You waste your reviewers' health :-P

Nathann

videlec · 2015-04-17T21:59:00Z

comment:40

Replying to @nathanncohen:

HMmmmmmmm... I don't exactly know what the isometry group is, but let's try anyway: what about defining a complete graph on your points, in which each edge has a color associated to its length. Wouldn't the automorphism group of that be what you want?

That is a valid definition. But the standard one is the set of orthogonal matrices that preserve the polyhedron. And it would be nice for isometry_group to be a finite matrix group (and not permutations)!

sagetrac-git · 2015-04-17T22:20:28Z

Changed commit from fac3cff to 1a82754

sagetrac-git · 2015-04-17T22:20:28Z

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

`21e70a7`	`Trac 18213: review commit`
`1a82754`	`Trac 18213: doctest fix`

videlec · 2015-04-17T22:21:00Z

comment:42

Patchbot should be happy after that.

nathanncohen · 2015-04-18T06:50:04Z

comment:43

Some broken doctests in the patchbot's report. Also, can you be sure that the sqrt(6.) / factorial(5) are not subject to numerical noise? There is no #tol on them right now.

Nathann

nathanncohen · 2015-04-18T07:48:45Z

comment:44

Hmmmmmm.. I can't seem to find on google an implementation of an isometry group function anywhere O_o

sagetrac-jkeitel · 2015-04-18T08:41:25Z

comment:45

Hi Vincent and Nathann

Just a quick comment, as I'm not sure how useful this will be for general polyhedra: There is a method for lattice polytopes:
LatticePolytope_PPL (in sage.geometry.polyhedron.ppl_lattice_polytope) has a method lattice_automorphism_group()

Cheers,
Jan

sagetrac-git · 2015-04-18T09:30:03Z

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

`120c1e9`	`Trac 18213: more abs tol in doctests`
`d09d8a5`	`Trac 18211: forgot a # optional in the doctest`
`a58da00`	`Trac 18213: merge failed doctest from #18211`

sagetrac-git · 2015-04-18T09:30:03Z

Changed commit from 1a82754 to a58da00

videlec · 2015-04-18T09:30:55Z

comment:48

Replying to @nathanncohen:

Some broken doctests in the patchbot's report. Also, can you be sure that the sqrt(6.) / factorial(5) are not subject to numerical noise? There is no #tol on them right now.

I don't know... Patchbot did not complain about this.

nathanncohen · 2015-04-18T10:18:18Z

comment:50

Okayyyyyyy. Then positive_review!

Nathann

nathanncohen · 2015-04-18T10:18:18Z

Reviewer: Nathann Cohen

vbraun · 2015-04-19T01:52:06Z

Changed branch from u/vdelecroix/18213 to a58da00

videlec added this to the sage-6.7 milestone Apr 15, 2015

videlec added c: geometry labels Apr 15, 2015

This comment has been minimized.

Sign in to view

videlec added the s: needs review label Apr 16, 2015

This comment has been minimized.

Sign in to view

videlec added s: needs work and removed s: needs review labels Apr 16, 2015

nathanncohen mannequin added s: needs work and removed s: needs review labels Apr 18, 2015

videlec added s: needs review and removed s: needs work labels Apr 18, 2015

nathanncohen mannequin added s: positive review and removed s: needs review labels Apr 18, 2015

videlec changed the title ~~A lot of polytopes constructor are broken~~ A lot of polytope constructors are broken Apr 18, 2015

vbraun removed the s: positive review label Apr 19, 2015

vbraun closed this as completed in 4f541c8 Apr 19, 2015

This was referenced Apr 19, 2015

Huge speed up for hash of quadratic number field elements #18215

Closed

Missing polytopes in the library #18225

Closed

constructing matrices is very slow #18231

Closed

A lot of polytope constructors are broken #18213

A lot of polytope constructors are broken #18213

Comments

videlec commented Apr 15, 2015

This comment has been minimized.

videlec commented Apr 16, 2015

videlec commented Apr 16, 2015

videlec commented Apr 16, 2015

videlec commented Apr 16, 2015

videlec commented Apr 16, 2015

This comment has been minimized.

nathanncohen mannequin commented Apr 16, 2015

videlec commented Apr 16, 2015

videlec commented Apr 16, 2015

videlec commented Apr 16, 2015

videlec commented Apr 16, 2015

This comment has been minimized.

sagetrac-git mannequin commented Apr 16, 2015

sagetrac-git mannequin commented Apr 16, 2015

sagetrac-git mannequin commented Apr 16, 2015

sagetrac-git mannequin commented Apr 16, 2015

This comment has been minimized.

jdemeyer commented Apr 16, 2015

videlec commented Apr 16, 2015

videlec commented Apr 16, 2015

sagetrac-git mannequin commented Apr 17, 2015

sagetrac-git mannequin commented Apr 17, 2015

nathanncohen mannequin commented Apr 17, 2015

videlec commented Apr 17, 2015

nathanncohen mannequin commented Apr 17, 2015

nathanncohen mannequin commented Apr 17, 2015

nathanncohen mannequin commented Apr 17, 2015

videlec commented Apr 17, 2015

sagetrac-git mannequin commented Apr 17, 2015

sagetrac-git mannequin commented Apr 17, 2015

videlec commented Apr 17, 2015

nathanncohen mannequin commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

sagetrac-jkeitel mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

vbraun commented Apr 19, 2015