Strassen algorithm for matrix multiplication (divide and conquer) - Inside code
HTML-код
- Опубликовано: 3 сен 2021
- Source code: gist.github.com/syphh/1cb6b9b...
🔴 Learn graph theory algorithms: inscod.com/graphalgo
⚙ Learn dynamic programming: inscod.com/dp_course
💡 Learn to solve popular coding interview problems: inscod.com/50problems_course
⌛ Learn time and space complexity analysis: inscod.com/complexity_course
🔁 Learn recursion: inscod.com/recursion_course
NB: This video is ad-free, you can choose to support Inside code by purchasing one of the courses above or dropping a super thanks!
NB2: Discounts of courses above are permanent
I also post content on LinkedIn (inscod.com/linkedin) and Instagram (inscod.com/instagram) - Наука
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 am a student in university, when the concept was explained by my professor seemed to be complicated, however you made it look easy with this understandable and informative video. Thank you, you gained a subscriber!!!!
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!
This is such a great video. Thank you so much, your animations are on par too. I'm a uni student, I just subscribed!
Don't stop making those kind of videos, good luck and thanks for this awesome way of explaining things.
Glad you like them!
Well explained algorithm. Best I've seen by far.
Having a test of this today, coming back for review, thanks for posting this, this is the best explanation so far.
You're welcome!
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...
What about non-square matrices? Do we set the rest of non-square matrices to zeroes or smth?
I enjoyed this video and the visualizations.
Bro you're a god at teaching wow
which software do you use to make such amazing lectures?
Thanks a lot. Much Obliged!
This is the best explination of strassen out there
Thanks!
Bro please make the video on
Prims, krushkal and dijkastra algorithm.....
So that we learn the algorithm
I'll recommend this channel to all of my classmates
Does Numpy use Strassen algorithm?
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
Much thank you!
Fantastic explanation 🥇
Thanks!
That was some extremely clean python code, damn.
Thanks!
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
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
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 :(
thanks brother
You're welcome!
do you have the code in c or c++?
Nope sorry but you can find it online, just write Strassen algorithm C or C++
cool, so it's like Karatsuba multiplication, but for 2d
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
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.
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
good video
Thanks a lot!