mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   Karatsuba algorithm relation to Matrix Multiplication (Strassen Algorithm)? (https://www.mersenneforum.org/showthread.php?t=24634)

neomacdev 2019-07-29 19:56

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 Strassen-like 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
[url]https://en.wikipedia.org/wiki/Strassen_algorithm[/url]

Karatsuba's Algorithm
[url]https://en.wikipedia.org/wiki/Karatsuba_algorithm[/url]

tServo 2019-07-30 01:40

[QUOTE=neomacdev;522538]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 Strassen-like 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
[url]https://en.wikipedia.org/wiki/Strassen_algorithm[/url]

Karatsuba's Algorithm
[url]https://en.wikipedia.org/wiki/Karatsuba_algorithm[/url][/QUOTE]

I'm not sure about the paper to which you refer but have you looked at Toom-3?
It reduces 9 multiplies to 5.
Wikipedia has a good article under the algorithm's full name: Toom-Cook.
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 Toom-3 implementation also.


All times are UTC. The time now is 06:04.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.