Opened 7 years ago
Closed 4 years ago
#18214 closed defect (fixed)
Bug in volume computation of polyhedron
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage8.7 
Component:  geometry  Keywords:  bug 
Cc:  jipilab, moritz, ghtom111  Merged in:  
Authors:  Dima Pasechnik  Reviewers:  Matthias Koeppe,Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  b6758cd (Commits, GitHub, GitLab)  Commit:  b6758cd0a4535855e38e0a765d11a2db7405d3bb 
Dependencies:  Stopgaps: 
Description (last modified by )
sage: polytopes.dodecahedron(base_ring=RDF).volume() Traceback (most recent call last): ... ZeroDivisionError: input matrix must be nonsingular
The same error is triggered by
sage: D=polytopes.dodecahedron(base_ring=RDF) sage: D.triangulate()
Change History (24)
comment:1 Changed 7 years ago by
 Keywords bug added
comment:2 Changed 6 years ago by
 Milestone changed from sage6.7 to sage7.3
comment:3 Changed 6 years ago by
 Description modified (diff)
comment:4 Changed 6 years ago by
 Branch set to u/chapoton/18214
 Commit set to d409a4cad8c4936dfe25e3cf0d5fa5fb59188e77
 Status changed from new to needs_review
comment:5 Changed 6 years ago by
I think you also need to change method PointConfiguration.contained_simplex
.
And that epsilon should indeed be customizable. And when PointConfiguration
is called from Polyhedron_RDF
, it should use the epsilons from Polyhedron_RDF._is_zero
etc.
comment:6 Changed 6 years ago by
 Milestone changed from sage7.3 to sage7.4
 Reviewers set to Matthias Koeppe
 Status changed from needs_review to needs_work
comment:7 Changed 6 years ago by
 Commit changed from d409a4cad8c4936dfe25e3cf0d5fa5fb59188e77 to 11dc0330037d336f82ac55ad81b353b7670dd6ae
Branch pushed to git repo; I updated commit sha1. New commits:
11dc033  Merge branch 'u/chapoton/18214' in 7.5.b3

comment:8 Changed 4 years ago by
 Commit changed from 11dc0330037d336f82ac55ad81b353b7670dd6ae to e042c426aa810d3d92a03b8ea6b0f87ff36cc04a
comment:9 Changed 4 years ago by
 Cc jipilab added
comment:10 Changed 4 years ago by
 Milestone changed from sage7.4 to sage8.2
comment:11 Changed 4 years ago by
 Cc moritz added
comment:12 Changed 4 years ago by
 Cc ghtom111 added
comment:13 followup: ↓ 14 Changed 4 years ago by
Is this still reproducable? I get
sage: polytopes.dodecahedron(base_ring=RDF).volume() 6.4520359589542045
comment:14 in reply to: ↑ 13 ; followup: ↓ 16 Changed 4 years ago by
Replying to vbraun:
Is this still reproducable? I get
sage: polytopes.dodecahedron(base_ring=RDF).volume() 6.4520359589542045
On my computer it is.
comment:15 Changed 4 years ago by
patchbot petitbonum is seeing this as a random failure:
./sage t long warnlong 54.5 src/sage/geometry/polyhedron/library.py ... sage: ico.volume() ... File "/home/chapoton/sage/local/lib/python2.7/sitepackages/sage/geometry/triangulation/point_configuration.py", line 1994, in facets_of_simplex normals = span.inverse().columns() File "sage/matrix/matrix2.pyx", line 8854, in sage.matrix.matrix2.Matrix.inverse (build/cythonized/sage/matrix/matrix2.c:71887) return ~self File "sage/matrix/matrix_double_dense.pyx", line 466, in sage.matrix.matrix_double_dense.Matrix_double_dense.__invert__ (build/cythonized/sage/matrix/matrix_double_dense.c:6026) raise ZeroDivisionError("input matrix must be nonsingular") ZeroDivisionError: input matrix must be nonsingular
comment:16 in reply to: ↑ 14 Changed 4 years ago by
Replying to vdelecroix:
Replying to vbraun:
Is this still reproducable? I get
sage: polytopes.dodecahedron(base_ring=RDF).volume() 6.4520359589542045On my computer it is.
Also reproducible on my Google CE host, with 8 Xeon CPUs: $ uname a Linux linux 4.9.08amd64 #1 SMP Debian 4.9.1302 (20181027) x86_64 GNU/Linux
comment:17 Changed 4 years ago by
with random test order I get more errors like this:
... File "src/sage/geometry/polyhedron/library.py", line 1158, in sage.geometry.polyhedron.library.Polytopes.truncated_dodecahedron Failed example: td = polytopes.truncated_dodecahedron(exact=False) Expected: doctest:warning ... UserWarning: This polyhedron data is numerically complicated; cdd could not convert between the inexact V and H representation without loss of data. The resulting object might show inconsistencies. Got: <BLANKLINE> ... 2 items had failures: 1 of 9 in sage.geometry.polyhedron.library.Polytopes.truncated_dodecahedron 1 of 7 in sage.geometry.polyhedron.library.Polytopes.truncated_icosidodecahedron [196 tests, 2 failures, 9.83 s]  sage t src/sage/geometry/polyhedron/library.py # 2 doctests failed  Total time for all tests: 10.0 seconds cpu time: 7.9 seconds cumulative wall time: 9.8 seconds dimpase@linux:~/sage$ ./sage tp randorder 127 src/sage/geometry/polyhedron/library.py
comment:18 Changed 4 years ago by
Degenerate polyhedra over floatingpoint numbers aren't really supported; Usually you are lucky and numerical errors triangulate your faces. But if you are unlucky then numerical fuzz leads to inconsistent incidence relations where a point is on both (or neither) side of a plane. Just adding fuzzy zero is afaik not enough.
comment:19 Changed 4 years ago by
This seems to be state of the art: https://dl.acm.org/citation.cfm?id=3194656
Surely, naive triangulation approach is doomed to fail... Should we just mark the corresponding tests are "known bug" and move on?
comment:20 Changed 4 years ago by
And here is the code: https://github.com/GeomScale/volume_approximation (it's C++).
comment:21 Changed 4 years ago by
 Branch changed from u/chapoton/18214 to u/dimpase/GQ
 Commit changed from e042c426aa810d3d92a03b8ea6b0f87ff36cc04a to b6758cd0a4535855e38e0a765d11a2db7405d3bb
 Status changed from needs_work to needs_review
comment:22 Changed 4 years ago by
 Reviewers changed from Matthias Koeppe to Matthias Koeppe,Frédéric Chapoton
 Status changed from needs_review to positive_review
ok
comment:23 Changed 4 years ago by
 Milestone changed from sage8.2 to sage8.7
comment:24 Changed 4 years ago by
 Branch changed from u/dimpase/GQ to b6758cd0a4535855e38e0a765d11a2db7405d3bb
 Resolution set to fixed
 Status changed from positive_review to closed
Here is a proposal for a solution. In case of inexact base ring, I introduce a nonzero epsilon constant, to take care of approximate equality of points. Maybe this could become a parameter.
New commits:
trac 18214 triangulation over inexact base rings