Opened 8 years ago

Closed 8 years ago

# Poset / LatticePoset: [meet|join]matrix algorithm

Reported by: Owned by: Jori Mäntysalo major sage-6.4 combinatorics Nathann Cohen Jori Mäntysalo Nathann Cohen, Travis Scrimshaw N/A 391c03b 391c03bcc290824c78f165d1623baaf1d921734d

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.

### comment:1 Changed 8 years ago by Jori Mäntysalo

Branch: → u/jmantysalo/poset___latticeposet___meet_join_matrix_algorithm

### comment:2 Changed 8 years ago by Jori Mäntysalo

Authors: → Jori Mäntysalo Nathann Cohen added → 8b2ab93a44970afc31a12dc0df57883f4b27eda6

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.

### comment:3 Changed 8 years ago by git

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

 ​aa6db23 Slight simplifying to _join.

### comment:4 Changed 8 years ago by 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

### comment:5 Changed 8 years ago by Jori Mäntysalo

Description: modified (diff) sage-wishlist → sage-6.4 new → needs_review

### comment:6 Changed 8 years ago by Nathann Cohen

Status: needs_review → needs_work

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

### comment:7 Changed 8 years ago by git

Commit: a7d2dd08623026a269f5fd7700b9e659985e7579 → a649be931b249028ff1e5961fc948c2daf50c695

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

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

### comment:8 follow-up:  9 Changed 8 years ago by Jori Mäntysalo

Reviewers: → Nathann Cohen needs_work → needs_review

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?)

### comment:9 in reply to:  8 Changed 8 years ago by Nathann Cohen

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

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

Nathann

### comment:10 Changed 8 years ago by Nathann Cohen

Status: needs_review → positive_review

### comment:11 follow-up:  14 Changed 8 years ago by Travis Scrimshaw

Status: positive_review → needs_info

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.

### comment:12 follow-up:  15 Changed 8 years ago by Travis Scrimshaw

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

### comment:13 follow-up:  16 Changed 8 years ago by Jori Mäntysalo

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?

### comment:14 in reply to:  11 ; follow-up:  18 Changed 8 years ago by Nathann Cohen

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.

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

### comment:15 in reply to:  12 Changed 8 years ago by Nathann Cohen

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

Last edited 8 years ago by Nathann Cohen (previous) (diff)

### comment:16 in reply to:  13 Changed 8 years ago by Nathann Cohen

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

### comment:17 Changed 8 years ago by Travis Scrimshaw

Status: needs_info → needs_work

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

### comment:18 in reply to:  14 ; follow-up:  19 Changed 8 years ago by Jori Mäntysalo

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.

### comment:19 in reply to:  18 Changed 8 years ago by Travis Scrimshaw

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

### comment:20 Changed 8 years ago by git

Commit: a649be931b249028ff1e5961fc948c2daf50c695 → 391c03bcc290824c78f165d1623baaf1d921734d

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

 ​391c03b Rollback: is_lattice() to categories.

### comment:21 follow-up:  22 Changed 8 years ago by Jori Mäntysalo

Status: needs_work → needs_review

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

### comment:22 in reply to:  21 Changed 8 years ago by Travis Scrimshaw

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.

### comment:23 Changed 8 years ago by Travis Scrimshaw

Reviewers: Nathann Cohen → Nathann Cohen, Travis Scrimshaw needs_review → positive_review

### comment:24 Changed 8 years ago by Volker Braun

Branch: u/jmantysalo/poset___latticeposet___meet_join_matrix_algorithm → 391c03bcc290824c78f165d1623baaf1d921734d → fixed positive_review → closed
Note: See TracTickets for help on using tickets.