#18860: Faster Poyhedron.graph()
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: new
Type: | Milestone: sage-6.8
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers:
geometry | Work issues:
Keywords: | Commit:
Authors: | 3b5eabb9735a867678c2c6a13dc7700c24d82732
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18860 |
Dependencies: |
#18779 |
-------------------------+-------------------------------------------------
Comment (by dimpase):
Replying to [comment:7 ncohen]:
> > My understanding is that hacking `hasse_diagram.py` to stop earlier is
what one actually needs to do.
>
> I do not know how to do that. If you know how to fix this
implementation, at least it will be done. Otherwise chances are that
nothing will happen
the whole Polyhedron code does a potentially very slow thing: enumerating
the inequalities at construction time, instead of doing it optionally
or/and lazily.
Indeed, e.g. the problem at hand, deciding if two vertices are adjacent,
does not need pre-computed inequalities. Namely, checking that v_1 and v_2
are adjacent can be done by solving the following LP:
{{{
variables: x_0..x_d,x_{d+1}
objective: max x_0
constraints:
-1 <= x_i <=1 for i in [1..d];
x_{d+1} >= 0;
sum_{j=1}^d v_{i,j}*x_j = x_{d+1}, for i=1,2;
sum_{j=1}^d v_{i,j}*x_j >= x_{d+1} + x_0, for i>2;
}}}
if the optimum exists and is strictly positive, they form an edge, and
otherwise they don't.
So we are trying to find an inequality that is valid for the convex hull
of v_k's and turns
into an equation on v_1 and v_2, but is a strict inequality on the rest of
v_k's.
(The LP above will not work if there are more v_j's on the line joining
v_1 and v_2 --- but this case can be taken care of trivially.)
--
Ticket URL: <http://trac.sagemath.org/ticket/18860#comment:8>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
