#10791: Fix and upgrade Gram-Schmidt
-------------------------------+--------------------------------------------
Reporter: rbeezer | Owner: jason, was
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.8
Component: linear algebra | Resolution:
Keywords: sd32 | Work_issues:
Upstream: N/A | Reviewer: Martin Raum, John Palmieri
Author: Rob Beezer | Merged:
Dependencies: |
-------------------------------+--------------------------------------------
Changes (by rbeezer):
* status: needs_work => needs_review
* reviewer: Martin Raum => Martin Raum, John Palmieri
Old description:
> 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/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. [attachment:trac_10791-fix-gram-schmidt-v3.patch]
> 1. [attachment:trac_10791-gram-schmidt-negative-zero.patch]
>
> '''Depends on:'''
> 1. #10536
> 2. #10683
> 3. #10794
New description:
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/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. [attachment:trac_10791-fix-gram-schmidt-v3.patch]
1. [attachment:trac_10791-gram-schmidt-negative-zero.patch]
1. [attachment:trac_10791-gram-schmidt-qqbar-doctests.patch]
'''Depends on:'''
1. #10536
2. #10683
3. #10794
--
Comment:
Oh man, that was painful. I am really rusty. Use it or lose it. But I'm
back.
Patch fixes failing doctests over QQbar, mostly by checking small norms on
matrices which should be the zero matrix. A bit brutal, but we don't have
{{{round()}}} and {{{zero_at()}}} for matrices over QQbar. (Those'd be a
nice additions, no?).
I got identical failures on Ubuntu. Now passing all tests in
matrix/matrix2.pyx. My 4.8.alpha3 has some weirdness (Atlas segfaults),
but I think this should be OK.
Thanks for the look, John and Jason. Off to investigate a few other
things.
Rob
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10791#comment:30>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
