Great speedup in polytopes construction with generic backend #18241

videlec · 2015-04-17T14:24:46Z

Construction of polytopes with number field coordinates are very slow. There are several reasons for that:

quadratic number field element hash is slow (already solved in Huge speed up for hash of quadratic number field elements #18215)
NumberField.__cmp__ is slow
we can avoid many useless copies and recomputations in the algorithm Vrep2Hrep and Hrep2Vrep

After applying the branch the speedup is really cool. Using polyhedron_test.py I got

Before

sage: %runfile polyhedron_test.py
sage: %time gr = great_rhombicuboctahedron()
CPU times: user 4.66 s, sys: 24 ms, total: 4.68 s
Wall time: 4.66 s

After

sage: %runfile polyhedron_test.py
sage: %time gr = great_rhombicuboctahedron()
CPU times: user 292 ms, sys: 28 ms, total: 320 ms
Wall time: 306 ms

(But I am still not able to build the 600-cell)

Modifications with the branch:

In the double description file
- use itertools instead of whatever sage/combinat/*
- use base_ring.zero() and base_ring.one() instead of the Python integer 0 and 1. That prevents many coercions.
- make the method add_inequality so that the object is changed inplace instead of returning a new instance. I had to change the type of the attribute from tuples to lists.
- add a cache for matrix spaces (see constructing matrices is very slow #18231). These are the methods _matrix_space and _matrix
- implement a cache for the method .zero_set (note that this was needed because the object is no more immutable, self.A will grow in add_inequality)
Start with a trivial case in NumberField.__cmp__.

Depends on #18215

CC: @vbraun @nathanncohen

Component: geometry

Author: Vincent Delecroix

Branch/Commit: c5b15bf

Reviewer: Nathann Cohen

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

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

videlec · 2015-04-17T14:26:58Z

Branch: u/vdelecroix/18241

videlec · 2015-04-17T14:26:58Z

New commits:

`3ec20b4`	`Trac 18215: Faster hash for quadratic number fields`
`562d81a`	`Trac 18241: better double description (Hrep2Vrep, Vrep2Hrep)`
`e28fdff`	`Trac 18241: tiny modifs in constructor/parent`
`99c6708`	`Trac 18241: trivial case in NumberField.__cmp__`

videlec · 2015-04-17T14:26:58Z

Commit: 99c6708

videlec · 2015-04-17T14:26:58Z

Author: Vincent Delecroix

videlec · 2015-04-17T14:42:30Z

comment:2

Attachment: polyhedron_test.py.gz

nathanncohen · 2015-04-18T08:39:08Z

comment:3

Could you say in the ticket's description what the branch does?

Every single thing that you do without explanation, the reviewer has to figure out from the diff file.

videlec · 2015-04-18T09:27:15Z

comment:4

Replying to @nathanncohen:

Could you say in the ticket's description what the branch does?

Every single thing that you do without explanation, the reviewer has to figure out from the diff file.

done!

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

comment:5

Looks like your mutable object is also hashable

sage: DD.__hash__()
1042963791458606606
sage: DD.add_inequality(vector([1,0,0]))
sage: DD.__hash__()
-1000165618804906370

videlec · 2015-04-18T10:39:38Z

comment:6

Replying to @nathanncohen:

Looks like your mutable object is also hashable

sage: DD.__hash__()
1042963791458606606
sage: DD.add_inequality(vector([1,0,0]))
sage: DD.__hash__()
-1000165618804906370

F!!!** Sage objects!

cdef class SageObject:
...
    def __hash__(self):
        return hash(self.__repr__())

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

comment:7

Unless all SageObject must be immutable, I guess that it should be removed (in another ticket that will become another war)

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

comment:8

Actually, no...

sage: class A:
....:     pass
sage: hash(A())
-9223363253024015589

We should probably make SageObject.__hash__ raise a NotImplementedError

videlec · 2015-04-18T10:46:43Z

comment:9

Replying to @nathanncohen:

Actually, no...
sage: class A:
....:     pass
sage: hash(A())
-9223363253024015589
We should probably make SageObject.__hash__ raise a NotImplementedError

Or

class A:
    __hash__ = None

sagetrac-git · 2015-04-18T10:55:07Z

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

`3c573ae`	`Trac 18241: simpler import + remove SageObject inheritance`

sagetrac-git · 2015-04-18T10:55:07Z

Changed commit from 99c6708 to 3c573ae

nathanncohen · 2015-04-18T13:27:24Z

comment:12

About this branch:

zero_set: why don't you just call DD.zero_set.clear_cache() instead of rewriting the caching mechanism? If you do want to keep this self.cache please make the name more specific.
A_matrix : returns a pointer toward a mutable internal object.

Err

Add an inequality to the double description with the inequality ``a``
added.

I do not like this '_matrix' function very much. Its name is not very clear (matrix_from_cached_vector_space?) but what about just doing this 'if' twice (it is called twice)?

Nathann

videlec · 2015-04-18T13:41:05Z

comment:13

Replying to @nathanncohen:

About this branch:

zero_set: why don't you just call DD.zero_set.clear_cache() instead of rewriting the caching mechanism? If you do want to keep this self.cache please make the name more specific.

Nope. If you call the function with the same ray argument you do not want to recompute it from scratch.

I do not like this '_matrix' function very much. Its name is not very clear (matrix_from_cached_vector_space?) but what about just doing this 'if' twice (it is called twice)?

Me neither. That's why I opened #18231. The function just constructs a matrix, why the name is badly chosen? You will get the very same answer as calling matrix(self.problem.base_ring(), data). Except that it is faster. What about .build_matrix and .build_matrix_space?

I do not understand you remark about the if.

nathanncohen · 2015-04-18T13:48:41Z

comment:14

Hello,

Nope. If you call the function with the same ray argument you do not want to recompute it from scratch.

Oh, okay. Then change the cache's name please

I do not like this '_matrix' function very much. Its name is not very clear (matrix_from_cached_vector_space?) but what about just doing this 'if' twice (it is called twice)?

Me neither. That's why I opened #18231.

Then should it be really fixed inside of this class? Or do we keep this code as it is and try to solve the #18231 instead.

The function just constructs a matrix, why the name is badly chosen? You will get the very same answer as calling matrix(self.problem.base_ring(), data). Except that it is faster.

Precisely because the name does not reflect the difference. matrix_from_cached_vector_space does.

What about .build_matrix and .build_matrix_space?

I hate this class already.

I do not understand you remark about the if.

Oh. Well, because all that 'matrix' does is a if. If it is not a function of its own, you just have to copy this 'if' around.

Nathann

sagetrac-git · 2015-04-18T14:44:47Z

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

`770ad60`	`Trac 18241: move code in double_description.py`

sagetrac-git · 2015-04-18T14:44:47Z

Changed commit from 3c573ae to 770ad60

videlec · 2015-04-18T14:47:14Z

comment:17

I get rid of def _matrix and move Problem._matrix_space -> DoubleDescription.matrix_space.
I changed .cache -> .zero_set_cache
I modified the output of zero_set to return Python sets instead of tuple (since the most important operation on them is the intersection)

Needs review again.

nathanncohen · 2015-04-18T16:17:33Z

comment:18

Yoooooooooooooo !

Looks good, almost good to go. Just two things:

This sentence repeats itself

Add an inequality to the double description with the inequality ``a``
added.

What is the difference between those two lines?

lines = self._linear_subspace.matrix().rows()
lines = self._linear_subspace.basis_matrix().rows()

Nathann

videlec · 2015-04-18T16:20:53Z

comment:20

Hello,

Replying to @nathanncohen:

What is the difference between those two lines?
lines = self._linear_subspace.matrix().rows()
lines = self._linear_subspace.basis_matrix().rows()

linear_subspace.matrix calls linear_subspace.basis_matrix. Having aliases is cool, but avoiding using them is cooler ;-)

Vincent

sagetrac-git · 2015-04-18T16:25:39Z

Changed commit from 770ad60 to c5b15bf

sagetrac-git · 2015-04-18T16:25:39Z

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

`2fba20c`	`Trac 18241: avoid a repetition in the doc`
`bee81ef`	`Trac 18215: fix a failing doctest`
`c5b15bf`	`Trac 18241: merge failing doctest from #18215`

nathanncohen · 2015-04-18T16:28:09Z

comment:23

Okayyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

videlec · 2015-04-18T16:32:37Z

comment:24

Replying to @nathanncohen:

Okayyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

Great! Thanks. It becomes reasonable to start using the generic backend.

Next step: avoid the recomputation of vertices! The algorithm is currently

INPUT: vertices
OUTPUT: (vertices, hyperplanes)
ALGO:
  1. compute hyperplanes from vertices (with no redundancy)
  2. recompute vertices from hyperplanes (with no redundancy)
  3. return (vertices, hyperplanes)

And it is precisely step 2 which takes an infinite amount of time for the 600-cell!

vbraun · 2015-04-18T23:45:38Z

comment:25

reviewer name

nathanncohen · 2015-04-19T05:33:31Z

Reviewer: Nathann Cohen

vbraun · 2015-04-19T16:44:59Z

Changed branch from u/vdelecroix/18241 to c5b15bf

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

videlec added c: geometry labels Apr 17, 2015

This comment has been minimized.

Sign in to view

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

This comment has been minimized.

Sign in to view

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 removed the s: needs review label Apr 18, 2015

nathanncohen mannequin added the s: needs work label Apr 18, 2015

videlec added s: needs review and removed s: needs work labels Apr 18, 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

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

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

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

vbraun closed this as completed in aa1939f Apr 19, 2015

videlec mentioned this issue Sep 7, 2015

remove naive __hash__ from SageObject #18246

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Great speedup in polytopes construction with generic backend #18241

Great speedup in polytopes construction with generic backend #18241

videlec commented Apr 17, 2015

videlec commented Apr 17, 2015

videlec commented Apr 17, 2015

This comment has been minimized.

videlec commented Apr 17, 2015

videlec commented Apr 17, 2015

videlec commented Apr 17, 2015

This comment has been minimized.

nathanncohen mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

This comment has been minimized.

nathanncohen mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

nathanncohen 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

videlec commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

vbraun commented Apr 18, 2015

nathanncohen mannequin commented Apr 19, 2015

vbraun commented Apr 19, 2015

Great speedup in polytopes construction with generic backend #18241

Great speedup in polytopes construction with generic backend #18241

Comments

videlec commented Apr 17, 2015

videlec commented Apr 17, 2015

videlec commented Apr 17, 2015

This comment has been minimized.

videlec commented Apr 17, 2015

videlec commented Apr 17, 2015

videlec commented Apr 17, 2015

This comment has been minimized.

nathanncohen mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

This comment has been minimized.

nathanncohen mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

nathanncohen 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

videlec commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

vbraun commented Apr 18, 2015

nathanncohen mannequin commented Apr 19, 2015

vbraun commented Apr 19, 2015