Computing the Determinant via the Generalized Euclidean Algorithm

Abstract

We present an algorithm with a natural geometric interpretation for computing the determinant of a matrix $B\in {\mathbb{Z}}^{d\times d}$. It improves upon the current fastest deterministic algorithms by a factor of $d^{\omega (1)+1-\omega (2)}\approx d^{0.1213}$, where $\omega (k)$ denotes the exponent required for multiplying a $d\times d$ matrix with a $d\times d^k$ matrix. Our approach builds on a recent result of Klein and Reuter (STOC 2025), who introduced a novel algorithmic idea for lattice basis computation that can be viewed as extending the Euclidean algorithm from $\mathbb{Z}$ to ${\mathbb{Z}}^d$. By adapting their techniques, we compute the determinant with the same bit complexity as applying the generalized Euclidean algorithm to an input matrix $A\in {\mathbb{Z}}^{d\times 2d}$ with $\Vert A\Vert =\Vert B\Vert$, namely $\tilde{O}(d^{\omega (2)}\log \Vert B\Vert )$. Prior to this work, the fastest deterministic algorithm for computing the determinant required $\tilde{O}(d^{\omega (1)+1}\log \Vert B\Vert )$ bit operations.