Improve charpoly computations

[saraedum]

At the moment I can see two areas where a lot of performance could be gained. One is the computation of ϕ-adic expansions and the other one I'd like to discuss here is the collapsing of a tower of extensions by replacing it by a single simple extension generated by a unformizing element.

What I do at the moment to collapse a tower of simple extensions is:

• guess a uniformizing element that generates that extension
• write down its matrix with respect to the obvious basis given by products of powers of generators of all the intermediate fields
• compute the characteristic polynomial
• check whether it's the minimal polynomial (i.e., square-free)
• find a simpler polynomial that generates the same field extension

The only step that is a problem at the moment is the computation of the characteristic polynomial. Currently, I just do this computation with Sage's algorithm over the rationals. I think that this algorithm is quite good, but due to coefficient explosion, I guess, this takes a very long time.

I would be happy to discuss some ideas on how to make this faster @swewers.

[saraedum]

Something that did not work: Do the computation in Sage's Qp. This does not work at all (at least in the way it is implemented for fields in Sage.) I usually end up with a x^N as the characteristic polynomial unless I use thousands of digits of precision which is then much slower than the computation over the rationals.

[saraedum]

Something that I did not get to work yet: The resulting polynomial is going to be integral, so instead of doing the computation over the rationals, I should be able to do it in Zmod(p^N) for some reasonable N. The algorithm that Sage has for this is reasonably fast. However, some entries in the matrix of multiplication are divisible by p. Is there some way to massage my basis (or the uniformizer) so I get an integral matrix?

[swewers]

Have a look at mclf/padic_extensions/fake_padic_completion.py. I grappled with the same problems there and found a solution which sort of worked. Unfortunately, the thing is in a very poor state; no doctest, and I frequently choose some arbitrary bounds for computations, with no guarantee that the result is correct in the end.

The collapsing to a single extension is done in extension; the computation of the characteristic polynomial mod p^N in characteristic_polynomial_mod. The main trick is to work with a 'p-integral basis'.