Die wahre Bitkomplexität der Matrixmultiplikation ist

9

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.Ö(n3)Ö(n3)mÖ(n3nm)=Ö(n4m)

Es scheint also, dass die wahre Komplexität der Matrixmultiplikation, gemessen über die Bitkomplexität, .Ö(n4)

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.Ö(n3+ϵ)Ö(n2+ϵ)

Ist das ein gültiges Argument?(2)

T ....
quelle

Antworten:

31

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 hatM.nω(Logn)Ö(1)M.(LogM.)Ö(1)ω<2.4M.M.(LogM.)2M.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.)nM.M.+Logn+Ö(1)n2M.Log(n2M.)+Ö(1)

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

Ryan Williams
quelle
Ich denke, mein Argument war fehlerhaft. Vielen Dank. Ich weiß das zu schätzen.
T ....