#11849 closed defect (fixed)
cddlib test in ppl.pyx takes a very long time
Reported by: | jdemeyer | Owned by: | was |
---|---|---|---|
Priority: | blocker | Milestone: | sage-4.7.2 |
Component: | interfaces | Keywords: | sd34 Parma Polyhedra Library |
Cc: | vbraun, leif | Merged in: | sage-4.7.2.alpha3 |
Authors: | Volker Braun | Reviewers: | Jeroen Demeyer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
From the file sage/libs/ppl.pyx
starting at line 112:
The computation finishes without noticeable delay on my desktop (timeit measures it to be 35msec). Cddlib needs about 3 minutes on the same hardware:: sage: basis = range(0,6) sage: x = [ Variable(i) for i in basis ] sage: gs = [ tuple(coeff) for coeff in permutations(basis) ] sage: Polyhedron(vertices=gs) # long time A 5-dimensional polyhedron in QQ^6 defined as the convex hull of 720 vertices.
This test takes minutes (as is claimed). This regularly causes timeouts when testing Sage on Skynet.
On sage.math.washington.edu, sage-4.7.2.alpha0:
sage: from sage.libs.ppl import Variable, Generator_System, point, C_Polyhedron sage: basis = range(0,6) sage: x = [ Variable(i) for i in basis ] sage: gs = [ tuple(coeff) for coeff in permutations(basis) ] sage: time Polyhedron(vertices=gs) A 5-dimensional polyhedron in QQ^6 defined as the convex hull of 720 vertices. Time: CPU 0.14 s, Wall: 218.94 s
Apply trac_11849_shorter_long_ppl_test.patch and 11849_reviewer.patch
Attachments (2)
Change History (12)
comment:1 Changed 10 years ago by
- Description modified (diff)
- Keywords Parma Polyhedra Library added
comment:2 follow-up: ↓ 3 Changed 10 years ago by
comment:3 in reply to: ↑ 2 Changed 10 years ago by
Replying to vbraun:
sage: C_Polyhedron(gs) }}} We could turn the
Polyhedron()
call into a shorter# long time
example.
Yes, please do that. I think you should aim for something taking at most 10 seconds or so on sage.math
.
Also, I would rephrase the paragraph starting from line 112 as
The above computation (using PPL) finishes without noticeable delay (timeit measures it to be 5ms on sage.math). Below we do the same computation with cddlib, which needs about 10 seconds on the same hardware:: sage: basis = range(0,6) sage: x = [ Variable(i) for i in basis ] sage: gs = [ tuple(coeff) for coeff in permutations(basis) ] sage: Polyhedron(vertices=gs) # long time (10s on sage.math, 2011) A 5-dimensional polyhedron in QQ^6 defined as the convex hull of 720 vertices.
comment:4 Changed 10 years ago by
- Description modified (diff)
- Status changed from new to needs_review
The attached patch switches to an computationally easier doctest problem. Now it should complete in < 5.
comment:5 Changed 10 years ago by
- Description modified (diff)
- Reviewers set to Jeroen Demeyer
- Status changed from needs_review to positive_review
positive_review modulo the reviewer patch.
comment:6 Changed 10 years ago by
- Description modified (diff)
- Summary changed from ppl.pyx test takes a very long time contrary to what is claimed to cddlib test in ppl.pyx takes a very long time
comment:7 Changed 10 years ago by
Great, thanks!
comment:8 Changed 10 years ago by
- Merged in set to sage-4.7.2.alpha3
- Resolution set to fixed
- Status changed from positive_review to closed
comment:9 Changed 10 years ago by
- Keywords sd34 added
Changed 10 years ago by
comment:10 Changed 10 years ago by
Fixed commit message of my reviewer patch.
You are looking at the wrong code. The
call takes a very long time, as stated. The PPL computation is a few lines above, and completes within miliseconds:
We could turn the
Polyhedron()
call into a shorter# long time
example.Also, I have some patches on trac to switch
Polyhedron
to PPL, as well.