2009/6/15 Jean-Guillaume Dumas <jean-guillaume.du...@imag.fr>:
>
> William Stein wrote:
>> On Wed, Jun 10, 2009 at 6:03 PM, Yann<yannlaiglecha...@gmail.com> wrote:
>>
>>> ----------------------------------------------------------------------
>>> | Sage Version 4.0.1, Release Date: 2009-06-06 |
>>> | Type notebook() for the GUI, and license() for information. |
>>> ----------------------------------------------------------------------
>>> sage: A=matrix(GF(3),2,[0,0,1,2])
>>> sage: R.<x>=GF(3)[]
>>> sage: D={ x:0 , x+1:0 , x^2+x:0 }
>>> sage: for i in range(100000):
>>> ....: D[A._minpoly_linbox()]+=1
>>> ....:
>>> sage: D
>>> {x: 38266, x + 1: 29397, x^2 + x: 32337}
>>>
>>>
>>
>> You're absolutely right! This *sucks* -- it seems like nothing we
>> have ever wrapped in Linbox is right at first. Hopefully the issue is
>> that somehow the algorithm is only supposed to be probabilistic, and
>> we're just misusing it in sage (quite possible).
>>
>> Anyway, Clement Pernet will be at Sage Days next week, and we'll sort this
>> out.
>> Many thanks for brining this to our attention!
>>
>> This is now:
>>
>> http://trac.sagemath.org/sage_trac/ticket/6296
>>
> Well, I think this was corrected in linbox-1.1.6:
We're using linbox-1.1.6 in Sage.
>
> The minpoly algorithm used depends on which method you are using from
> LinBox of course but,
> If you use the solution "minpoly" you will get the blackbox algorithm
> (just like if you specify "minpoly(pol, mat, Method::Blackbox())")
> then (since sept 2008 and 1.1.6) we will end up using an extension field
> to compute the minpoly (on my machine it will be GF(3^10)) and then
> I e.g. got the following result for one try (the algorithm is still
> probabilistic, but has a much larger success rate, roughly around 1/3^10):
Here's what we're using:
void linbox_modn_dense_minpoly(mod_int modulus, mod_int **mp, size_t*
degree, size_t n, mod_int **matrix, int do_minpoly) {
ModInt F((double)modulus);
size_t m = n;
DenseMatrix<ModInt> A(linbox_new_modn_matrix( modulus, matrix, m, m));
GivPolynomial<ModInt::Element> m_A;
if (do_minpoly)
minpoly(m_A, A);
else
charpoly(m_A, A);
(*mp) = new mod_int[m_A.size()];
*degree = m_A.size() - 1;
for (size_t i=0; i <= *degree; i++) {
(*mp)[i] = (mod_int)m_A[i];
}
}
This is from the file interfaces/linbox-sage.C, which ships with linbox.
Many thanks for clarifying that minpoly fails with some probability,
and that we need to call it multiple times, take lcm's, and force the
user to give the option "proof=False" to use it.
Just out of curiosity, is there any provably correct minpoly in
linbox? We don't have one in Sage at all, so it would be useful so
we don't have to implement one from scratch.
William
>
> > 99993 minimal Polynomials are x^2 +x, 3 minimal polynomial are x+1, 4
> minimal polynomials are x
>
> Now for a so small matrix it could be better to use a dense version,
> which can be called by "minpoly(pol,mat,Method::Elimination())".
> If i am correct this dense version is also probabilistic (choice of the
> Krylov non-zero vector) and therefore should also pick vectors from an
> extension.
> This is not the case in 1.1.6.
> Clément can you confirm this ? If so it should be easy to fix, the same
> way we fixed Wiedemann.
>
> For your example matrix in some of the cases, when vectors [1,1], and
> [2,2] are chosen the Krylov space has rank 1, whereas for other non zero
> vectors it has rank 2 and
> thus the dense minbpoly will be x^2+x or x+1 ...
>
> btw, the returned polynomial is always a factor of the true polynomial,
> therefore to get a 1/3^{10k} probability of success it will be
> sufficient to perform the lcm of k runs.
>
> Best,
>
> --
> Jean-Guillaume Dumas.
> ____________________________________________________________________
> jean-guillaume.du...@imag.fr Tél.: +33 476 514 866
> Université Joseph Fourier, Grenoble I. Fax.: +33 476 631 263
> Laboratoire Jean Kuntzmann, Mathématiques Appliquées et Informatique
> 51, avenue des Mathématiques. LJK/IMAG - BP53. 38041 Grenoble FRANCE
> http://ljk.imag.fr/membres/Jean-Guillaume.Dumas
> ____________________________________________________________________
>
>
> >
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support-unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
