Stack Overflow
Stack Overflow

Questions tagged [strassen]

Set of algorithms (co)created by Volker Strassen for speeding up number (Schönhage–Strassen algorithm) and matrix (Strassen Algorithm) multiplications.

Strassen Algorithm

  • it subdivides square matrices to 4 quadrants
  • and handle them in way similar to Karatsuba multiplication
  • it is only slightly faster then standard matrix multiplication (and only for big matrices)

Schönhage–Strassen algorithm

  • it uses FFT/NTT convolution (of digits) to compute number multiplication
  • it is fast only for very big numbers
  • it handle number as polynomial of digits and digit base

Homepage: http://www.math.uni-konstanz.de/~strassen

73 questions
30
votes
3 answers

Strassen's algorithm for matrix multiplication

Can someone please explain strassen's algorithm for matrix multiplication in an intuitive way? I've gone through (well, tried to go through) the explanation in the book and wiki but it's not clicking upstairs. Any links on the web that use a lot of…
confused_by_strassen
  • 301
  • 1
  • 3
  • 3
20
votes
4 answers

Why is Strassen matrix multiplication so much slower than standard matrix multiplication?

I have written programs in C++, Python and Java for matrix multiplication and tested their speed for multiplying two 2000 x 2000 matrices (see post). The standard ikj-implentation - which is in - took: C++: 15 seconds (Source) Python: 6 minutes 13…
Martin Thoma
  • 124,992
  • 159
  • 614
  • 958
16
votes
4 answers

How to split a matrix into 4 blocks using numpy?

I'm implementing Strassen's Matrix Multiplication using python. In divide step, we divide a larger matrix into smaller sub-matrices. Is there a built-in numpy function to split a matrix?
shobhu
  • 694
  • 2
  • 7
  • 16
14
votes
2 answers

Why is my Strassen's Matrix Multiplication slow?

I wrote two Matrix Multiplications programs in C++: Regular MM (source), and Strassen's MM (source), both of which operate on square matrices of sizes 2^k x 2^k(in other words, square matrices of even size). Results are just terrible. For 1024 x…
newprint
  • 6,936
  • 13
  • 67
  • 109
7
votes
1 answer

Boolean matrix multiplication algorithm

This is my first question on stackoverflow. I've been solving some exercises from "Algorithm design" by Goodrich, Tamassia. However, I'm quite clueless about this problem. Unusre where to start from and how to proceed. Any advice would be great.…
user4452139
4
votes
2 answers

How to use this C code to multiply two matrices using Strassen's algorithm?

I was looking for an implementation of Strassen's Algorithm in C, and I've found this code at the end. To use the multiply function: void multiply(int n, matrix a, matrix b, matrix c, matrix d); which multiplies two matrices a, b and puts the…
ob_dev
  • 2,808
  • 1
  • 20
  • 26
4
votes
3 answers

Strassen algorithm not the fastest?

I copied strassen's algorithm from somewhere and then executed it. Here is the output n = 256 classical took 360ms strassen 1 took 33609ms strassen2 took 1172ms classical took 437ms strassen 1 took 32891ms strassen2 took 1156ms classical took…
Lokesh Khandelwal
  • 41
  • 1
  • 2
4
votes
5 answers

Matrix multiplication: Strassen vs. Standard

I tried to implement the Strassen algorithm for matrix multiplication with C++, but the result isn't that, what I expected. As you can see strassen always takes more time then standard implementation and only with a dimension from a power of 2 is as…
multiholle
  • 3,050
  • 8
  • 41
  • 60
4
votes
2 answers

Product of two complex numbers in less than 3 multiplications

Can someone break this down for me? Why can't it be done in two multiplications? The Multiplication of Complex Numbers If the number of multiplications required for a computation is regarded as a measure of its difficulty and these computations are…
SuperCell
  • 241
  • 1
  • 12
4
votes
1 answer

Can Strassen algorithm be used for Boolean matrix multiplication?

I am wondering if Strassen's algorithm can be used for Boolean matrix multiplication? I know that it is used for regular matrix multiplication but not too sure about Boolean. Also, if it can be, is it faster asymptotically than using Four Russians…
Gana
  • 75
  • 1
  • 7
4
votes
1 answer

In-place implementation of Strassen algorithm?

I managed to implement an in-place solution though index manipulations for naive Divide & Conquer algorithm for matrix multiplication which requires 8 recursive calls in each recurrence. However, when trying to implement Strassen algorithm, I…
Xing Hu
  • 128
  • 10
3
votes
2 answers

optimized static padding for strassen's odd matrices

I'm trying to address the issue of odd matrices for strassen's algorithm. My implementation truncates the recursion at a certain point, call it Q, and switches over to the standard implementation. Therefore in doing static padding, I don't actually…
Yiren Lu
  • 153
  • 3
  • 13
3
votes
3 answers

Crossover Point: Strassen's Algorithm

What is the optimal crossover point under which Strassen's Algorithm should stop the recursion and apply the multiplication, in terms of efficiency? I know this is closely connected to the specific implementation and hardware but there should be…
kxk
  • 576
  • 2
  • 11
  • 30
3
votes
1 answer

Strassen-Winograd Algorithm

I got a task to write a Strassen-Winograd algorithm in C++. I have written it twice, but the first version of my code doesn't work. The result is correct in the lower left corner of result matrix. And my second version is running slower than naive…
NoActualName
  • 71
  • 9
3
votes
3 answers

What's wrong with Strassen's method to compute square of a matrix?

Using the same approach as of Strassen's only 5 multiplications are sufficient to compute square of a matrix. If A[2][2] = [a, b, c, d], the multiplications are a * a, d * d, b * (a + d), c * (a + d), b * c. If we generalise this algorithm for…
77H3jjuu
  • 346
  • 3
  • 10
1
2 3 4 5