Poset / LatticePoset: [meet|join]matrix algorithm

[jm58660]

Because join() and meet() are defined on [meet|join]lattices, not on posets, it is logical to also move join_matrix() and meet_matrix() there.

On hasse_diagram.py there is for example

le = copy(self.lequal_matrix())
for i in range(n): le[i,i] = 1

This is unneeded, because lequal_matrix() already contains ones at diagonal. We can use _leq_matrix directly. There are also few other places to small optimization.

At the same time I suggesg moving is_lattice() to posets.py from category code, because is_[meet|join]_semilattice() already is there.

CC: @nathanncohen

Component: combinatorics

Author: Jori Mäntysalo

Branch/Commit: 391c03b

Reviewer: Nathann Cohen, Travis Scrimshaw

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

[jm58660]

Branch: u/jmantysalo/poset___latticeposet___meet_join_matrix_algorithm

[jm58660]

Author: Jori Mäntysalo

[jm58660]

Commit: 8b2ab93

[jm58660]

comment:2

A slightly better(?) version for _meet() is done. Somebody could check if I did something stupid.

It seems to already have a complexity on O(n^2.5). I'm not sure if it would be much faster to just check if a poset is meet-semilattice. Probably no.

---

New commits:

8b2ab93

Slight simplification for meet-matrix.

[sagetrac-git]

Changed commit from 8b2ab93 to aa6db23

[sagetrac-git]

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

aa6db23

Slight simplifying to _join.

[sagetrac-git]

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

a7d2dd0

Moved [meet|join]_matrix from posets to lattices and is_lattice from

[sagetrac-git]

Changed commit from aa6db23 to a7d2dd0

[nathanncohen]

comment:6

Hello !

Thanks you for this branch, it is nice code.

A couple of comments and it can go:

1. The tests do not pass in the combinat/poset/ folder.

2. The code of _join would be simpled if you called "min(T)" instead of relabelling all points as n-1-y.

Nathann

[sagetrac-git]

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

a649be9

Let empty poset has [meet|join]matrix with 0 rows and columns.

[sagetrac-git]

Changed commit from a7d2dd0 to a649be9

[jm58660]

Reviewer: Nathann Cohen

[jm58660]

comment:8

1. Should empty set be a lattice? Anyways, this is now corrected. Should have a test suite containing tests for empty semilattices too. Actually a test suite should test all properties for 0- and 1-element posets. (How about is_chain(), for example?)

2. Hmm... I think I'll think about this on next round iterating throught the code.

[nathanncohen]

comment:9

Yo !

1. Should empty set be a lattice? Anyways, this is now corrected. Should have a test suite containing tests for empty semilattices too. Actually a test suite should test all properties for 0- and 1-element posets. (How about is_chain(), for example?)

Well. I just asked a friend, and as usual it depends on the definition that you prefer. He told me that a lattice should have a maximum and minimum element. The definition I prefer is that "any two guys have both a meet and a join", which hold for an empty set. I do not mind much to be honest, I always suspect other to use different conventions than I, so I usually do not trust softwares for that :-P

2. Hmm... I think I'll think about this on next round iterating throught the code.

Oh, I had not seen that the code was already like that before you modified it. Well, looks good to go !

Nathann

[tscrim]

comment:11

Has anyone checked that we do get speedups in meet/join matrix?

For the definition of a lattice, I've also been told you want a unique meet and join. Otherwise just the existence is something like regular poset, sorry I forget the exact term right now.

Also could you make the very minor change:

-        return matrix(ZZ, [[n-1-join[n-1-x][n-1-y] for y in range(n)] for
-                           x in range(n)])
+        return matrix(ZZ, [[n-1-join[n-1-x][n-1-y] for y in range(n)]
+                           for x in range(n)])

IMO it makes the code easier to read, but feel free to disregard.

[tscrim]

comment:12

Actually, you can't remove that function from the category without deprecating it.

[jm58660]

comment:13

About speedup: For example after P7=Posets(7).list() it took 630 ms to run sum([P.is_lattice() for P in P7]), after this patch 280 ms. Same can be seen in several test runs.

Suggestion of code formatting is good.

When is is_lattice() on category tried to run? I don't quite understand --- what happens if both finite_posets.py on categories and posets.py on combinats define same function?

[nathanncohen]

comment:14

Has anyone checked that we do get speedups in meet/join matrix?

Look at the code, and you will see that the algorithm never changed. It is only code simplification. For instance a call to 'max' instead of computing the max by hand, for instance list-comprehension instead of successive calls to 'append'. And a copy of a matrix is avoided too.

For the definition of a lattice, I've also been told you want a unique meet and join. Otherwise just the existence is something like regular poset, sorry I forget the exact term right now.

Travis, please read the code for your question is answered there.

Also could you make the very minor change:

Please don't change the status of a ticket that has been reviewed unless you see something which is actually wrong. Something more important than moving a 'for' around.

Nathann

[nathanncohen]

comment:15

Actually, you can't remove that function from the category without deprecating it.

If such an object exists somewhere in Sage then we should not move the function from the category file to the lattice file, for that would be a regression.

If such an object does not exist there is no reason to add a deprecation.

Bear in mind that an object that currently belongs to the category of Lattices and is not a FiniteLattice must implement its own is_meet_semilattice and is_join_semilattice.

Nathann

[nathanncohen]

comment:16

When is is_lattice() on category tried to run? I don't quite understand --- what happens if both finite_posets.py on categories and posets.py on combinats define same function?

Here is the thing: some guys in Sage rewrote method inheritance and call that "categories". A Lattice belongs to several "categories" by default:

sage: LatticePoset(Poset()).category()
Join of Category of finite lattice posets and Category of finite enumerated sets and Category of facade sets

Now, you can create any class and make it belong to the category of Lattices. It will consequently inherit from the methods defined in the "lattices" category file. This being said, is_lattice called is_join_semilattice and is_meet_semilattice which are defined in the usual poset/lattices.py file.

Which means that if you want the is_lattice method to work on an object which is not an instance of FiniteLattice, then it must implement its own is_join_semilattice and is_meet_semilattice.

And chances are that nobody ever did that, for removing that function from the category while re-implementing it in the poset files did not break any doctest.

Nathann

[tscrim]

comment:17

First off, I changed the status because there was no evidence that people had run any timings. This is why I changed it to needs_info. I never trust code that should be faster to really be faster; overhead and idiosyncrasies of python can make things slower, even if asymptotically it is a better algorithm (my go-to example is sorting, for (very) small lists, we just use bubble sort because of overhead). Also the algorithm to check that the finite poset is a lattice has changed (using has_top and has_bottom instead of the matrix).

Categories also can carry mathematical information as well, in particular for morphisms. The issue I'm raising about why the method needs to be deprecated is this. Suppose I have some personal code for a finite poset that does not inherit from FinitePoset, but is a parent belonging to the category of FinitePosets. Thus I have is_lattice from the category. However, with this patch, all of a sudden my code is (horribly) broken because I no longer have the is_lattice method.

There is likely some duplication from things in FinitePoset that should be up in the category coming from the initial implementation of the class and when we transitioned to using categories. So what should happen is you should delete the method in the FinitePoset class (which doesn't need a deprecation because you get it from the category).

[jm58660]

comment:18

Replying to @nathanncohen:

Please don't change the status of a ticket that has been reviewed unless you see something which is actually wrong. Something more important than moving a 'for' around.

But Travis had also other points. It does not bother me, because this is an enhancement, not a bug (and nothing like changing O(2^n) to O(n^2) or similar).

I don't quite get this category thing. For example there is no category for semilattices, but there is for lattices if I remember correctly. But anyways, I'll put a deprecation to categories code.

[tscrim]

comment:19

Replying to @jm58660:

I don't quite get this category thing. For example there is no category for semilattices, but there is for lattices if I remember correctly.

Well, no one currently has a need for those categories, or at least could put any generic code in them.

But anyways, I'll put a deprecation to categories code.

I think you're better off removing the one in FinitePoset and reinstating the category one; no deprecation needed. (It's like moving the method up in the class hierarchy.)

[sagetrac-git]

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

391c03b

Rollback: is_lattice() to categories.

[sagetrac-git]

Changed commit from a649be9 to 391c03b

[jm58660]

comment:21

Rollback done, for moved to other line.

Is it so that function on "real" class overrides function with same name in category? If so, then in principle there could be meet_matrix() defined on category --- it would loop over elements and construct a matrix. Basic implementation of lattice would only have meet(), but better on could have it's own and better meet_matrix()(?) This is basically what could be done in good old C++.

Anyways, this is now ready for review. Another thing is making documentation better. There is simply no point to make user to look different places for is_meet_semilattice() and is_lattice().

[tscrim]

comment:22

Replying to @jm58660:

Rollback done, for moved to other line.

Thanks.

Is it so that function on "real" class overrides function with same name in category? If so, then in principle there could be meet_matrix() defined on category --- it would loop over elements and construct a matrix. Basic implementation of lattice would only have meet(), but better on could have it's own and better meet_matrix()(?) This is basically what could be done in good old C++.

Yes, that's correct. Such a method would be a good benefit, although it might be good for it to also be an enumerated set. However a lattice morphism is stronger than a poset morphism, in that we must also have f(a ^ b) = f(a) ^ f(b) and similarly for joins. See http://en.wikipedia.org/wiki/Lattice_(order). So for two lattices L,P, we have Hom(L, P) <= Hom(L, P, category=Posets()) (the first one is the category of Lattices).

Anyways, this is now ready for review. Another thing is making documentation better. There is simply no point to make user to look different places for is_meet_semilattice() and is_lattice().

How most (from my experience) people get documentation is interactively (i.e. P.is_lattice?), so it doesn't make a difference where the method is located.

[tscrim]

Changed reviewer from Nathann Cohen to Nathann Cohen, Travis Scrimshaw

[vbraun]

Changed branch from u/jmantysalo/poset___latticeposet___meet_join_matrix_algorithm to 391c03b