padic_radix_mat_det_lu_full, padic_radix_mat_det_levels, padic_radix_mat_det

Set res to the determinant of the square matrix A. The lu_full version uses Gaussian elimination with full pivoting on valuations (an entry of minimal valuation in the whole remaining submatrix). Then the multipliers and the pivot rows have valuations at least that of the pivot, the Schur complements keep the absolute precision of the input, and the pivots have the valuations $a_1 \le \cdots \le a_n$ of the elementary divisors. For a matrix with entries known to $O(p^N)$ (and $a_n < N$) the determinant is obtained to precision $N + a_1 + \cdots + a_{n-1}$, which is optimal: it is that of the differential $d \det(A) = \operatorname{tr}(\operatorname{adj}(A)\, dA)$. In comparison, division-free algorithms (Berkowitz, cofactor expansion) only give precision about $N$, losing up to $v(\det A) - a_n$ digits, and Gaussian elimination with the first nonzero pivot loses precision growing with the dimension for small $p$, even for generic matrices (about 19 digits at $n = 60$ for $p = 7$). If the remaining submatrix consists of zeros, the determinant of that block is bounded using the sums of the row and column minima of the precisions.

The levels version is a blocked form of full pivoting. At the minimal valuation $a$ of the current Schur complement $S$, a rank-revealing LU decomposition of $(S / p^a) \bmod p$ over $\mathbb{F}_p$ selects $r$ rows and columns such that $S_{11} = p^a U$ with $U$ invertible modulo $p$: these $r$ pivots all have valuation $a$, as in full pivoting, and are eliminated at once, with $\det S = \pm \det(S_{11}) \det(S_{22} - S_{21} S_{11}^{-1} S_{12})$, using the LU decomposition of $S_{11}$, triangular solves and one matrix product. The new Schur complement has entries of valuation at least $a + 1$. The precision is again optimal, and the cost is that of a blocked LU decomposition (a single level for a matrix invertible modulo $p$).

padic_radix_mat_det implements the generic method gr_mat_det: the cofactor formula for $n \le 2$, the lu_full version up to a dimension depending on the precision (40 at one limb, 24 at two limbs, 16 beyond), and the levels version above.