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:  sage8.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 sage8.1 to sageduplicate/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 sageduplicate/invalid/wontfix to sage8.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_kernel24138
 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_kernel24138' of git://trac.sagemath.org/sage into public/linear_algebra/improve_sparse_right_kernel24138

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 sage8.1 to sage8.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_kernel24138 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.