Opened 8 years ago

Closed 5 years ago

# Overriding checks to generate poset and lattice faster

Reported by: Owned by: jmantysalo major sage-7.5 combinatorics tscrim Jori Mäntysalo Travis Scrimshaw N/A b0e5686 b0e568636be5546969483c0a3eb6a6b81a9a3dae

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.

### 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: ↓ 4 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

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: ↓ 6 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

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: ↓ 10 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:

 ​1cb4103 `An example implementation.`

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

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: ↓ 14 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

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:

 ​b0e5686 `Faster 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: ↓ 20 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

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.