4
$\begingroup$

I'm trying to understand the full bit-complexity of computing the determinant of an $n\times n$ integer matrix, with each entry represented by $M$ bits. I would like to know what is the state-of-the-art bit-complexity. As far as I could find, the two possible candidates are:

(1) The low-depth circuits, due to Csansky [1976], and Berkowitz [1984], but these, despite having $log^2(n)$ depth, require some $n^4$ bit operations.

(2) The Bunch and Hopcroft [1974] algorithm, which takes any black-box algorithm for integer matrix multiplication, and produces an algorithm for the determinant using the same $\textbf{arithmetic}$ complexity. Since any two $M$-bit integers can be multiplied in $M \cdot log^2(M)$ operations, and the largest value during the computation can be as large as $2^{M n}$, it seems that its bit-complexity is $\tilde{O}(M n^{\omega+1})$, where $\omega$ is the state-of-the-art matrix product coefficient $< 2.38$.

Is there a better upper-bound?

$\endgroup$
5
$\begingroup$

Storjohann designs a Las-Vegas algorithm with $\tilde O(n^\omega M)$ bit operations http://dx.doi.org/10.1016/j.jco.2005.04.002

Prior to this, Kaltofen and Villard gave improved algorithms, see http://lara.inist.fr/bitstream/handle/2332/850/LIP-RR2003-36.pdf%3Fsequence%3D1

$\endgroup$
  • $\begingroup$ Thanks for the great links! However, I do not understand the bound you are stating: it says in the paper, that the bit complexity is $\tilde{O}(n^{\omega} log (\left\|A\right\|))$, so if $A$ is an $n\times n$ matrix of $M$ bits each, then $\left\|A\right\|$ can be as large as $2^{Mn}$, so its complexity is exactly $\tilde{O}(n^{\omega+1} M)$. What am I missing here? $\endgroup$ – Lior Eldar Jun 19 '13 at 7:03
  • 1
    $\begingroup$ $|| A ||$ is the max-norm in Storjohann's paper, so $||A|| \le 2^M$. $\endgroup$ – Markus Bläser Jun 19 '13 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.