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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
2
  • $\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, 2013 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, 2013 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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