Opened 7 years ago

Closed 7 years ago

#17216 closed enhancement (fixed)

Poset / LatticePoset: [meet|join]matrix algorithm

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-6.4
Component: combinatorics Keywords:
Cc: ncohen Merged in:
Authors: Jori Mäntysalo Reviewers: Nathann Cohen, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 391c03b (Commits, GitHub, GitLab) Commit: 391c03bcc290824c78f165d1623baaf1d921734d
Dependencies: Stopgaps:

Status badges

Description (last modified by jmantysalo)

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.

Change History (24)

comment:1 Changed 7 years ago by jmantysalo

  • Branch set to u/jmantysalo/poset___latticeposet___meet_join_matrix_algorithm

comment:2 Changed 7 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Cc ncohen added
  • Commit set to 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:

8b2ab93Slight simplification for meet-matrix.

comment:3 Changed 7 years ago by git

  • Commit changed from 8b2ab93a44970afc31a12dc0df57883f4b27eda6 to aa6db231af42197ba9a4daccf904c126dad87204

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

aa6db23Slight simplifying to _join.

comment:4 Changed 7 years ago by git

  • Commit changed from aa6db231af42197ba9a4daccf904c126dad87204 to a7d2dd08623026a269f5fd7700b9e659985e7579

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

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

comment:5 Changed 7 years ago by jmantysalo

  • Description modified (diff)
  • Milestone changed from sage-wishlist to sage-6.4
  • Status changed from new to needs_review

comment:6 Changed 7 years ago by ncohen

  • Status changed from needs_review to 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 7 years ago by git

  • Commit changed from a7d2dd08623026a269f5fd7700b9e659985e7579 to a649be931b249028ff1e5961fc948c2daf50c695

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

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

comment:8 follow-up: Changed 7 years ago by jmantysalo

  • Reviewers set to Nathann Cohen
  • Status changed from needs_work to 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?)

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

comment:9 in reply to: ↑ 8 Changed 7 years ago by ncohen

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

comment:10 Changed 7 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:11 follow-up: Changed 7 years ago by tscrim

  • Status changed from positive_review to 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: Changed 7 years ago by tscrim

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

comment:13 follow-up: Changed 7 years ago by jmantysalo

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: Changed 7 years ago by ncohen

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

comment:15 in reply to: ↑ 12 Changed 7 years ago by ncohen

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 7 years ago by ncohen (previous) (diff)

comment:16 in reply to: ↑ 13 Changed 7 years ago by ncohen

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 7 years ago by tscrim

  • Status changed from needs_info to 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: Changed 7 years ago by jmantysalo

Replying to ncohen:

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 7 years ago by tscrim

Replying to jmantysalo:

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 7 years ago by git

  • Commit changed from a649be931b249028ff1e5961fc948c2daf50c695 to 391c03bcc290824c78f165d1623baaf1d921734d

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

391c03bRollback: is_lattice() to categories.

comment:21 follow-up: Changed 7 years ago by jmantysalo

  • Status changed from needs_work to 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 7 years ago by tscrim

Replying to jmantysalo:

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 7 years ago by tscrim

  • Reviewers changed from Nathann Cohen to Nathann Cohen, Travis Scrimshaw
  • Status changed from needs_review to positive_review

comment:24 Changed 7 years ago by vbraun

  • Branch changed from u/jmantysalo/poset___latticeposet___meet_join_matrix_algorithm to 391c03bcc290824c78f165d1623baaf1d921734d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.