#7109: [with patch, needs review] polyhedra bugs with linearities, rewrite
proposal
---------------------------+------------------------------------------------
Reporter: vbraun | Owner: mhampton
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-feature
Component: geometry | Keywords: polyhedra
Work_issues: | Author:
Reviewer: | Merged:
---------------------------+------------------------------------------------
Comment(by vbraun):
Previously we only eliminated redundant vertices, now we also eliminate
redundant (in)equalities. I added some timing to the output:
{{{
sage: time p = Polyhedron(vertices = [[i,i^2,i^3,i^4,i^5] for i in
range(14)], verbose=true)
V-representation
begin
14 6 rational
1 0 0 0 0 0
1 1 1 1 1 1
1 2 4 8 16 32
[...]
1 13 169 2197 28561 371293
end
# walltime used for complementary representation: 0s
# walltime used for canonical H-representation: 6s
# walltime used for canonical V-representation: 0s
V-representation
begin
14 6 rational
1 0 0 0 0 0
1 1 1 1 1 1
[...]
1 13 169 2197 28561 371293
end
H-representation
begin
110 6 rational
0 11880 -4578 659 -42 1
[...]
0 17160 -6026 791 -46 1
end
Vertex graph
begin
14 14
1 13 : 2 3 4 5 6 7 8 9 10 11 12 13 14
[...]
14 13 : 1 2 3 4 5 6 7 8 9 10 11 12 13
end
# walltime used for vertex adjacencies: 0s
Facet graph
begin
110 110
1 5 : 9 45 91 105 110
2 5 : 8 9 38 92 103
[...]
110 5 : 1 46 91 105 109
end
# walltime used for facet adjacencies: 10s
CPU times: user 0.01 s, sys: 0.01 s, total: 0.02 s
Wall time: 16.37 s
}}}
The polyhedral input is one with relatively few vertices (and without any
redundancies), but lots of inequalities. This is why reducing the
inequalities to a minimal set takes relatively long.
About 2/3 of the total time is spent on computing facet adjacencies. This
part of the computation could be split off, but since it is less than one
order of magnitude it is probably not worth the added complexity.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7109#comment:14>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
