Fast check for linear dependence

[tscrim]

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.

Component: linear algebra

Keywords: linear dependence check

Author: Travis Scrimshaw

Branch/Commit: c3e7244

Reviewer: Marc Mezzarobba

Issue created by migration from https://trac.sagemath.org/ticket/15827

[tscrim]

Branch: public/linear_algebra/linear_dep_check-15827

[tscrim]

comment:1

There might be even faster algorithms out there, but this is much faster than how I was doing it before:

sage: M = QQ^3
sage: vecs = [M([1,2,3]), M([4,5,6]), M([3,3,3])]
sage: %timeit len(M.linear_dependence(vecs)) > 0
100 loops, best of 3: 5.71 ms per loop

sage: %timeit M.are_linearly_dependent(vecs)
1000 loops, best of 3: 530 us per loop

---

New commits:

c3e7244

Added are_linearly_dependent.

[tscrim]

Commit: c3e7244

[mezzarobba]

comment:2

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.

[mezzarobba]

Reviewer: Marc Mezzarobba

[mezzarobba]

comment:3

Let's get this patch in, we can always improve the implementation later if necessary.

[tscrim]

comment:4

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

[vbraun]

Changed branch from public/linear_algebra/linear_dep_check-15827 to c3e7244