Opened 8 years ago
Closed 8 years ago
#15827 closed enhancement (fixed)
Fast check for linear dependence
Reported by: | tscrim | Owned by: | tscrim |
---|---|---|---|
Priority: | major | Milestone: | sage-6.2 |
Component: | linear algebra | Keywords: | linear dependence check |
Cc: | Merged in: | ||
Authors: | Travis Scrimshaw | Reviewers: | Marc Mezzarobba |
Report Upstream: | N/A | Work issues: | |
Branch: | c3e7244 (Commits, GitHub, GitLab) | Commit: | c3e72445517e297998cf9adbdb13852b7e88acc0 |
Dependencies: | Stopgaps: |
Description
Currently I can check for linear dependence by
sage: V = QQ^4 sage: ld = lambda vecs: len(V.linear_dependence(ves) > 0
However this is relatively slow since it determines a basis of all such linear dependencies. Also it only works for vector spaces. A faster way to do a simple check is to construct a matrix of the vectors, echelonize the matrix, and see if any of the resulting rows are 0.
Change History (5)
comment:1 Changed 8 years ago by
- Branch set to public/linear_algebra/linear_dep_check-15827
- Commit set to c3e72445517e297998cf9adbdb13852b7e88acc0
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
When the base ring is, say, ZZ
, QQ
, or a polynomial ring, you may want to first compute the echelon form after specializing the variables and/or reducing modulo a small prime. But perhaps that's something for another ticket.
comment:3 Changed 8 years ago by
- Reviewers set to Marc Mezzarobba
- Status changed from needs_review to positive_review
Let's get this patch in, we can always improve the implementation later if necessary.
comment:4 Changed 8 years ago by
Hey Marc,
Thanks for reviewing this. Sorry I let this slip off my radar. I'm not knowledgeable enough to know what to do in regard to how to specialize and/or reduce. So I'm for another ticket unless you know what to do.
Thanks again,
Travis
comment:5 Changed 8 years ago by
- Branch changed from public/linear_algebra/linear_dep_check-15827 to c3e72445517e297998cf9adbdb13852b7e88acc0
- Resolution set to fixed
- Status changed from positive_review to closed
There might be even faster algorithms out there, but this is much faster than how I was doing it before:
New commits:
Added are_linearly_dependent.