Opened 7 years ago

Closed 7 years ago

#18241 closed enhancement (fixed)

Great speedup in polytopes construction with generic backend

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.7
Component: geometry Keywords:
Cc: vbraun, ncohen Merged in:
Authors: Vincent Delecroix Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: c5b15bf (Commits, GitHub, GitLab) Commit: c5b15bf0297ee8626e9dcadf75a325aad49673af
Dependencies: #18215 Stopgaps:

Status badges

Description (last modified by vdelecroix)

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 #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:

  1. 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 #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)
  1. Start with a trivial case in NumberField.__cmp__.

Attachments (1)

polyhedron_test.py (574 bytes) - added by vdelecroix 7 years ago.

Download all attachments as: .zip

Change History (28)

comment:1 Changed 7 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Branch set to u/vdelecroix/18241
  • Commit set to 99c670831a4064246d2cdb2aec32a3e51fd4fd7c
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

3ec20b4Trac 18215: Faster hash for quadratic number fields
562d81aTrac 18241: better double description (Hrep2Vrep, Vrep2Hrep)
e28fdffTrac 18241: tiny modifs in constructor/parent
99c6708Trac 18241: trivial case in NumberField.__cmp__

Changed 7 years ago by vdelecroix

comment:2 Changed 7 years ago by vdelecroix

  • Description modified (diff)

comment:3 follow-up: Changed 7 years ago by ncohen

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.

Last edited 7 years ago by ncohen (previous) (diff)

comment:4 in reply to: ↑ 3 Changed 7 years ago by vdelecroix

  • Description modified (diff)

Replying to ncohen:

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!

comment:5 follow-up: Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_work

Looks like your mutable object is also hashable

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

comment:6 in reply to: ↑ 5 Changed 7 years ago by vdelecroix

Replying to ncohen:

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__())
Last edited 7 years ago by vdelecroix (previous) (diff)

comment:7 Changed 7 years ago by ncohen

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

comment:8 follow-up: Changed 7 years ago by ncohen

Actually, no...

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

We should probably make SageObject.__hash__ raise a NotImplementedError

comment:9 in reply to: ↑ 8 Changed 7 years ago by vdelecroix

Replying to ncohen:

Actually, no...

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

We should probably make SageObject.__hash__ raise a NotImplementedError

Or

class A:
    __hash__ = None

comment:10 Changed 7 years ago by git

  • Commit changed from 99c670831a4064246d2cdb2aec32a3e51fd4fd7c to 3c573aef7df1659213bec2614f9ba2b788c1f4fa

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

3c573aeTrac 18241: simpler import + remove SageObject inheritance

comment:11 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:12 follow-up: Changed 7 years ago by ncohen

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

comment:13 in reply to: ↑ 12 ; follow-up: Changed 7 years ago by vdelecroix

Replying to ncohen:

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.

comment:14 in reply to: ↑ 13 Changed 7 years ago by ncohen

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

comment:15 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:16 Changed 7 years ago by git

  • Commit changed from 3c573aef7df1659213bec2614f9ba2b788c1f4fa to 770ad60c6812e524b6d957b2179bd486e2d3896e

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

770ad60Trac 18241: move code in double_description.py

comment:17 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review
  • 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.

comment:18 follow-up: Changed 7 years ago by ncohen

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

comment:19 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:20 in reply to: ↑ 18 Changed 7 years ago by vdelecroix

Hello,

Replying to ncohen:

  • 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

comment:21 Changed 7 years ago by git

  • Commit changed from 770ad60c6812e524b6d957b2179bd486e2d3896e to c5b15bf0297ee8626e9dcadf75a325aad49673af

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

2fba20cTrac 18241: avoid a repetition in the doc
bee81efTrac 18215: fix a failing doctest
c5b15bfTrac 18241: merge failing doctest from #18215

comment:22 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:23 follow-up: Changed 7 years ago by ncohen

  • Status changed from needs_review to positive_review

Okayyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

comment:24 in reply to: ↑ 23 Changed 7 years ago by vdelecroix

Replying to ncohen:

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!

Last edited 7 years ago by vdelecroix (previous) (diff)

comment:25 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work

reviewer name

comment:26 Changed 7 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_work to positive_review

comment:27 Changed 7 years ago by vbraun

  • Branch changed from u/vdelecroix/18241 to c5b15bf0297ee8626e9dcadf75a325aad49673af
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.