mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2019-07-29, 19:56   #1
neomacdev
 
Apr 2019

1616 Posts
Default 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
neomacdev is offline   Reply With Quote
Old 2019-07-30, 01:40   #2
tServo
 
tServo's Avatar
 
"Marv"
May 2009
near the Tannhäuser Gate

5·127 Posts
Default

Quote:
Originally Posted by neomacdev View Post
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
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.
tServo is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Possible better multiplication algorithm Triber Computer Science & Computational Number Theory 17 2015-11-10 17:48
Polynomial algorithm diep Factoring 7 2012-09-29 12:09
TF algorithm(s) davieddy Miscellaneous Math 61 2011-07-06 20:13
Schönhage-Strassen Algorithm Paper flouran Math 8 2009-05-23 23:52
New Multiplication Algorithm vector Miscellaneous Math 10 2007-12-20 18:16

All times are UTC. The time now is 01:41.

Sat May 8 01:41:56 UTC 2021 up 29 days, 20:22, 0 users, load averages: 1.41, 1.38, 1.39

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.