Opened 4 years ago

Closed 8 months ago

#18214 closed defect (fixed)

Bug in volume computation of polyhedron

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-8.7
Component: geometry Keywords: bug
Cc: jipilab, moritz, gh-tom111 Merged in:
Authors: Dima Pasechnik Reviewers: Matthias Koeppe,Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: b6758cd (Commits) Commit: b6758cd0a4535855e38e0a765d11a2db7405d3bb
Dependencies: Stopgaps:

Description (last modified by chapoton)

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 4 years ago by vdelecroix

  • Keywords bug added

comment:2 Changed 3 years ago by mkoeppe

  • Milestone changed from sage-6.7 to sage-7.3

comment:3 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:4 Changed 3 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to u/chapoton/18214
  • Commit set to d409a4cad8c4936dfe25e3cf0d5fa5fb59188e77
  • Status changed from new to needs_review

Here is a proposal for a solution. In case of inexact base ring, I introduce a non-zero epsilon constant, to take care of approximate equality of points. Maybe this could become a parameter.


New commits:

d409a4ctrac 18214 triangulation over inexact base rings

comment:5 Changed 3 years ago by mkoeppe

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.

Last edited 3 years ago by mkoeppe (previous) (diff)

comment:6 Changed 3 years ago by mkoeppe

  • Milestone changed from sage-7.3 to sage-7.4
  • Reviewers set to Matthias Koeppe
  • Status changed from needs_review to needs_work

comment:7 Changed 3 years ago by git

  • Commit changed from d409a4cad8c4936dfe25e3cf0d5fa5fb59188e77 to 11dc0330037d336f82ac55ad81b353b7670dd6ae

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

11dc033Merge branch 'u/chapoton/18214' in 7.5.b3

comment:8 Changed 19 months ago by git

  • Commit changed from 11dc0330037d336f82ac55ad81b353b7670dd6ae to e042c426aa810d3d92a03b8ea6b0f87ff36cc04a

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

f086a14Merge branch 'u/chapoton/18214' in 8.2.b6
e042c42trac 18214 adding abs tol to volume doctest

comment:9 Changed 19 months ago by chapoton

  • Cc jipilab added

New commits:

f086a14Merge branch 'u/chapoton/18214' in 8.2.b6
e042c42trac 18214 adding abs tol to volume doctest

comment:10 Changed 19 months ago by chapoton

  • Milestone changed from sage-7.4 to sage-8.2

comment:11 Changed 15 months ago by jipilab

  • Cc moritz added

comment:12 Changed 12 months ago by mkoeppe

  • Cc gh-tom111 added

comment:13 follow-up: Changed 11 months ago by vbraun

Is this still reproducable? I get

sage: polytopes.dodecahedron(base_ring=RDF).volume()
6.4520359589542045

comment:14 in reply to: ↑ 13 ; follow-up: Changed 11 months ago by vdelecroix

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 11 months ago by chapoton

patchbot petitbonum is seeing this as a random failure:

./sage -t --long --warn-long 54.5 src/sage/geometry/polyhedron/library.py
...
sage: ico.volume()
...
      File "/home/chapoton/sage/local/lib/python2.7/site-packages/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 8 months ago by dimpase

Replying to vdelecroix:

Replying to vbraun:

Is this still reproducable? I get

sage: polytopes.dodecahedron(base_ring=RDF).volume()
6.4520359589542045

On my computer it is.

Also reproducible on my Google CE host, with 8 Xeon CPUs: $ uname -a Linux linux 4.9.0-8-amd64 #1 SMP Debian 4.9.130-2 (2018-10-27) x86_64 GNU/Linux

comment:17 Changed 8 months ago by dimpase

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 8 months ago by vbraun

Degenerate polyhedra over floating-point 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 8 months ago by dimpase

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 8 months ago by dimpase

And here is the code: https://github.com/GeomScale/volume_approximation (it's C++).

comment:21 Changed 8 months ago by dimpase

  • Authors changed from Frédéric Chapoton to Frédéric Chapoton, Dima Pasechnik
  • Branch changed from u/chapoton/18214 to u/dimpase/GQ
  • Commit changed from e042c426aa810d3d92a03b8ea6b0f87ff36cc04a to b6758cd0a4535855e38e0a765d11a2db7405d3bb
  • Status changed from needs_work to needs_review

see #27056 for a follow-up


New commits:

b6758cdvolume computation of fuzzy RDF polytope might fail

comment:22 Changed 8 months ago by chapoton

  • Authors changed from Frédéric Chapoton, Dima Pasechnik to Dima Pasechnik
  • Reviewers changed from Matthias Koeppe to Matthias Koeppe,Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok

comment:23 Changed 8 months ago by chapoton

  • Milestone changed from sage-8.2 to sage-8.7

comment:24 Changed 8 months ago by vbraun

  • Branch changed from u/dimpase/GQ to b6758cd0a4535855e38e0a765d11a2db7405d3bb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.