> 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 [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/
-~----------~----~----~----~------~----~------~--~---
