Die wahre Bitkomplexität der Matrixmultiplikation ist

Die Matrixmultiplikation unter Verwendung der regulären Technik (Zeilen-Spalten-Innenprodukt) erfordert -Multiplikationen und O ( n 3 ) -Additionen . Unter der Annahme gleich großer Einträge (Anzahl der Bits in jedem Eintrag beider Matrizen, die multipliziert werden) mit einer Größe von m Bits erfolgt die Additionsoperation tatsächlich für O ( n 3 n m ) = O ( n 4 m ) Bits.$O(n^{3})$$O(n^{3})$$m$$O(n^{3}nm) = O(n^{4}m)$

Es scheint also, dass die wahre Komplexität der Matrixmultiplikation, gemessen über die Bitkomplexität, .$O(n^{4})$

Ist das richtig?$(1)$

Angenommen, man erstellt einen Algorithmus, der die Bitkomplexität auf anstatt auf Gesamtmultiplikationen und -additionen reduziert, könnte dies ein vernünftigerer Ansatz sein, als beispielsweise die Gesamtmultiplikationen und -additionen auf O ( n 2 + ϵ ) wie versucht zu reduzieren von Forschern wie Coppersmith und Cohn.$O(n^{3+\epsilon})$$O(n^{2+\epsilon})$

Ist das ein gültiges Argument?$(2)$

Nein, das Bit Komplexität der Matrixmultiplikation auf -Bit - Einträge ist n ω ( log n ) O ( 1 ) ⋅ M ( log M ) O ( 1 ) , wobei ω < 2.4 ist die bekannteste Matrixmultiplikation Exponenten. Die Multiplikation und Addition von M- Bit-Zahlen kann in M ( log M ) 2- Zeit erfolgen. Das Multiplizieren von zwei M- Bit-Zahlen ergibt eine Zahl, die nicht mehr als 2 $M$$n^{\omega} (\log n)^{O(1)} \cdot M (\log M)^{O(1)}$$\omega < 2.4$$M$$M (\log M)^2$$M$$2M$Bits. Das Addieren von Zahlen von jeweils M Bits ergibt eine Zahl, die nicht mehr als M + log n + O ( 1 ) Bits hat. (Denken Sie darüber nach: Die Summe beträgt höchstens n 2 M , sodass die Bitdarstellung nicht mehr als log ( n 2 M ) + O ( 1 ) Bits benötigt.)$n$$M$$M+\log n+O(1)$$n 2^M$$\log (n 2^M)+O(1)$

Verweise auf schnelle ganzzahlige Multiplikationsalgorithmen können mit einer Websuche oder Wikipedia gefunden werden.