Oups, I missed this discussion. So I confirm, that we are using the Krylov based dense minpoly that returns a probabilistic minpoly, and I'm the one to blame for not taking care of this. So far, I don't know of any better certificate for minpoly than checking Pmin(A) = 0 (improved by using the factors, as William pointed out).
I'm also thinking of Danilevskii's elimination: although it could be viewed as a Krylov method, it does not use any randomization, so could it always give the whole minpoly ? As for the use of extensions, the dense method imposes restrictions on the size of the field (in order to use the BLAS). So this might be a severe limiting factor. I'm willing to sort this pb out at Sage Days 16 next week. Clément Jean-Guillaume Dumas a écrit : > William Stein wrote: >> Ouch. (In sage the default for *everything* is proof=True.) Is there any >> easier way to prove correctness of the minpoly (this is a basic exact >> linear algebra question)? > Well I think only deterministic versions of the Frobenius form would > answer this in a lower complexity. > We do not have those algorithms implemented yet. > In small fields they would in general require also working in an > extension, which will also kill the use of the BLAS. > > Therefore in practice, I am afraid that for small finite fields blas > based lcm of non extended minpoly's then blas based evaluation of Pi_1 > at A might be the best for a large range of dense matrix sizes. >> At the least I could factor Pi_1 first >> before substituting in A. >> > yes good idea (and storing the lcm'ed components too might prove also > useful). > Best, > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
