> And I'll fix this this weekend if nobody else does. It is probably a
> problem doing a multi modular matrix multiply and not having enough
> primes. I designed and mostly implemented the cycle linalg
> algorithms in sage, so this is my fault, probably.
>
I helped with the cyclo linalg code, so I took a quick look -- it
looks like this is an honest problem with the code for matrices over
ZZ:
sage: from sage.matrix.matrix_integer_dense import _lift_crt
sage: _lift_crt(matrix(ZZ,2,1), [matrix(Integers(46337),2,1,[23250,
0])])
[-23087]
[ 0]
Obviously there's just an issue with which residue is getting
returned, because 23087 + 23250 = 46337. Probably a mishandled corner
case in _lift_crt -- I glanced at mpz_crt_vec in sage/ext/
multi_modular.pyx, and lo, and behold! There's a comment that's
telling us what's going on -- around line 589:
# normalize to be between -prod/2 and prod/2.
if mpz_cmp(z[j], self.half_product) > 0:
mpz_sub(z[j], z[j], self.product)
Indeed, that's where the residue is getting changed. So we just need
to change which normalization we return -- or document what _lift_crt
does better, and change the way we use it in cyclotomic matrix
multiply.
> It is very fast. It gets the wrong answer faster than magma.
>
:)
-cc
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
To unsubscribe, reply using "remove me" as the subject.
