Opened 6 years ago

Closed 6 years ago

#21823 closed enhancement (fixed)

LatticePosets: Faster is_pseudocomplemented()

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.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:

Status badges

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 jmantysalo

  • Branch set to u/jmantysalo/faster-is-pseudocomplemented

comment:2 Changed 6 years ago by jmantysalo

  • Cc chapoton added
  • Commit set to d7abb5758608f5d2c598cbe7b0806b8a7348138b
  • Status changed from new to needs_review

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:

d7abb57Faster is_pseudocomplemented().

comment:3 Changed 6 years ago by chapoton

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 jmantysalo

  • Cc tscrim added

Thanks Frédéric!

Travis, can you review this trivial patch? I will optimize skeleton() in another ticket.

comment:5 follow-up: Changed 6 years ago by tscrim

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 git

  • Commit changed from d7abb5758608f5d2c598cbe7b0806b8a7348138b to 84c874f7127edc1260594c00617cd3c4d2ad7001

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

84c874fMove reference from comments to visible.

comment:7 in reply to: ↑ 5 Changed 6 years ago by jmantysalo

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 non-related typo correction "fintie" -> "finite".)

comment:8 follow-up: Changed 6 years ago by tscrim

Now we have that master reference file, so the reference should go in there.

comment:9 Changed 6 years ago by git

  • Commit changed from 84c874f7127edc1260594c00617cd3c4d2ad7001 to 45f8bc19da7639eecacedb63f3eb3347050f78ab

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

45f8bc1Reference to master file.

comment:10 in reply to: ↑ 8 Changed 6 years ago by jmantysalo

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 doc-compile only master references file?

comment:11 Changed 6 years ago by tscrim

  • 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 vbraun

  • Branch changed from u/jmantysalo/faster-is-pseudocomplemented to 45f8bc19da7639eecacedb63f3eb3347050f78ab
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.