patternMinor
Common idea in Karatsuba, Gauss and Strassen multiplication
Viewed 0 times
ideakaratsubastrassenmultiplicationgaussandcommon
Problem
The identities used in multiplication algorithms by
-
Karatsuba (integers)
-
Gauss (complex numbers)
-
Strassen (matrices)
seem very closely related. Is there a common abstract framework/generalization?
-
Karatsuba (integers)
-
Gauss (complex numbers)
-
Strassen (matrices)
seem very closely related. Is there a common abstract framework/generalization?
Solution
A partial answer to your question is the group-theoretic approach first developed by Cohn and Umans and further developed by Cohn, Kleinberg, Szegedy and Umans. It can "sort of" capture Strassen and Coppersmith-Winograd for matrix multiplication.
Context
StackExchange Computer Science Q#1901, answer score: 8
Revisions (0)
No revisions yet.