Strassen’s Matrix Multiplication | Divide and Conquer | GeeksforGeeks

  Рет қаралды 181,849

GeeksforGeeks

GeeksforGeeks

Күн бұрын

Find Complete Code at GeeksforGeeks Article: www.geeksforgeeks.org/strassen...
This video is contributed by Harshit Verma
Please Like, Comment and Share the Video among your friends.
Also, Subscribe if you haven't already! :)

Пікірлер: 55
@nebras__
@nebras__ 5 жыл бұрын
thank you .. my left ear loved the video
@brianevans4
@brianevans4 4 жыл бұрын
Your headphones are on the wrong way. It should be your right ear
@chengyaozheng8536
@chengyaozheng8536 4 жыл бұрын
@@brianevans4 Doesn't matter, it flows out from the other ear anyways.
@ashujha9165
@ashujha9165 4 жыл бұрын
BRO THIS VIDEO'S AUDIO IS LIKE 3D AUDIO.
@siddhvyas6330
@siddhvyas6330 3 жыл бұрын
hahahaha
@ayushiojha6376
@ayushiojha6376 2 жыл бұрын
Right😂
@soumitramehrotra2045
@soumitramehrotra2045 4 жыл бұрын
where is the addition of matrices comes into the picture as you say ut takes O(N^2) for addition?
@manojprajapati932
@manojprajapati932 5 жыл бұрын
Strassen’s Matrix Multiplication looks incorrect. The correct algorithm is here en.wikipedia.org/wiki/Strassen_algorithm
@muskanrai2282
@muskanrai2282 6 жыл бұрын
Good job 👍 sir
@nazishschughtai5712
@nazishschughtai5712 3 жыл бұрын
amazing video.. thanks
@arushiraj8607
@arushiraj8607 2 жыл бұрын
thanks😊, very helpful.
@Nellak2011
@Nellak2011 4 жыл бұрын
Turns out, the optimal amount of operations in the optimal algorithm would perform only 4 operations instead of Strassen's 7. Because, the optimal algorithm would run in O(n^2) time
@bonbonpony
@bonbonpony 3 жыл бұрын
What lead you to this conclusion? Just because the resulting matrix has 4 cells, doesn't mean that this is the minimal number of multiplications required, because you still need some way to combine 8 cells coming from 2 factor matrices somehow. And they are combined as dot products. The only thing you can do is to reshape their formulas in such a way that would lower the number of multiplications (at the cost of increasing the number of additions - those are usually less expensive to calculate), by reusing some partial results.
@solsane5217
@solsane5217 2 жыл бұрын
If you could implement a sequential O(n^2) matrix multiplication algo you'd get a Nobel prize.
@saifhaider2310
@saifhaider2310 7 жыл бұрын
what if matrix is oddxodd i.e if 7x7 then how to devide into 4 matrix
@erick9016
@erick9016 6 жыл бұрын
you convert them into 8x8 by adding a row & column of just zeroes. Everything else works identically
@googol-boy-data
@googol-boy-data 6 жыл бұрын
It's necessary, because Strassen algorithm can only be done on 2^n x 2^n matrix
@shivatejachavali787
@shivatejachavali787 4 жыл бұрын
@@googol-boy-data nice
@keshavmaheshwari521
@keshavmaheshwari521 3 жыл бұрын
why is it not preferred for practical purposes
@cvismenu
@cvismenu 4 жыл бұрын
Thank you
@ankitvashisht7350
@ankitvashisht7350 5 жыл бұрын
why strassen's method is not preferred for practical purposes ?
@anshul4249
@anshul4249 4 жыл бұрын
Most probably because we would prefer small calculations several times rather than large calculations.....
@vishalkumarsingh5509
@vishalkumarsingh5509 Жыл бұрын
Because it only works for square matrixes
@KeshaShah1106
@KeshaShah1106 7 жыл бұрын
how do u come up with p1 to p7 formula?
@harshitv
@harshitv 7 жыл бұрын
That is Strassen's formula. All you can do is memorise it. See here: www.geeksforgeeks.org/easy-way-remember-strassens-matrix-equation/
@frozenarmymc2182
@frozenarmymc2182 5 жыл бұрын
It’s just an invention, some found it and it worked
@asoahmadzade4305
@asoahmadzade4305 2 жыл бұрын
nice job
@unboxer6226
@unboxer6226 5 жыл бұрын
not useful,just reading the ppt
@sanjayjeyavel9871
@sanjayjeyavel9871 7 жыл бұрын
It would have been even more useful if u had explained the implementation of the algo!!! nice video though!
@chiefjudge8456
@chiefjudge8456 6 жыл бұрын
You didn't explain the method. You also wrote lg7 (or log_2 7) as log 7 which is confusing.
@shushrutgupta
@shushrutgupta 5 жыл бұрын
If your ever read Introduction to Algorithms by Cormen, you will notice that, log_2(n) is written as lg n and log_e(n) is written as ln n
@DeepakKumar-wv7jg
@DeepakKumar-wv7jg 5 жыл бұрын
Rtaaaa maarrr
@khorshidvahidi
@khorshidvahidi 5 жыл бұрын
In computer science, any log is assumed to have base 2 unless specified otherwise
@brianevans4
@brianevans4 4 жыл бұрын
I think generally speaking log(n) is assumed to be log base 10 of n
@bonbonpony
@bonbonpony 3 жыл бұрын
@@brianevans4 Unfortunately, it depends on the country/school/book. Different authors use different notations (as if there wasn't enough confusion already :q ).
@cahitskttaramal3152
@cahitskttaramal3152 3 жыл бұрын
This was a bad explanation. I mean why bother if you won't go deep and explain the theory behind it in the video? I found this whole info and understand in 20 seconds on google before watch this. No need to watch 4.5 mins video for this. Man I hate to dislike informative videos on KZfaq but sometimes they really push!
@bonbonpony
@bonbonpony 3 жыл бұрын
As they say, for every Wikipedia page, there's an Indian video on KZfaq trying to tell you the same with pseudo-English.
@kartikanand6348
@kartikanand6348 3 жыл бұрын
@@bonbonpony I mean, I'm an Indian, but lol, that's to the point XD
@poojapoojadhapte1430
@poojapoojadhapte1430 10 ай бұрын
Matrix multiplication algorithm
@drwhackadoodle360
@drwhackadoodle360 4 жыл бұрын
This isn't explained properly at all
@bonbonpony
@bonbonpony 3 жыл бұрын
You should have expected that from the beginning after hearing Indian accent, shouldn't you? :q
@ronakpatil6081
@ronakpatil6081 3 жыл бұрын
@@bonbonpony so ,instead watch abdul bari another indian with great explanation of the algorithm it would help you definitely then you will not have any problem with indian accent😂
@bonbonpony
@bonbonpony 3 жыл бұрын
@@ronakpatil6081 I don't have a problem with Indian accent. (In fact, I watched quite a lot of Indian video lectures from NPTEL etc.). I have a problem with Indian people who think that they understand something and they can teach about it, and then flooding KZfaq with crappy videos recorded with a cucumber, with traffic noises in the background, and "explaining" to me with their poor unintelligible English the stuff that I could just read from Wikipedia. Or worse, making videos in Hindi but putting English titles to deceive English-speaking people into watching them.
@DeepakKumar-wv7jg
@DeepakKumar-wv7jg 5 жыл бұрын
Saaale ka bol rha hai khud ki pta hau
@shashankvashishtha4454
@shashankvashishtha4454 3 ай бұрын
could not understand
@rishabhraj865
@rishabhraj865 4 жыл бұрын
have you ever hear about Abdul Bari, go get some skill how to teach..
@kemal4282
@kemal4282 5 жыл бұрын
can u guys stop speaking like hindi while speaking english
@Nikhil-pm6rn
@Nikhil-pm6rn 4 жыл бұрын
can you guys stop speaking in english
@shivatejachavali787
@shivatejachavali787 4 жыл бұрын
sad reacts only
@vishnuramj4660
@vishnuramj4660 3 жыл бұрын
@@Nikhil-pm6rn hindi theriyadhu poda
@Nikhil-pm6rn
@Nikhil-pm6rn 3 жыл бұрын
@@vishnuramj4660 OK bro, I will start a channel just for you and tamilians.
@bonbonpony
@bonbonpony 3 жыл бұрын
@@Nikhil-pm6rn There should be an entire separate KZfaq for them, so that they didn't have to spam the regular KZfaq with their crappy unintelligible videos about every single subject on Earth.
2.9 Strassens Matrix Multiplication
23:40
Abdul Bari
Рет қаралды 1 МЛН
The delivery rescued them
00:52
Mamasoboliha
Рет қаралды 9 МЛН
Каха инструкция по шашлыку
01:00
К-Media
Рет қаралды 7 МЛН
WHY IS A CAR MORE EXPENSIVE THAN A GIRL?
00:37
Levsob
Рет қаралды 19 МЛН
How AI Discovered a Faster Matrix Multiplication Algorithm
13:00
Quanta Magazine
Рет қаралды 1,4 МЛН
Closest Pair of Points (Divide and Conquer) Explained
8:45
The fastest matrix multiplication algorithm
11:28
Dr. Trefor Bazett
Рет қаралды 281 М.
Karatsuba Algorithm Explained with Examples
13:57
Engineering Prof.
Рет қаралды 33 М.
3. Greedy Method -  Introduction
12:02
Abdul Bari
Рет қаралды 1,4 МЛН