Opened 6 years ago
Closed 6 years ago
#21823 closed enhancement (fixed)
LatticePosets: Faster is_pseudocomplemented()
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  combinatorics  Keywords:  
Cc:  chapoton, tscrim  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  45f8bc1 (Commits, GitHub, GitLab)  Commit:  45f8bc19da7639eecacedb63f3eb3347050f78ab 
Dependencies:  Stopgaps: 
Description
After
P = Posets.BooleanLattice(3) _ = P.is_pseudocomplemented() P = Posets.BooleanLattice(9) _ = P.meet_matrix() _ = P.join_matrix()
without this patch:
sage: timeit('P.is_pseudocomplemented()') 5 loops, best of 3: 143 ms per loop
after this patch:
sage: timeit('P.is_pseudocomplemented()') 125 loops, best of 3: 4.09 ms per loop
Change History (12)
comment:1 Changed 6 years ago by
 Branch set to u/jmantysalo/fasterispseudocomplemented
comment:2 Changed 6 years ago by
 Cc chapoton added
 Commit set to d7abb5758608f5d2c598cbe7b0806b8a7348138b
 Status changed from new to needs_review
comment:3 Changed 6 years ago by
proof seems ok to me
it says that the pseucomplement of x is the meet of the pseudocomplements of the atoms below x
proof is very simple, take 7 lines at start of proof of Theoreme 3.3 page 96
You just need 3 French words : évident = obvious, montrer = show, implique = implies
:)
comment:4 Changed 6 years ago by
 Cc tscrim added
Thanks Frédéric!
Travis, can you review this trivial patch? I will optimize skeleton()
in another ticket.
comment:5 followup: ↓ 7 Changed 6 years ago by
I think you should add the reference and put a short description (perhaps an ALGORITHM:
block) in the docstring.
comment:6 Changed 6 years ago by
 Commit changed from d7abb5758608f5d2c598cbe7b0806b8a7348138b to 84c874f7127edc1260594c00617cd3c4d2ad7001
Branch pushed to git repo; I updated commit sha1. New commits:
84c874f  Move reference from comments to visible.

comment:7 in reply to: ↑ 5 Changed 6 years ago by
Replying to tscrim:
I think you should add the reference and put a short description (perhaps an
ALGORITHM:
block) in the docstring.
Done.
(Contains a nonrelated typo correction "fintie" > "finite".)
comment:8 followup: ↓ 10 Changed 6 years ago by
Now we have that master reference file, so the reference should go in there.
comment:9 Changed 6 years ago by
 Commit changed from 84c874f7127edc1260594c00617cd3c4d2ad7001 to 45f8bc19da7639eecacedb63f3eb3347050f78ab
Branch pushed to git repo; I updated commit sha1. New commits:
45f8bc1  Reference to master file.

comment:10 in reply to: ↑ 8 Changed 6 years ago by
Replying to tscrim:
Now we have that master reference file, so the reference should go in there.
Good point. This should work, but takes time to compile... How to doccompile only master references file?
comment:11 Changed 6 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
I don't know. (Personally I wasn't so happy with this shift.) LGTM though.
comment:12 Changed 6 years ago by
 Branch changed from u/jmantysalo/fasterispseudocomplemented to 45f8bc19da7639eecacedb63f3eb3347050f78ab
 Resolution set to fixed
 Status changed from positive_review to closed
Frédéric, can you check the reference? I found it from http://cams.ehess.fr/docannexe.php?id=1111, but do not understand French.
New commits:
Faster is_pseudocomplemented().