9
$\begingroup$

Matrix multiplication using regular (row - column inner product) technique takes $O(n^{3})$ multiplucations and $O(n^{3})$ additions. However assuming equal sized entries (number of bits in each entry of both matrices being multiplied) of size $m$ bits, the addition operation actually happens on $O(n^{3}nm) = O(n^{4}m)$ bits.

So it seems that the true complexity of matrix multiplication if measured via bit complexity should be $O(n^{4})$.

$(1)$Is this correct?

Supposing if one creates an algorithm which reduces the bit complexity to $O(n^{3+\epsilon})$ rather than total multiplications and additions, this might be a sounder approach than say reducing the total multiplications and additions to $O(n^{2+\epsilon})$ as attempted by researchers such as Coppersmith and Cohn.

$(2)$ Is this a valid argument?

$\endgroup$
31
$\begingroup$

No, the bit complexity of matrix multiplication on $M$-bit entries is $n^{\omega} (\log n)^{O(1)} \cdot M (\log M)^{O(1)}$, where $\omega < 2.4$ is the best known matrix multiplication exponent. Multiplication and addition of $M$-bit numbers can be done in $M (\log M)^2$ time. Multiplying two $M$-bit numbers yields a number which has no more than $2M$ bits. Adding $n$ numbers of $M$ bits each, yields a number which has no more than $M+\log n+O(1)$ bits. (Think about it: the sum is at most $n 2^M$, so the bit representation takes no more than $\log (n 2^M)+O(1)$ bits.)

References to fast integer multiplication algorithms can be found with a web search or wikipedia.

$\endgroup$
  • $\begingroup$ I think my argument was flawed. Thank you. I appreciate this. $\endgroup$ – Turbo Oct 21 '10 at 3:03

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.