Opened 8 years ago

Closed 8 years ago

# Fast check for linear dependence

Reported by: Owned by: tscrim tscrim major sage-6.2 linear algebra linear dependence check Travis Scrimshaw Marc Mezzarobba N/A c3e7244 c3e72445517e297998cf9adbdb13852b7e88acc0

### 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.

### comment:1 Changed 8 years ago by tscrim

• Branch set to public/linear_algebra/linear_dep_check-15827
• Status changed from new to needs_review

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:

### comment:2 Changed 8 years ago by mmezzarobba

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 mmezzarobba

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

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 vbraun

• Branch changed from public/linear_algebra/linear_dep_check-15827 to c3e72445517e297998cf9adbdb13852b7e88acc0
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.