id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
10791 Fix and upgrade Gram-Schmidt rbeezer jason was "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/ in ()
/sage/sage-4.6.2.alpha4/local/lib/python2.6/site-packages/sage/matrix/matrix2.so 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/element.so 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/rational.so 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.
'''Apply:'''
1. trac_10791-fix-gram-schmidt.patch
2. trac_10791-gram-schmidt-doctests-v2.patch
'''Depends on:'''
1. #10536
2. #10683
3. #10794
" defect needs_review major sage-4.7.1 linear algebra Rob Beezer Martin Raum N/A