Opened 11 years ago

Last modified 10 years ago

#10791 closed defect

Fix and upgrade Gram-Schmidt — at Version 1

Reported by: rbeezer Owned by: jason, was
Priority: major Milestone: sage-4.8
Component: linear algebra Keywords: sd32
Cc: Merged in:
Authors: Rob Beezer Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by rbeezer)

If a set of vectors has a linearly dependent subset, followed by a vector outside the span of that subset, then the presence of a zero vector in the orthogonal set causes division by a zero dot product.

There are various other improvements that can be made in this routine.

sage: A=matrix(QQ, [[1,2],[2,4],[1,1]])
sage: A.gram_schmidt()
ZeroDivisionError                         Traceback (most recent call last)

/sage/sage-4.6.2.alpha4/<ipython console> in <module>()

/sage/sage-4.6.2.alpha4/local/lib/python2.6/site-packages/sage/matrix/ in sage.matrix.matrix2.Matrix.gram_schmidt (sage/matrix/matrix2.c:31979)()

/sage/sage-4.6.2.alpha4/local/lib/python2.6/site-packages/sage/modules/misc.pyc in gram_schmidt(B)
     55     for i in range(1,n):
     56         for j in range(i):
---> 57             mu[i,j] = B[i].dot_product(Bstar[j]) / (Bstar[j].dot_product(Bstar[j]))
     58         Bstar.append(B[i] - sum(mu[i,j]*Bstar[j] for j in range(i)))
     59     return Bstar, mu

/sage/sage-4.6.2.alpha4/local/lib/python2.6/site-packages/sage/structure/ in sage.structure.element.RingElement.__div__ (sage/structure/element.c:11981)()

/sage/sage-4.6.2.alpha4/local/lib/python2.6/site-packages/sage/rings/ in sage.rings.rational.Rational._div_ (sage/rings/rational.c:15177)()

ZeroDivisionError: Rational division by zero

Patch summary:

  • Original Gram-Schmidt has been adjusted to raise an error on linearly dependent input.
  • Free module version of original Gram-Schmidt was used just one place, and it has been referenced directly, rather than through the matrix version.
  • Matrix version is totally rewritten, building on QR factorizations as possible to get orthonormal bases. Linearly dependent subsets should be handled properly now. Return format has, by necessity, changed.
  • The "noscale" helper method is reminiscent of the old code, but written in a column-oriented QR style.

Depends #10536, #10683, #10794

Change History (2)

Changed 11 years ago by rbeezer

comment:1 Changed 11 years ago by rbeezer

  • Authors set to Rob Beezer
  • Description modified (diff)
  • Status changed from new to needs_review
Note: See TracTickets for help on using tickets.