Opened 3 years ago

Closed 3 years ago

#28396 closed enhancement (fixed)

faster Möbius matrix for Hasse diagrams

Reported by: chapoton Owned by:
Priority: major Milestone: sage-8.9
Component: combinatorics Keywords:
Cc: tscrim, jmantysalo Merged in:
Authors: Frédéric Chapoton Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: ce66956 (Commits, GitHub, GitLab) Commit: ce66956a4d323ef6607c0ed3a1cf28b64ace36cb
Dependencies: Stopgaps:

Status badges

Description

I propose a choice of algorithm for computing the Mobius matrix of a poset : the current matrix inversion, or the classical recursive formula. The second one seems to be always faster..

Change History (3)

comment:1 Changed 3 years ago by chapoton

  • Branch set to u/chapoton/28396
  • Commit set to ce66956a4d323ef6607c0ed3a1cf28b64ace36cb
  • Status changed from new to needs_review

Timings with the branch applied:

sage: P = posets.TamariLattice(5)
sage: H = P._hasse_diagram
sage: %time H.moebius_function_matrix()
CPU times: user 5.82 ms, sys: 150 µs, total: 5.97 ms
Wall time: 5.72 ms
42 x 42 sparse matrix over Integer Ring (use the '.str()' method to see the entries)
sage: H.__dict__.pop('_moebius_function_matrix')
42 x 42 sparse matrix over Integer Ring (use the '.str()' method to see the entries)
sage: %time H.moebius_function_matrix('matrix')
CPU times: user 53.5 ms, sys: 3.78 ms, total: 57.3 ms
Wall time: 56.8 ms
42 x 42 sparse matrix over Integer Ring (use the '.str()' method to see the entries)

New commits:

ce66956trac 28396 faster Moebius matrices for posets

comment:2 Changed 3 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

There might be some benefit once the lequal_matrix has already been computed, but I agree with everything in this ticket, so it gets a positive review.

comment:3 Changed 3 years ago by vbraun

  • Branch changed from u/chapoton/28396 to ce66956a4d323ef6607c0ed3a1cf28b64ace36cb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.