Opened 8 years ago

Closed 7 years ago

# Speedup k-closed check

Reported by: Owned by: tscrim tscrim major sage-6.8 matroid theory k-closed Stefan, Rudi, chaoxu Travis Scrimshaw Rudi Pendavingh N/A f4ff999 f4ff999adcb52b3628aab925fe72ca867ed6f9de #18429

### Description

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

### comment:1 Changed 8 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:

 ​ff68516 `Speedup k-closure by using python sets.` ​07c0a3f `Removed unnecessary import.` ​2da089f `One additional tweak to avoid unnecessary checks.`

### comment:2 Changed 8 years ago by git

• Commit changed from 2da089f7f2be369af66a5277eb5c9797dcbc5234 to 6fc7e6e986326b80ef4e32de1ee127ada1dd84b0

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

 ​6fc7e6e `Some more speedups.`

### comment:4 Changed 7 years ago by tscrim

• Milestone changed from sage-6.5 to sage-6.8

### comment:5 follow-up: ↓ 6 Changed 7 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 7 years ago by tscrim

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

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

• Status changed from positive_review to needs_work

Merge conflict (probably #18429 or #18427).

### comment:8 Changed 7 years ago by git

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

 ​e29cbe1 `_intersection_augmentation efficiency tweak` ​01e11cd `Matroid.is_3connected() can now provide a separation to certify non-3-connectedness` ​7d59d68 `One more bug` ​402fdf7 `Killed a doctest bug` ​aa453e7 `Merge branch 'do_not_checkout' into public/matroid/add_matroid_connectivity-18429` ​9b55e71 `Reviewer changes to docstring formatting and trailing whitespace.` ​35b5ab6 `Merge branch 'public/matroid/add_matroid_connectivity-18429' of trac.sagemath.org:sage into u/tscrim/k_closed_speedup-17492` ​b1c4de0 `Allow one to specify ring/field for Wheel matroids` ​750760e `Merge branch 'u/chaoxu/ticket/18427' of trac.sagemath.org:sage into u/tscrim/k_closed_speedup-17492` ​f4ff999 `Removed unneeded imports.`

### comment:9 Changed 7 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 7 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.