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: sage-7.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:

Status badges

Description (last modified by jmantysalo)

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.

Change History (24)

comment:1 Changed 8 years ago by ncohen

  • Cc ncohen added

comment:2 Changed 6 years ago by jmantysalo

  • Cc tscrim added; ncohen removed
  • Milestone changed from sage-wishlist to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

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.

comment:3 follow-up: Changed 6 years ago by tscrim

  • Milestone changed from sage-duplicate/invalid/wontfix to sage-7.4
  • Status changed from needs_review to needs_work

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

comment:4 in reply to: ↑ 3 Changed 6 years ago by jmantysalo

  • Status changed from needs_work to needs_info

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?

comment:5 follow-up: Changed 6 years ago by tscrim

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 jmantysalo

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?

comment:7 Changed 6 years ago by tscrim

Yes, that's correct.

comment:8 Changed 6 years ago by jmantysalo

  • Branch set to u/jmantysalo/overriding_checks_to_generate_poset_and_lattice_faster

comment:9 follow-up: Changed 6 years ago by jmantysalo

  • 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:

1cb4103An example implementation.

comment:10 in reply to: ↑ 9 Changed 6 years ago by tscrim

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 jmantysalo

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

comment:12 Changed 6 years ago by jmantysalo

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 follow-up: Changed 6 years ago by jmantysalo

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 tscrim

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 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.

comment:15 Changed 6 years ago by jmantysalo

I did #21666 as a first part for this.

comment:16 Changed 6 years ago by jmantysalo

  • Description modified (diff)
  • Milestone changed from sage-7.4 to sage-7.5
  • Status changed from needs_info to needs_work

comment:17 Changed 6 years ago by git

  • Commit changed from 1cb4103fa4c56ca1907f2a50ebe7562eaea6cbc9 to b0e568636be5546969483c0a3eb6a6b81a9a3dae

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

b0e5686Faster basic poset structures.

comment:18 Changed 6 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • 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 follow-up: Changed 6 years ago by tscrim

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 jmantysalo

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 jmantysalo

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 tscrim

  • 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 jmantysalo

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

comment:24 Changed 5 years ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.