Faster transitive_reduction (=> faster Poset creation)

[nathanncohen]

As reported on #17361, the call to transitive_reduction represents a non-negligible part of Poset creation.

This branch re-implements it for acyclic graphs.

sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure(); g = g.cartesian_product(g)
sage: %timeit g.transitive_reduction()
1 loops, best of 3: 1.02 s per loop
sage: %timeit g.transitive_reduction(acyclic=True)
10 loops, best of 3: 28.9 ms per loop

Now the critical part in the creation of a Poset is triggered by UniqueRepresentation. As soon as you create a Poset it is being compared with those that already exists... That is actually pre-computing the equality relationships between all existing posets even if you never asked for it, and I personally see it as wasted time (especially since I cannot disable it).

Nathann

CC: @fchapoton @jm58660

Component: graph theory

Keywords: poset

Author: Nathann Cohen

Branch/Commit: ade98aa

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/17408

[nathanncohen]

Branch: u/ncohen/17408

[sagetrac-git]

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

ce577a9

trac #17408: Faster transitive_reduction (=> faster Poset creation)

[sagetrac-git]

Commit: ce577a9

[fchapoton]

Changed keywords from none to poset

[jm58660]

comment:6

"That is actually pre-computing the equality relationships between all existing posets even if you never asked for it, and I personally see it as wasted time (especially since I cannot disable it)."

What happens with key= -parameter? If you put a different one in every poset, I think it should not try to compare to posets with different key.

[nathanncohen]

comment:7

Indeed, but then the poset equality is broken. And I have no control the posets built by subfunctions like the poset constructors, the products, etc ...

[jm58660]

comment:8

Replying to @nathanncohen:

Indeed, but then the poset equality is broken. And I have no control the posets built by subfunctions like the poset constructors, the products, etc ...

True. Should there be a global setting for it? Or an option in every poset function for this?

[nathanncohen]

comment:9

True. Should there be a global setting for it? Or an option in every poset function for this?

Truth is that I do not know. This feature is a class inheritance from UniqueRepresentation, so you cannot really "flag" that.

Yep. Complicated. Don't know how to make both work easily -_-

Nathann

[nbruin]

comment:10

Objects produced in an inner loop should not be UniqueRepresentation. Parent are designed to be heavy objects. You should be creating them at least one or two orders less frequently than your most frequently created objects (unless your computations aren't bound by creation of objects). If you're finding that you're creating posets frequently, then you should make a "lightweight" version of poset that's not carrying around all the parent baggage.

If you're finding that those "lightweight" posets need to be turned into full-fledged parents every now and again, then consider making it possible to create a full-scale poset from a lightweight one.

See [#14356 comment:6]

[jm58660]

comment:11

Replying to @nbruin:

If you're finding that you're creating posets frequently, then you should make a "lightweight" version of poset that's not carrying around all the parent baggage.

Maybe we already have this: it is called Hasse diagram?

I mean, can we have a code generating only hasse diagrams and using functions from hasse_diagram.py? I have been computing quite many calculations of format "Generate posets of size n. Remove those that have property p. For remaining compute f(P) and then find smallest/biggest value among results."

[nathanncohen]

comment:12

If you're finding that you're creating posets frequently, then you should make a "lightweight" version of poset that's not carrying around all the parent baggage.

Well, Jori wants to implement a way to enumerate all posets of a given size, so in this case we will have to pay a high tribute to parents. But how do you think that it should be implemented ? Jori is right that Hasse Diagrams have a lot of features already, but that is only... Well, a Hasse Diagram. No comparisons of elements, none of the products defined in the posets directly, well.

What we would need as you say is a class exactly like Poset without the parent infrastructure, but how could we implement that with the smallest amount of copy/paste ?

Nathann

[nathanncohen]

comment:13

sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure(); g = g.cartesian_product(g)
sage: %time Poset(g)
CPU times: user 284 ms, sys: 32 ms, total: 316 ms
Wall time: 278 ms
Finite poset containing 1024 elements
sage: %time Poset(g)
CPU times: user 1.63 s, sys: 44 ms, total: 1.68 s
Wall time: 1.61 s
Finite poset containing 1024 elements

[nbruin]

comment:14

Replying to @nathanncohen:

What we would need as you say is a class exactly like Poset without the parent infrastructure, but how could we implement that with the smallest amount of copy/paste ?

It would require some thought and some major refactoring. The natural structure to me would seem to have a base class that does not inherit from UniqueRepresentation that implements all the basic stuff and then (hopefully) use multiple inheritance to equip this with the requisite parent stuff for the "full Parent POSet". If there are things that are incompatible between a usable "fast POSet" and a "full parent POSet" then the useful thing should probably inherit separately from the common base class.

The "full parent poset" __init__ would probably require some trickery to allow instantiation of a full parent from a fast poset (if that's required). Quite possibly, you'd be better off with a UniqueFactory there, so that you have better control over what the construction is keyed under.

[jm58660]

comment:15

What is the rationale behind current implementation? I mean, there must be some example where UniqueRepresentation makes things faster.

I understand the logic for, say, finite ring, but not for posets.

[nbruin]

comment:16

Replying to @jm58660:

What is the rationale behind current implementation? I mean, there must be some example where UniqueRepresentation makes things faster.

I suspect it was done out of dogma: "Parents are supposed to be unique" in sage. That statement by itself is not correct: not all parents need to be unique. However, equal-but-non-identical parents can cause some minor problems in the coercion framework.

The real catch is if you're building a parent that can serve as base for other parents that ARE unique representation. Because cache keys there are looked up by equality and not identity, you can really confuse the coercion framework to the point of getting buggy behaviour. See [#15248 comment:2] for an explanation of a classic example.

There is always a solution to this: do not inherit from UniqueRepresentation or UniqueFactory but do inherit from WithEqualityById (or implement that by yourself). It gives you a very cheap but mathematically not terribly useful equality test. However, there's something to say for it: The two posets A={1,2,3} and B={1,2,3} with trivial relation (ie. x<=y iff x==y) are isomorphic, but not uniquely so. So unless we're explicitly saying by what isomorphism A,B are to be identified, perhaps we should treat them as not equal. After all, C={a,b,c} (with empty relation) is also isomorphic to A and B and there no-one would be tempted to say C is equal to A and B.

However, such strict equality might be too hard to swallow for people who want their computer algebra system to cater a little more to intuitive, human reasoning. In that case you can just make your parent non-unique, but still define equality to be by some looser equivalence relation. You should just document that your class is not appropriate for use as a base for another UniqueRepesentation parent.

[nathanncohen]

comment:17

Yooooo !

I suspect it was done out of dogma: "Parents are supposed to be unique" in sage.

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.

We just can't give up enumerating posets up to isomorphism because of this cached equality test. And lose seconds like in the ticket's description.

Nathann

P.S. : What this ticket does is totally orthogonal to that, though, and still in needs_review :-P

[nathanncohen]

comment:18

By the way I wonder if I should add a "if self.is_directed_acyclic()" in th function. I am not sure that those who use this transitive_reduction thing will think of looking at the doc, and is_directed_acyclic is rather cheap. What would you think of running it when acyclic=False, just in case ?

Nathann

[nbruin]

comment:19

Replying to @nathanncohen:

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.

[nathanncohen]

comment:20

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.

Well, perhaps we could return "Poset-as-parents" when the user asks for a non-facade poset, and non-parent posets otherwise.

Sigh. I'll write to the sage-devel and the combinat guys...

Nathann

[jm58660]

comment:21

Replying to @nbruin:

What is the rationale behind current implementation? I mean, there must be some example where UniqueRepresentation makes things faster.

However, there's something to say for it: The two posets A={1,2,3} and B={1,2,3} with trivial relation (ie. x<=y iff x==y) are isomorphic, but not uniquely so. So unless we're explicitly saying by what isomorphism A,B are to be identified, perhaps we should treat them as not equal. After all, C={a,b,c} (with empty relation) is also isomorphic to A and B and there no-one would be tempted to say C is equal to A and B.

Thank you for very good explanation!

Generating all posets of size 7 up to isomorphism takes 18,5 second --- this is not a bottle neck then. But with #14110 the time drops to 2,5 seconds. And when generating just Hasse diagrams instead of posets it took 0,3 second. In the code I was asked to write this is the turning point: now slowest part is doing something with posets, not generating them.

Maybe this is so specialized case that we should let posets to be like they are now. A user might then optimize by directly playing with Hasse diagrams.

This optimization does not mean that you can do things with posets of size 2n --- it means that that you can use posets of size n+2.

[nathanncohen]

comment:22

(beyond the poset discussion, this ticket is still needing a review) :-P

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

253fc21

trac #17408: Faster transitive_reduction (=> faster Poset creation)

[sagetrac-git]

Changed commit from ce577a9 to 253fc21

[nathanncohen]

comment:24

I removed the "acyclic" flag that nobody would have seen and added an automatic detection of acyclic graphs. This has a small cost, but as I believe that nobody ever calls this function except on acyclic graphs I would say that it is a win (really, nobody would have seen the optional flag).

Nathann

[fchapoton]

Changed branch from u/ncohen/17408 to public/ticket/17408

[fchapoton]

Changed commit from 253fc21 to 858d7a9

[fchapoton]

comment:25

There was a failing doctest, because undirected graphs do not have a is_directed_acyclic method.

I have also made a few pep8 changes.

Looks good to me. You can set a positive review if you agree with my changes.

---

New commits:

858d7a9

trac #17408 reviewer commit, pep8 and other details

[nathanncohen]

Reviewer: Frédéric Chapoton

[nathanncohen]

comment:26

Helloooooo !

There was a failing doctest, because undirected graphs do not have a is_directed_acyclic method.

Oh, I see. Thanks ! ;-)

I have also made a few pep8 changes.

You should see a doctor about that :-P

Looks good to me. You can set a positive review if you agree with my changes.

Thanks again ! :-)

Nathann

[vbraun]

comment:27

doctests fail

[sagetrac-git]

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

ade98aa

trac #17408: Broken doctests

[sagetrac-git]

Changed commit from 858d7a9 to ade98aa

[vbraun]

Changed branch from public/ticket/17408 to ade98aa