Schonhage's algorithm (Matrix Multiplication Matrix Product): Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Time Complexity == $O(n^{({3}*log52/log110)}) ~ O(n^{2.{521}8})$ == Space Complexity == $O(n^{2})$ words (Derived: Same idea as Strassen's, plus three additional nxn matrices) == Description == == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/abs/10.1137/0210032") |
No edit summary |
||
Line 1: | Line 1: | ||
== Time Complexity == | == Time Complexity == | ||
$O(n^{({3}* | $O(n^{({3}*\log {52}/l \og {110})}) ~ O(n^{2.{521}8})$ | ||
== Space Complexity == | == Space Complexity == |
Latest revision as of 10:19, 28 April 2023
Time Complexity
$O(n^{({3}*\log {52}/l \og {110})}) ~ O(n^{2.{521}8})$
Space Complexity
$O(n^{2})$ words
(Derived: Same idea as Strassen's, plus three additional nxn matrices)
Description
Approximate?
Approximate
Approximation Factor: ?
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1980