Opened 11 years ago
Last modified 10 years ago
#10791 closed defect
Fix and upgrade Gram-Schmidt — at Version 5
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: | Martin Raum |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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:
- trac_10791-fix-gram-schmidt.patch
- trac_10791-gram-schmidt-doctests.patch
Depends on:
Change History (7)
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
- Description modified (diff)
comment:3 Changed 11 years ago by
- Reviewers set to Martin Raum
- Status changed from needs_review to needs_work
In line 6364: properly contains In line 6444: For the integers and the rationals the field
There is only one thing you didn't catch. If you fix that I can give this a positive review (please provide a patch that depends on the current one, to make my life easier) :
File "/scratch/mraum/sagedev/devel/sage-dev/sage/modules/misc.py", line 66:
sage: gram_schmidt(V)
Exception raised:
Traceback (most recent call last):
File "/scratch/mraum/sagedev/local/bin/ncadoctest.py", line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/scratch/mraum/sagedev/local/bin/sagedoctest.py", line 38, in run_one_example
OrigDocTestRunner?.run_one_example(self, test, example, filename, compileflags)
File "/scratch/mraum/sagedev/local/bin/ncadoctest.py", line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest main.example_1[16]>", line 1, in <module>
gram_schmidt(V)###line 66:
sage: gram_schmidt(V)
File "/scratch/mraum/sagedev/local/lib/python/site-packages/sage/modules/misc.py", line 83, in gram_schmidt
raise ValueError?("linearly dependent input for module version of Gram-Schmidt")
ValueError?: linearly dependent input for module version of Gram-Schmidt
Changed 11 years ago by
comment:4 Changed 11 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
Martin - thanks for the careful review and for catching these three items.
"doctests" patch implements changes to fix all three.
Rob
comment:5 Changed 11 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
Ok, the doctest patch fixes all issues. So this gets a positive review
fix patchbot comment