Opened 7 years ago

Closed 6 years ago

#17492 closed enhancement (fixed)

Speedup k-closed check

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-6.8
Component: matroid theory Keywords: k-closed
Cc: Stefan, Rudi, chaoxu Merged in:
Authors: Travis Scrimshaw Reviewers: Rudi Pendavingh
Report Upstream: N/A Work issues:
Branch: f4ff999 (Commits, GitHub, GitLab) Commit: f4ff999adcb52b3628aab925fe72ca867ed6f9de
Dependencies: #18429 Stopgaps:

Status badges

Description

Right now, checking for k-closed is slow because it uses Sage sets whereas we only need python sets.

Change History (10)

comment:1 Changed 7 years ago by tscrim

  • Branch set to u/tscrim/k_closed_speedup-17492
  • Commit set to 2da089f7f2be369af66a5277eb5c9797dcbc5234
  • Status changed from new to needs_review
  • Summary changed from Speedup k-closure to Speedup k-closed check

With patch:

sage: PR4 = RootSystem(['D',4]).root_lattice().positive_roots()
sage: m4 = matrix(map(lambda x: x.to_vector(), PR4)).transpose()
sage: M4 = Matroid(m4)
sage: %timeit M4.is_k_closed(3)
10 loops, best of 3: 147 ms per loop
sage: %timeit M4.is_k_closed(4)
1 loops, best of 3: 413 ms per loop
sage: PR5 = RootSystem(['D',5]).root_lattice().positive_roots()
sage: m5 = matrix(map(lambda x: x.to_vector(), PR5)).transpose()
sage: M5 = Matroid(m5)
sage: %timeit M5.is_k_closed(3)
1 loops, best of 3: 1.45 s per loop

Before:

sage: %timeit M4.is_k_closed(3)
1 loops, best of 3: 776 ms per loop
sage: %timeit M4.is_k_closed(4)
1 loops, best of 3: 3.09 s per loop
sage: %timeit M5.is_k_closed(3)
1 loops, best of 3: 4.16 s per loop

So we are getting a 3x~4x speedup.


New commits:

ff68516Speedup k-closure by using python sets.
07c0a3fRemoved unnecessary import.
2da089fOne additional tweak to avoid unnecessary checks.

comment:2 Changed 7 years ago by git

  • Commit changed from 2da089f7f2be369af66a5277eb5c9797dcbc5234 to 6fc7e6e986326b80ef4e32de1ee127ada1dd84b0

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

6fc7e6eSome more speedups.

comment:3 Changed 7 years ago by tscrim

  • Cc Stefan Rudi added

comment:4 Changed 6 years ago by tscrim

  • Cc chaoxu added
  • Milestone changed from sage-6.5 to sage-6.8

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

Hi Travis,

I checked out this patch and it all works as advertised. Positive review, except for one thing:

A merge with 'master' was necessary before sage -b would successfully build this on my sage 6.7. The logical thing would perhaps be to push the merged branch I created, but I hesitate to do this since my recent experience with git tell me that I might not fully understand how things work when it comes to this. Perhaps there is another, better way, and also I do not want to risk messing up your work.

So please update the branch to something that compiles out of the box, or argue that this is unnecessary. Then feel free to set this to 'positive review'.

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

  • Reviewers set to Rudi Pendavingh
  • Status changed from needs_review to positive_review

Replying to Rudi:

I checked out this patch and it all works as advertised. Positive review, except for one thing:

Thank you for the review.

A merge with 'master' was necessary before sage -b would successfully build this on my sage 6.7. The logical thing would perhaps be to push the merged branch I created, but I hesitate to do this since my recent experience with git tell me that I might not fully understand how things work when it comes to this. Perhaps there is another, better way, and also I do not want to risk messing up your work.

So please update the branch to something that compiles out of the box, or argue that this is unnecessary. Then feel free to set this to 'positive review'.

The branch is merged with the latest develop at merge time, so if this works after merging (cleanly, i.e., without having to handle any merge conflicts) with master (or now develop at 6.8.beta0), there should be no problems.

For the record, my usual workflow is to always merge the branch into my current develop branch as my current spkgs might be incompatible with older versions of Sage. Plus it saves on compilation time. Also if you push it to a different branch and set that, there is no way to corrupt my work on my branch.

Thank you again.

comment:7 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict (probably #18429 or #18427).

comment:8 Changed 6 years ago by git

  • Commit changed from 6fc7e6e986326b80ef4e32de1ee127ada1dd84b0 to f4ff999adcb52b3628aab925fe72ca867ed6f9de

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

e29cbe1_intersection_augmentation efficiency tweak
01e11cdMatroid.is_3connected() can now provide a separation to certify non-3-connectedness
7d59d68One more bug
402fdf7Killed a doctest bug
aa453e7Merge branch 'do_not_checkout' into public/matroid/add_matroid_connectivity-18429
9b55e71Reviewer changes to docstring formatting and trailing whitespace.
35b5ab6Merge branch 'public/matroid/add_matroid_connectivity-18429' of trac.sagemath.org:sage into u/tscrim/k_closed_speedup-17492
b1c4de0Allow one to specify ring/field for Wheel matroids
750760eMerge branch 'u/chaoxu/ticket/18427' of trac.sagemath.org:sage into u/tscrim/k_closed_speedup-17492
f4ff999Removed unneeded imports.

comment:9 Changed 6 years ago by tscrim

  • Dependencies set to #18429
  • Status changed from needs_work to positive_review

Conflict was #18429, but I also merged in #18427 to be safe.

comment:10 Changed 6 years ago by vbraun

  • Branch changed from u/tscrim/k_closed_speedup-17492 to f4ff999adcb52b3628aab925fe72ca867ed6f9de
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.