Overriding checks to generate poset and lattice faster

[f29946bc-ee7b-48cd-9abc-3445948c551d]

This ticket was originally about overriding checks to make poset creation faster. But this is actually already available: instead of Poset(...) one can use FinitePoset(D, ..., category=FinitePosets, ...). For some lattices the time saving is huge, as there is no need to compute meet- or join-matrix; think about BooleanLattice used as an example of a poset, not as an example of lattice. (This could be documented somehow, "Advanced SageMath Hacking" or something like that.)

However, currently for example Posets.ChainPoset(500) may takes 10 seconds. That is so because the constructors for common posets and lattices do not use this faster construction. Hence the new aim of the ticket is to change thst.

CC: @tscrim

Component: combinatorics

Author: Jori Mäntysalo

Branch/Commit: b0e5686

Reviewer: Travis Scrimshaw

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

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:2

Travis, I guess we should close this one. But to be sure:

First, if I just say n = 500; L1 = LatticePoset((range(n), [[x,x+1] for x in range(n-1)])) it takes about two seconds. But if I say

n = 500
D = DiGraph([range(n), [[x,x+1] for x in range(n-1)]], format='vertices_and_edges')
from sage.combinat.posets.lattices import FiniteLatticePoset
L2 = FiniteLatticePoset(D, range(n), FiniteLatticePosets(), True)

it takes only 10 or 20 millisecods. Can you confirm that this works, and so there is a way to override check "is this poset really a poset (i.e. acyclic transitive reduction of graph)"?

Second, another possibility is that the code could directly compute le-matrix, Möbius function matrix etc, and those would be very easy for a chain, diamond and so one. But that is a place for another ticket.

Third, it is unnecessary to re-compute meet- or join-matrix. But that is a duplicate of #20434 or #18776.

[tscrim]

comment:3

I am opting for changing the relevant constructors to avoid the checks, which is a separate from #20434 and #18776.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:4

Replying to @tscrim:

I am opting for changing the relevant constructors to avoid the checks, which is a separate from #20434 and #18776.

Do you mean only mandatory checks, i.e. is_poset and having a join matrix and a bottom element (or meet matrix and top), or more precomputation?

[tscrim]

comment:5

I mean replace LatticePoset with FiniteLatticePoset as in comment:2 to avoid the input validation checks

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:6

Replying to @tscrim:

I mean replace LatticePoset with FiniteLatticePoset as in comment:2 to avoid the input validation checks

In specific functions at lattice_examples.py that creates, say, DivisorLattice?

[tscrim]

comment:7

Yes, that's correct.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Branch: u/jmantysalo/overriding_checks_to_generate_poset_and_lattice_faster

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:9

Like this?

Does everything work? I.e. meets, joins, listing elements, linear extension is OK and so on? How about unique representation?

---

New commits:

1cb4103

An example implementation.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Commit: 1cb4103

[tscrim]

comment:10

Replying to @jm58660:

Like this?

Yes.

Does everything work? I.e. meets, joins, listing elements, linear extension is OK and so on? How about unique representation?

AFAIK, yes, but I don't have time immediately to test it. Unique representation is handled by the FinitePoset class and our input is basically the result from going through Poset. IIRC, the default for fixed linear extensions is to not have one. The others look like they are naturally the same from going through Poset as well.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:11

OK. Then how to create DivisorLattice or whatever poset whose elements are not integers 0..n-1?

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:12

Ah, the "hasse diagram" -parameter is not Hasse diagram in a sense that hasse_diagram.py defines... I.e. it is just a DiGraph with some properties as an unlabeled graph. So something like this could work:

from sage.combinat.posets.lattices import FiniteLatticePoset
from sage.categories.finite_lattice_posets import FiniteLatticePosets
n = 10^12
Div_n = divisors(n)
D = DiGraph([Div_n, lambda a, b: b%a==0 and is_prime(b//a)])
L = FiniteLatticePoset(D, elements=Div_n, category=FiniteLatticePosets())

This is faster than current implementation, but could be made even faster with some thinking. Having a natural linear extension would even make some small examples better; currently Posets.DivisorLattice(12).join_irreducibles() will give [2, 4, 3].

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:13

Is there something against using distinguished linear extension in general? Slower, eats more memory, something?

I think that DivisorLattice() is a good example for some functions like join_irreducibles(). But it is more natural if linear extension is ascending. That is, Posets.DivisorLattice(12).join_irreducibles() could return [2, 3, 4] and not [2, 4, 3] like it now does.

[tscrim]

comment:14

Replying to @jm58660:

Is there something against using distinguished linear extension in general? Slower, eats more memory, something?

Not that I am aware.

I think that DivisorLattice() is a good example for some functions like join_irreducibles(). But it is more natural if linear extension is ascending. That is, Posets.DivisorLattice(12).join_irreducibles() could return [2, 3, 4] and not [2, 4, 3] like it now does.

It is natural in a way, but I don't have any opinion on this.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:15

I did #21666 as a first part for this.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-Now for example `Posets.ChainPoset(500)` takes about 10 second. It does something like 1) make a list, 2) make a poset from list, checking that list really is acyclic as when read as digraph edges and 3) make a lattice from poset, checking that poset really is lattice. Phase 3 is done by really generating meet- and join-matrix.
+This ticket was originally about overriding checks to make poset creation faster. But this is actually already available: instead of `Poset(...)` one can use `FinitePoset(D, ..., category=FinitePosets, ...)`. For some lattices the time saving is huge, as there is no need to compute meet- or join-matrix; think about `BooleanLattice` used as an example of a poset, not as an example of lattice. (This could be documented somehow, "Advanced [SageMath](../wiki/SageMath) Hacking" or something like that.)

-Poset and lattice creating functions need an option that says "do not check, trust blindly".
+However, currently for example `Posets.ChainPoset(500)` may takes 10 seconds. That is so because the constructors for common posets and lattices do not use this faster construction. Hence the new aim of the ticket is to change thst.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b0e5686

Faster basic poset structures.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1cb4103 to b0e5686

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:18

Done for most basic structures. I guess this one can be closed; more complicated structures take more time to create as a digraph, so proportional time change is not that much.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Author: Jori Mäntysalo

[tscrim]

comment:19

I agree that we can do things incrementally as there is a need. However, I don't agree with this change:

-        p.hasse_diagram()._pos = {0:[2,0],1:[0,2],2:[3,1],3:[3,3],4:[2,4]}
-        return p

as this is used to make the printing of the poset is "nice".

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:20

Replying to @tscrim:

I don't agree with this change:

-        p.hasse_diagram()._pos = {0:[2,0],1:[0,2],2:[3,1],3:[3,3],4:[2,4]}
-        return p

as this is used to make the printing of the poset is "nice".

Posets are plotted wih layout='acyclic', so that will be overrided in any case.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:21

Just pinging. As you can see from

g = DiGraph({0: [1]})
g._pos={0: [0,0], 1: [1,1]}
g.show(layout='acyclic')

the ...pos=... line does nothing.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:22

Looking at the code more, the original didn't actually set the _pos because it was doing it to a copy of the Hasse diagram. So it is okay I guess...it does have some effect on the HasseDiagram when done correctly, but like I said, it wasn't actually doing it correctly anyways.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:23

OK, thanks. I'll continue on sage-devel about _pos.

[vbraun]

Changed branch from u/jmantysalo/overriding_checks_to_generate_poset_and_lattice_faster to b0e5686