Opened 5 years ago
Closed 3 years ago
#24138 closed enhancement (fixed)
Improve sparse matrix constructions in _right_kernel_matrix_over_*
Reported by: | tscrim | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.8 |
Component: | performance | Keywords: | |
Cc: | Merged in: | ||
Authors: | Travis Scrimshaw | Reviewers: | Daniel Krenn |
Report Upstream: | N/A | Work issues: | |
Branch: | 0f2f76e (Commits, GitHub, GitLab) | Commit: | 0f2f76eb2e4624c25ee532046a7ee461c5ff8527 |
Dependencies: | Stopgaps: |
Description (last modified by )
They currently assume a dense matrix and set a lot of 0 values if the matrix sparse. We can give a better construction.
Change History (11)
comment:1 Changed 5 years ago by
- Milestone changed from sage-8.1 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
comment:2 Changed 5 years ago by
- Status changed from needs_review to positive_review
comment:3 Changed 5 years ago by
- Description modified (diff)
- Milestone changed from sage-duplicate/invalid/wontfix to sage-8.1
- Status changed from positive_review to needs_work
- Summary changed from Use echelonize() instead of echelon_form in right_kernel_matrix echelon basis to Improve sparse matrix constructions in _right_kernel_matrix_over_*
Actually, I can recycle this.
comment:4 Changed 5 years ago by
- Branch set to public/linear_algebra/improve_sparse_right_kernel-24138
- Commit set to 430e0850d4582ce556e188d8d1728d860684f05c
- Status changed from needs_work to needs_review
I am making an assumption, that the kernel of a sparse matrix will still generally be sparse. It will probably increase in density, but I do not think by enough in general to warrant the result being a dense matrix. On an example I tested:
0.000136661807580175 0.00566007653061225
where the top is the original density and the bottom is the density of the right_kernel_matrix
.
New commits:
430e085 | Have the kernel be a sparse matrix if the input is sparse.
|
comment:5 Changed 3 years ago by
- Status changed from needs_review to needs_work
- Some doctests are failing.
- The code itself looks good. As always, I tend to say blank after a comma (PEP8)
+ entries[cur_row,i] = one [...] + for r,p in enumerate(pivots): [...] + if i >= nrows or d[i,i] == 0:
Summary: LGTM once the failing doctests are investigated.
comment:6 Changed 3 years ago by
- Reviewers set to Daniel Krenn
comment:7 Changed 3 years ago by
- Commit changed from 430e0850d4582ce556e188d8d1728d860684f05c to d3bb9aad028130304bd7c192f016900adc1178a9
Branch pushed to git repo; I updated commit sha1. New commits:
d3bb9aa | Merge branch 'public/linear_algebra/improve_sparse_right_kernel-24138' of git://trac.sagemath.org/sage into public/linear_algebra/improve_sparse_right_kernel-24138
|
comment:8 Changed 3 years ago by
- Commit changed from d3bb9aad028130304bd7c192f016900adc1178a9 to 0f2f76eb2e4624c25ee532046a7ee461c5ff8527
Branch pushed to git repo; I updated commit sha1. New commits:
0f2f76e | Fixing doctest and Some last little bit of changes.
|
comment:9 Changed 3 years ago by
- Milestone changed from sage-8.1 to sage-8.8
- Status changed from needs_work to needs_review
Thanks for looking at this.
This takes care of the failing doctest. So my tacit understanding why simply updating the doctest is okay is because the algorithm is now better and doesn't change those entries, meaning they stay at exactly 0 rather than approximately 0.
I don't entirely agree with the comma space (same reasoning as on #27442), but I added it. I also did a few other little PEP8 and maintenance things.
comment:11 Changed 3 years ago by
- Branch changed from public/linear_algebra/improve_sparse_right_kernel-24138 to 0f2f76eb2e4624c25ee532046a7ee461c5ff8527
- Resolution set to fixed
- Status changed from positive_review to closed
I just added this into #24122. This ticket can be recycled if anyone wants it.