_padic_radix_mat_charpoly_berkowitz, padic_radix_mat_charpoly_hessenberg, padic_radix_mat_charpoly_lift, padic_radix_mat_charpoly

Set cp to the characteristic polynomial $\chi(x) = \det(xI - A)$ of the square matrix mat.

The berkowitz version is the division-free Berkowitz algorithm, with the matrix-vector products done on the matrix packed once (falling back to _gr_mat_charpoly_berkowitz for dimension at most 5, in contexts without a relative precision, and for matrices with exact nonzero entries). For integral entries known to $O(p^N)$ it gives every coefficient to precision about $N$, which is optimal when the matrix is cyclic modulo $p$ but can lose many digits otherwise (dozens for the low coefficients of moderately structured matrices of dimension 16).

The hessenberg version reduces the matrix to Hessenberg form by similarity transformations with pivots of minimal valuation (so that the transformations are in $\mathrm{GL}_n(\mathbb{Z}_p)$), in $O(n^3)$ operations; it loses a few digits.

The lift version gives the optimal precision. With the matrix scaled by a power of $p$ to make it integral, $M$ the exact lift of the entries and $\operatorname{adj}(xI - M) = \sum_k B_k x^k$, a perturbation $E$ with $v(E_{ij}) \ge N_{ij}$ changes $c_k$ by $-\operatorname{tr}(B_k E)$ plus terms of order at least two in $E$, whose coefficients (minors of $xI - M$) are integral. Hence $c_k(A) = c_k(M) + O(p^{N_k})$ with $N_k = \min(2 N_{\min}, \min_{ij} (N_{ij} + v((B_k)_{ji})))$, the precision of the differential of $\chi$. The coefficients $c_k(M)$ are computed modulo $p^{2 N_{\min}}$ by the hessenberg version at a raised working precision (retried with more digits if needed, with the berkowitz version as a last resort), and the $B_k$ by the recurrence $B_{n-1} = I$, $B_{k-1} = M B_k + c_k I$, modulo one word first and modulo $p^{N_{\min}}$ if valuations at that bound matter, with $n$ matrix products. Exact matrices give the exact characteristic polynomial (multimodular), rounded to the context precision.

The lifted entries are reduced modulo the largest working precision, so that entries of high valuation cost nothing. The working precision $2(N_{\min} + s)$, where $p^s$ is the scaling, is large when an entry has a much smaller valuation (or error term) than the others; the lift version returns GR_UNABLE when $N_{\min} + s > 64(R + n) + 1024$, where $R$ is the largest relative precision of an inexact entry. For exact matrices it returns GR_UNABLE when the exact characteristic polynomial would exceed the size_limit of the context, when the entries of $M$ have more than $4 r + 256$ digits for a finite context precision $r$, or when they are dominated by powers of $p$ (valuations above four times the size of the units plus 256 digits), which Berkowitz's algorithm in $\mathbf{Q}_p$ handles without expanding them.

padic_radix_mat_charpoly implements the generic method. For matrices with integral entries of uniform precision $N$ that are cyclic modulo $p$ (tested with a random Krylov basis over $\mathbb{F}_p$), the optimal precision is $N$ for every coefficient: the hessenberg version is tried first and accepted if it attains it (as for matrices that are generic modulo $p$), and otherwise the berkowitz version, which always does, is used. Other matrices use the lift version, together with Danilevsky's algorithm (keeping the more precise result for each coefficient) where the bound $2 N_{\min}$ limits it, and the berkowitz version when the lift version gives up. With the context flag PADIC_RADIX_FAST_LINALG, the hessenberg version is used for all matrices.