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

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

CC BY-SA 3.0
2013-06-19T07:03:56.323Z
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?
Lior Eldar
CC BY-SA 3.0
2013-06-19T08:04:06.167Z
$|| A ||$ is the max-norm in Storjohann's paper, so $||A|| \le 2^M$.
Markus Bläser
CC BY-SA 3.0
2013-06-18T18:14:00.827Z
2013-06-18T18:14:00.827Z
Markus Bläser
<p>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:</p>

<p>(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.</p>

<p>(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 $&lt; 2.38$.</p>

<p>Is there a better upper-bound?</p>

<time-complexity><linear-algebra><matrix-product><space-complexity><determinant>
state-of-the-art bit complexity of the determinant
Lior Eldar
# state-of-the-art bit complexity of the determinant

(Asked by: username_0 on 2013-06-18)

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?

**Tags:** time-complexity, linear-algebra, matrix-product, space-complexity, determinant


---

## 1 answers

### Answer by username_1 on 2013-06-18. Score: 5 | Accepted answer

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>

> **Comments:**
> **username_0**: 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?  
> **username_1**: $|| A ||$ is the max-norm in Storjohann's paper, so $||A|| \le 2^M$.  

---

