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:

Status badges

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 tscrim

  • Branch set to public/linear_algebra/linear_dep_check-15827
  • Commit set to c3e72445517e297998cf9adbdb13852b7e88acc0
  • 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:

c3e7244Added are_linearly_dependent.

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.