20190729, 19:56  #1 
Apr 2019
2×11 Posts 
Karatsuba algorithm relation to Matrix Multiplication (Strassen Algorithm)?
Hi,
This question is not Mersenne prime related, nor prime related at all. There is a series of optimized algorithms for Matrix Multiplication ala Strassen's Algorithm for performing 2x2 x 2x2 Matrix multiplication in only 7 scalar multiplications rather than the standard 8. And there is Karatsuba's algorithm for performing large integer multiplication which reduces the number of single digit multiplications from n^2 to n^1.58. I vaguely recall I saw a reference to a Mathematics paper that, if I recall correctly, stated for every Strassenlike accelerated matrix multiplication algorithm there was a corresponding accelerated integer multiplication algorithm like Karatsuba. Is anyone framiliar with this paper? Can you provide a citation or link? I have tried searching, but must not be using the correct terms as I can't locate it. Or perhaps I've imagined the entire thing! Thanks. For reference: Strassen's Algorithm https://en.wikipedia.org/wiki/Strassen_algorithm Karatsuba's Algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm 
20190730, 01:40  #2  
"Marv"
May 2009
near the Tannhäuser Gate
625_{10} Posts 
Quote:
It reduces 9 multiplies to 5. Wikipedia has a good article under the algorithm's full name: ToomCook. Also, check the link the article has to Marco Bodrato's web site. He has some good stuff. The freely available big integer system call LibTomMath has a Toom3 implementation also. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Possible better multiplication algorithm  Triber  Computer Science & Computational Number Theory  17  20151110 17:48 
Polynomial algorithm  diep  Factoring  7  20120929 12:09 
TF algorithm(s)  davieddy  Miscellaneous Math  61  20110706 20:13 
SchönhageStrassen Algorithm Paper  flouran  Math  8  20090523 23:52 
New Multiplication Algorithm  vector  Miscellaneous Math  10  20071220 18:16 