#17408: Faster transitive_reduction (=> faster Poset creation)
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: poset | Commit:
Authors: | ce577a909e3ac2835f975cc9515b54459174e8ca
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/17408 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by nbruin):
Replying to [comment:17 ncohen]:
> HMmmm... I am afraid that if I follow the mains lines of what you say, I
have no clue how it is to be implemented in practice. I believe that the
combinat guys use posets as exponents of polynomials, and that this is why
they need a fast equality test. It would be cool if we could remove this
`UniqueRepresentation` dependency from Posets, while letting them have a
way to add it afterwards if they need it in their computations.
For one thing, that use wouldn't require posets to be *parents* then.
[possibly off-topic example]
This happens in number theory too: fractional ideals are Z-submodules of a
number field, so they have elements. That would qualify them to be
"parents", but nobody in their right mind would implement them like that
if you're going to do ideal arithmetic: then they're just represented as
matrices or tuples of generating elements. Equality is taken care of by
putting generators in normal form, which can be fairly expensive the first
time around, but equality testing afterwards is pretty quick.
If you want to make POsets faster you should seriously consider splitting
POsets-as-parents and POsets-as-objects. Both usage scenarios you describe
seem to fall in the latter scenario, by the way, so perhaps POsets-as-
parents aren't really needed beyond checking a box for which parents are
available in sage.
--
Ticket URL: <http://trac.sagemath.org/ticket/17408#comment:19>
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.
