You explain wonderfully, thank you very much. I wanted to ask - something I couldn't understand anywhere else. Why are the subsequent addition operations of the submatrices O(n^2)?
It's not just O(n^3) because of 3 for loops. I have done it in 2, but the total amount of *multiplications* (which is the slow part of these calculations) remained the same. It's always n*n^2 multiplications and (n-1)*n^2 additions. The probelm I see with this algorithm is that you remove 1 multiplication but you have to call hundreds of recursions (for a practically sized matrix, like idk 1000*1000) and you must have square matrices or pad them with 1s.... in terms of code this algorithm will be slower than regular multiplication simply because all these recursions will take time just to even be called and returned.
For sufficiently large matrices (1mil x 1mil - Matrices and beyond), newer algorithms with O(n^2.34) were found These are only worth using on really big matrices though because they have big constant factors in their time complexity that the big O notation does not show. In general, just use the method from numpy
I tried to run the code and it doesn’t work for me. It says TypeError: unsupported operand type(s) for -: 'list' and 'list' for the p1 + p2 - p3 + p4 part
@@insidecode hi thanks for checking, I tried it again with your exact inputs and I’m still getting the same error. I can’t see a difference in my code and yours though, so don’t know what’s happening :(
@@insidecode Haha, so I actually switched my projects to a Vertex Cover and Convex Hull algorithms. I thought they'd be easier and more interesting to present than this would be.
@@insidecode Oh yeah, turns out those were the first ones I watched when looking at the algorithm a few weeks ago. I should link my results when I'm done.
Hello professor, There is a wrong & I get an error: TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType' why?? return of function is None Type and can not support operand... please help me...
Thanks for the great explanation! But code doesn't work with Python 3.11. ------------------------------------------ Error in Python 3.11 line 14, in split return matrix[:n // 2, :n // 2], matrix[:n // 2, n // 2:], matrix[n // 2:, :n // 2], matrix[n // 2:, n // 2:] TypeError: list indices must be integers or slices, not tuple
Discover the new graph theory algorithms course: inscod.com/graphalgo
🔴
/ \
🔵-🔴
| |
🔴-🔵
10 times easier to understand it than my professor, who took 1 hour showing the paper that strassen published back then.
Thank you !
You're welcome!
I had an "aha" moment at about 3:40. I didn't really get the divide/conquer stuff until I saw your visuals. Thank you!
Don't stop making those kind of videos, good luck and thanks for this awesome way of explaining things.
Glad you like them!
Having a test of this today, coming back for review, thanks for posting this, this is the best explanation so far.
You're welcome!
I'll recommend this channel to all of my classmates
This is such a great video. Thank you so much, your animations are on par too. I'm a uni student, I just subscribed!
Bro you're a god at teaching wow
Well explained algorithm. Best I've seen by far.
That was some extremely clean python code, damn.
Thanks!
I'll be honest, I understood all of that; but I don't think I could do it on my own--especially not in an interview.
I don't think that these algorithms are asked in an interview, but they're good to know
what kind of algorithms can be asked in an interview, please ?@@insidecode
Does Numpy use Strassen algorithm?
very well explained 👏👏
I enjoyed this video and the visualizations.
Bro please make the video on
Prims, krushkal and dijkastra algorithm.....
So that we learn the algorithm
This is the best explination of strassen out there
Thanks!
which software do you use to make such amazing lectures?
What about non-square matrices? Do we set the rest of non-square matrices to zeroes or smth?
Fantastic explanation 🥇
Thanks!
You explain wonderfully, thank you very much.
I wanted to ask - something I couldn't understand anywhere else.
Why are the subsequent addition operations of the submatrices O(n^2)?
Because adding two matrices requires traversing all elements and a matrix of size n by n has n² elements
1:02 Last multiplication should be 3 * 6 ;)
Nevertheless video is great!
Now we can all enjoy video games with 4k graphics and 144hz refresh rate because of this awesome algorithm 🎮 🎮 🎮 🎮
It's not just O(n^3) because of 3 for loops. I have done it in 2, but the total amount of *multiplications* (which is the slow part of these calculations) remained the same. It's always n*n^2 multiplications and (n-1)*n^2 additions.
The probelm I see with this algorithm is that you remove 1 multiplication but you have to call hundreds of recursions (for a practically sized matrix, like idk 1000*1000) and you must have square matrices or pad them with 1s.... in terms of code this algorithm will be slower than regular multiplication simply because all these recursions will take time just to even be called and returned.
Hi, is this the best method (assuming that I'm multiplying non squared matrices containing random values)? Thanks for the video.
if n is big enough yes
For sufficiently large matrices (1mil x 1mil - Matrices and beyond), newer algorithms with O(n^2.34) were found
These are only worth using on really big matrices though because they have big constant factors in their time complexity that the big O notation does not show.
In general, just use the method from numpy
Thanks a lot. Much Obliged!
do you have the code in c or c++?
Nope sorry but you can find it online, just write Strassen algorithm C or C++
4:53 i think strassen would be strassen2
The function name should be strassen not strassen2, I just forgot to remove the 2 my bad
Much thank you!
I tried to run the code and it doesn’t work for me. It says TypeError: unsupported operand type(s) for -: 'list' and 'list' for the p1 + p2 - p3 + p4 part
yes because the code works with numpy arrays not normal lists
@@insidecode I used numpy arrays for my input matrices though
Weird, I'll try the code when I get home and I'll see
@@elliebartlett Update: I tried the code and it worked perfectly, I wrote as input
m1 = np.array([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
m2 = np.array([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
print(strassen(m1, m2))
@@insidecode hi thanks for checking, I tried it again with your exact inputs and I’m still getting the same error. I can’t see a difference in my code and yours though, so don’t know what’s happening :(
awesome. so now I just have to do all this in C++ ...
How did it go? Did you succeed?
@@insidecode Haha, so I actually switched my projects to a Vertex Cover and Convex Hull algorithms. I thought they'd be easier and more interesting to present than this would be.
@@insidecode Sorry to disappoint XD
No problem, by the way I made 2 convex hull videos, you can check them
@@insidecode Oh yeah, turns out those were the first ones I watched when looking at the algorithm a few weeks ago.
I should link my results when I'm done.
Hello professor, There is a wrong & I get an error: TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'
why?? return of function is None Type and can not support operand...
please help me...
cool, so it's like Karatsuba multiplication, but for 2d
Thanks for the great explanation!
But code doesn't work with Python 3.11.
------------------------------------------
Error in Python 3.11
line 14, in split
return matrix[:n // 2, :n // 2], matrix[:n // 2, n // 2:], matrix[n // 2:, :n // 2], matrix[n // 2:, n // 2:]
TypeError: list indices must be integers or slices, not tuple
Fixed in tests due to numpy.
-----------------------
import unittest
from ..strassen_with_numpy import strassen_with_numpy
import numpy as np
class MyTestCase(unittest.TestCase):
def test_strassen(self):
matrix_a = np.array([
[3, 5, 1, 3],
[1, 2, 3, 4],
[4, 5, 6, 8],
[7, 8, 9, 3]
])
matrix_b = np.array([
[4, 1, 2, 3],
[1, 2, 1, 6],
[2, 4, 6, 2],
[6, 2, 5, 4]
])
matrix_result = np.array([
[37, 23, 32, 53],
[36, 25, 42, 37],
[81, 54, 89, 86],
[72, 65, 91, 99]
])
# stackoverflow.com/questions/3302949/best-way-to-assert-for-numpy-array-equality
np.testing.assert_array_equal(strassen_with_numpy(matrix_a, matrix_b), matrix_result)
if __name__ == '__main__':
unittest.main()
Hello, yes we use numpy not Python lists
thanks brother
You're welcome!
good video
Thanks a lot!