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:

Status badges

Description (last modified by tscrim)

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 tscrim

  • Authors Travis Scrimshaw deleted
  • Milestone changed from sage-8.1 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

I just added this into #24122. This ticket can be recycled if anyone wants it.

comment:2 Changed 5 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:3 Changed 5 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • 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 tscrim

  • 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:

​430e085Have the kernel be a sparse matrix if the input is sparse.

comment:5 Changed 3 years ago by dkrenn

  • Status changed from needs_review to needs_work
  1. Some doctests are failing.
  2. 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 dkrenn

  • Reviewers set to Daniel Krenn

comment:7 Changed 3 years ago by git

  • Commit changed from 430e0850d4582ce556e188d8d1728d860684f05c to d3bb9aad028130304bd7c192f016900adc1178a9

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

​d3bb9aaMerge 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 git

  • Commit changed from d3bb9aad028130304bd7c192f016900adc1178a9 to 0f2f76eb2e4624c25ee532046a7ee461c5ff8527

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

​0f2f76eFixing doctest and Some last little bit of changes.

comment:9 Changed 3 years ago by tscrim

  • 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:10 Changed 3 years ago by dkrenn

  • Status changed from needs_review to positive_review

LGTM.

comment:11 Changed 3 years ago by vbraun

  • Branch changed from public/linear_algebra/improve_sparse_right_kernel-24138 to 0f2f76eb2e4624c25ee532046a7ee461c5ff8527
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.