mersenneforum.org - View Single Post - Karatsuba algorithm relation to Matrix Multiplication (Strassen Algorithm)?

neomacdev · 2019-07-29, 19:56

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
https://en.wikipedia.org/wiki/Strassen_algorithm

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

2019-07-29, 19:56	#1
neomacdev Apr 2019 26₈ 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 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 https://en.wikipedia.org/wiki/Strassen_algorithm Karatsuba's Algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm