Rzeczywista złożoność bitowa mnożenia macierzy wynosi

Mnożenie macierzy przy użyciu techniki regularnej (iloczyn wewnętrzny rzędów i kolumn) $O(n^{3})$ mnożenia i $O(n^{3})$wzbogacenie. Jednak przy założeniu, że wpisy o jednakowej wielkości (liczba bitów w każdym wpisie obu macierzy jest mnożona) o wielkości$m$ bitów, operacja dodawania faktycznie się dzieje $O(n^{3}nm) = O(n^{4}m)$ bitów

Wydaje się więc, że prawdziwa złożoność mnożenia macierzy, jeśli jest mierzona za pomocą złożoności bitowej, powinna wynosić $O(n^{4})$.

$(1)$Czy to jest poprawne?

Załóżmy, że tworzy się algorytm, który zmniejsza złożoność bitów do $O(n^{3+\epsilon})$ zamiast całkowitej liczby mnożeń i dodatków, może to być bardziej rozsądne podejście niż powiedzieć, że łączna liczba mnożeń i dodatków do $O(n^{2+\epsilon})$ jak próbowali badacze tacy jak Coppersmith i Cohn.

$(2)$ Czy to prawidłowy argument?

Nie, złożoność bitowa mnożenia macierzy jest włączona $M$-bit wpisy są $n^{\omega} (\log n)^{O(1)} \cdot M (\log M)^{O(1)}$, gdzie $\omega < 2.4$jest najlepiej znanym wykładnikiem mnożenia macierzy. Mnożenie i dodawanie$M$-bitowe liczby można wprowadzić w $M (\log M)^2$czas. Mnożenie dwóch$M$-bitowe liczby dają liczbę, która nie ma więcej niż $2M$bitów Dodawanie$n$ Numery tego $M$ bitów każdy, daje liczbę, która nie ma więcej niż $M+\log n+O(1)$bitów (Pomyśl o tym: suma jest co najwyżej$n 2^M$, więc reprezentacja bitowa nie zajmuje więcej niż $\log (n 2^M)+O(1)$ bitów.)

Odnośniki do algorytmów szybkiego mnożenia liczb całkowitych można znaleźć w wyszukiwarce internetowej lub w Wikipedii.