On May 29, 12:11 pm, Emil <emi...@gmail.com> wrote:
> Thanks! I'm trying to reproduce it, but haven't been successful so far.
>
> But in the meantime, it does seem slightly unsatisfactory that
> something with an obvious deterministic algorithm can fail for random
> reasons. And that this has been observed in a real situation.
Hm, I've looked at the code:
i = 0
while True:
p = <random_prime between 10000 and MAX_MODULUS-5000
if A.has_right_property_at(p):
break
else:
i += 1
if i == 50: raise error
So it's pretty clear there are many matrices for which the algorithm
has a (small) chance to fail and
it's also pretty easy to see how to create examples where the
probability is much larger:
sage: from sage.matrix.matrix_modn_dense import MAX_MODULUS
sage: D=prime_range(10000,MAX_MODULUS-5000)
sage: n=7
sage: l=len(D)//n
sage: M=diagonal_matrix(QQ,[prod(D[b:b+l]) for b in
range(0,len(D),l)],sparse=false)
sage: M.echelonize()
RuntimeError: Bug in _rational_echelon_via_solve in finding pivot
columns.
sage: len(str(M.determinant()))
13537
sage: M.parent()
Full MatrixSpace of 8 by 8 dense matrices over Rational Field
so by modern standards, this matrix isn't even that big. Indeed,
sage: copy(M).echelonize(algorithm='multimodular')
sage: copy(M).echelonize(algorithm='classical')
both succeed. I'm not sure whether hardening
_rational_echelon_via_solve is worth it, but if not then
M.echelon(algorithm="default") should definitely fall back on
"classical" or "multimodular".
--
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
