Opened 8 years ago
Closed 5 years ago
#17147 closed enhancement (fixed)
Overriding checks to generate poset and lattice faster
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  combinatorics  Keywords:  
Cc:  tscrim  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  b0e5686 (Commits, GitHub, GitLab)  Commit:  b0e568636be5546969483c0a3eb6a6b81a9a3dae 
Dependencies:  Stopgaps: 
Description (last modified by )
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 joinmatrix; 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.
Change History (24)
comment:1 Changed 8 years ago by
 Cc ncohen added
comment:2 Changed 6 years ago by
 Cc tscrim added; ncohen removed
 Milestone changed from sagewishlist to sageduplicate/invalid/wontfix
 Status changed from new to needs_review
comment:3 followup: ↓ 4 Changed 6 years ago by
 Milestone changed from sageduplicate/invalid/wontfix to sage7.4
 Status changed from needs_review to needs_work
comment:4 in reply to: ↑ 3 Changed 6 years ago by
 Status changed from needs_work to needs_info
comment:5 followup: ↓ 6 Changed 6 years ago by
I mean replace LatticePoset
with FiniteLatticePoset
as in comment:2 to avoid the input validation checks
comment:6 in reply to: ↑ 5 Changed 6 years ago by
comment:7 Changed 6 years ago by
Yes, that's correct.
comment:8 Changed 6 years ago by
 Branch set to u/jmantysalo/overriding_checks_to_generate_poset_and_lattice_faster
comment:9 followup: ↓ 10 Changed 6 years ago by
 Commit set to 1cb4103fa4c56ca1907f2a50ebe7562eaea6cbc9
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.

comment:10 in reply to: ↑ 9 Changed 6 years ago by
Replying to jmantysalo:
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.
comment:11 Changed 6 years ago by
OK. Then how to create DivisorLattice
or whatever poset whose elements are not integers 0..n1
?
comment:12 Changed 6 years ago by
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]
.
comment:13 followup: ↓ 14 Changed 6 years ago by
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.
comment:14 in reply to: ↑ 13 Changed 6 years ago by
Replying to jmantysalo:
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 likejoin_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.
comment:15 Changed 6 years ago by
I did #21666 as a first part for this.
comment:16 Changed 6 years ago by
 Description modified (diff)
 Milestone changed from sage7.4 to sage7.5
 Status changed from needs_info to needs_work
comment:17 Changed 6 years ago by
 Commit changed from 1cb4103fa4c56ca1907f2a50ebe7562eaea6cbc9 to b0e568636be5546969483c0a3eb6a6b81a9a3dae
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
b0e5686  Faster basic poset structures.

comment:18 Changed 6 years ago by
 Status changed from needs_work to needs_review
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.
comment:19 followup: ↓ 20 Changed 6 years ago by
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".
comment:20 in reply to: ↑ 19 Changed 6 years ago by
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.
comment:21 Changed 5 years ago by
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.
comment:22 Changed 5 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
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.
comment:23 Changed 5 years ago by
OK, thanks. I'll continue on sagedevel about _pos
.
comment:24 Changed 5 years ago by
 Branch changed from u/jmantysalo/overriding_checks_to_generate_poset_and_lattice_faster to b0e568636be5546969483c0a3eb6a6b81a9a3dae
 Resolution set to fixed
 Status changed from positive_review to closed
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(n1)]))
it takes about two seconds. But if I sayit 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 lematrix, 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 recompute meet or joinmatrix. But that is a duplicate of #20434 or #18776.