Here's a patch that resolves the underlying issue, namely that elements of the fraction field over a generic polynomial ring couldn't be cast back into the original ring despite having denominator 0. This came up because the Hessenberg form calculation involved passing to the field of fractions. An example is perhaps more clear:
sage: W.<w>=QQ['w'] sage: WZ.<z>=W['z'] sage: WZ(WZ.fraction_field()(z)) Traceback (most recent call last): ... TypeError: Unable to coerce 0 (<class 'sage.rings.polynomial_element_generic.Polynomial_rational_dense'>) to Rational I agree with Kyle that small cases should default to the naive algorithm, 2x2 at least, especially if working in the fraction field is expensive in comparison. Should I change this? - Robert --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
poly-det-fix.diff
Description: Binary data
On Mar 21, 2007, at 2:06 AM, Kyle Schalm wrote: >> On 3/20/07, Kyle Schalm <[EMAIL PROTECTED]> wrote: >>> there is trouble with the determinant method on a matrix over a >>> funky ring >>> (yes, the same funky ring causing all my other problems). in its >>> simplest >>> form: >>> >>> In [43]: W.<w>=QQ['w'] >>> In [44]: WZ.<z>=W['z'] >>> In [45]: matrix(WZ,2,2,[1,z,z,z^2]).det() >>> Out[45]: <kaboom!!!> >> >> The attached patch fixes this. It's a one liner, so if you have >> trouble >> applying it, just look at it and make the change by hand, then do >> sage -br. It's not the "right" fix, though it is in no way wrong >> either; >> don't worry, in my personal codebase I've created a doctest that >> exposes the true problem that causes the issue above. > > it works, but is very slow. the naive algorithm is 25x to 100x > faster for > the 3x3 examples below. this should perhaps be the default > algorithm for > at least up to 4x4, maybe more. > > i was afraid to write out the 4x4 case (see below), but it could be > done. > otoh, the looped version already present in the determinant method > would > probably be fine too. > > btw, i did have trouble applying the patch. it said, > "abort: outstanding uncommitted changes". > any idea what that means? > > here's my code and timings: > > ################################### > > def determinant(W): > n=W.ncols() > if n==1: > return W[0,0] > if n==2: > return W[0,0]*W[1,1]-W[0,1]*W[1,0] > if n==3: > return W[0,0]*(W[1,1]*W[2,2]-W[1,2]*W[2,1]) - \ > W[0,1]*(W[1,0]*W[2,2]-W[1,2]*W[2,0]) + \ > W[0,2]*(W[1,0]*W[2,1]-W[1,1]*W[2,0]) > return W.determinant() > > #################################### > # timings on a sample matrix. > # (simpler examples i tried were too fast to produce useful > # comparisons.) > > In [31]: W.<w1,w2>=QQ['w1','w2'] > > In [32]: WZ.<z>=W['z'] # the now well-known "schalm ring" > > In [34]: m=wronskian_matrix([(z-1)^2,(z-w1)^2,(z-w2)^2]); m > Out[34]: > [ z^2 + (-2)*z + 1 z^2 + (-2*w1)*z + w1^2 z^2 + (-2*w2)*z + w2^2] > [ 2*z + -2 2*z + -2*w1 2*z + -2*w2] > [ 2 2 2] > > In [36]: time determinant(m) > CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s > Wall time: 0.01 > Out[36]: 4*w2 - 4*w2^2 - 4*w1 + 4*w1*w2^2 + 4*w1^2 - 4*w1^2*w2 > > In [37]: time m.det() > CPU times: user 0.50 s, sys: 0.00 s, total: 0.50 s > Wall time: 0.50 > Out[37]: 4*w2 - 4*w2^2 - 4*w1 + 4*w1*w2^2 + 4*w1^2 - 4*w1^2*w2 > > ###################################################### > # some other results were worse: > > In [54]: m=wronskian_matrix([(z-1)^3,(z-w1)^2,(z-w2)^2]) > > In [55]: time m.det() > CPU times: user 1.23 s, sys: 0.00 s, total: 1.23 s > Wall time: 1.24 > Out[55]: ... > > In [56]: time determinant(m) > CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s > Wall time: 0.02 > Out[56]: ... > > ################################## > # 3 seconds, ouch! > > In [60]: m=wronskian_matrix([(z-1)^4,(z-w1)^3,(z-w2)^2]) > > In [61]: time m.det() > CPU times: user 3.15 s, sys: 0.00 s, total: 3.15 s > Wall time: 3.15 > Out[61]: ... > > In [62]: time determinant(m) > CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s > Wall time: 0.04 > Out[62]: ... > > > --~--~---------~--~----~------------~-------~--~----~ > To post to this group, send email to sage-devel@googlegroups.com > To unsubscribe from this group, send email to sage-devel- > [EMAIL PROTECTED] > For more options, visit this group at http://groups.google.com/ > group/sage-devel > URLs: http://sage.scipy.org/sage/ and http:// > modular.math.washington.edu/sage/ > -~----------~----~----~----~------~----~------~--~---
