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)
  • НаукаНаука

Комментарии • 59

  • @insidecode
    @insidecode  Год назад +3

    Discover the new graph theory algorithms course: inscod.com/graphalgo
    🔴
    / \
    🔵-🔴
    | |
    🔴-🔵

  • @meli24
    @meli24 2 года назад +39

    10 times easier to understand it than my professor, who took 1 hour showing the paper that strassen published back then.
    Thank you !

  • @arestiskonstantinou985
    @arestiskonstantinou985 3 месяца назад +2

    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!!!!

  • @MrAdamo
    @MrAdamo 7 месяцев назад +2

    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!

  • @Sarah-re7cg
    @Sarah-re7cg 2 месяца назад +1

    This is such a great video. Thank you so much, your animations are on par too. I'm a uni student, I just subscribed!

  • @dntk2083
    @dntk2083 2 года назад +7

    Don't stop making those kind of videos, good luck and thanks for this awesome way of explaining things.

  • @oribenez
    @oribenez Год назад

    Well explained algorithm. Best I've seen by far.

  • @elriczeroful
    @elriczeroful 2 года назад +4

    Having a test of this today, coming back for review, thanks for posting this, this is the best explanation so far.

  • @raziehahmadi4185
    @raziehahmadi4185 2 года назад

    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...

  • @nullbeyondo
    @nullbeyondo 2 года назад +1

    What about non-square matrices? Do we set the rest of non-square matrices to zeroes or smth?

  • @Nerdimo
    @Nerdimo 7 месяцев назад

    I enjoyed this video and the visualizations.

  • @user-rf4vc7mt4d
    @user-rf4vc7mt4d 10 месяцев назад +1

    Bro you're a god at teaching wow

  • @YugamAggarwal
    @YugamAggarwal 9 месяцев назад

    which software do you use to make such amazing lectures?

  • @AK-bl8gl
    @AK-bl8gl Год назад

    Thanks a lot. Much Obliged!

  • @franssjostrom719
    @franssjostrom719 Год назад

    This is the best explination of strassen out there

  • @ranjan502
    @ranjan502 2 года назад +1

    Bro please make the video on
    Prims, krushkal and dijkastra algorithm.....
    So that we learn the algorithm

  • @omerfeyyazselcuk7325
    @omerfeyyazselcuk7325 Год назад

    I'll recommend this channel to all of my classmates

  • @iam.damian
    @iam.damian Год назад +1

    Does Numpy use Strassen algorithm?

  • @user-ui6bq9wd7m
    @user-ui6bq9wd7m Год назад

    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)?

    • @insidecode
      @insidecode  Год назад

      Because adding two matrices requires traversing all elements and a matrix of size n by n has n² elements

  • @BasharIdrees
    @BasharIdrees Год назад

    Much thank you!

  • @annawolarz7136
    @annawolarz7136 2 года назад +1

    Fantastic explanation 🥇

  • @hotpushupguy4203
    @hotpushupguy4203 2 года назад +2

    That was some extremely clean python code, damn.

  • @zardouayassir7359
    @zardouayassir7359 2 года назад +1

    Hi, is this the best method (assuming that I'm multiplying non squared matrices containing random values)? Thanks for the video.

    • @insidecode
      @insidecode  2 года назад

      if n is big enough yes

    • @weiiswurst
      @weiiswurst 2 года назад

      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

  • @ChristopherCricketWallace
    @ChristopherCricketWallace 2 года назад +8

    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.

    • @insidecode
      @insidecode  2 года назад

      I don't think that these algorithms are asked in an interview, but they're good to know

    • @zakthesquirrel7621
      @zakthesquirrel7621 8 месяцев назад

      what kind of algorithms can be asked in an interview, please ?@@insidecode

  • @elliebartlett
    @elliebartlett 2 года назад

    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
      @insidecode  2 года назад

      yes because the code works with numpy arrays not normal lists

    • @elliebartlett
      @elliebartlett 2 года назад

      @@insidecode I used numpy arrays for my input matrices though

    • @insidecode
      @insidecode  2 года назад

      Weird, I'll try the code when I get home and I'll see

    • @insidecode
      @insidecode  2 года назад +1

      @@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))

    • @elliebartlett
      @elliebartlett 2 года назад

      @@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 :(

  • @44_rahulboddupally24
    @44_rahulboddupally24 2 года назад

    thanks brother

  • @PrabhatK29
    @PrabhatK29 2 года назад +1

    do you have the code in c or c++?

    • @insidecode
      @insidecode  2 года назад

      Nope sorry but you can find it online, just write Strassen algorithm C or C++

  • @NoNameAtAll2
    @NoNameAtAll2 2 года назад

    cool, so it's like Karatsuba multiplication, but for 2d

  • @aryan7069_
    @aryan7069_ 2 года назад +2

    4:53 i think strassen would be strassen2

    • @insidecode
      @insidecode  2 года назад +1

      The function name should be strassen not strassen2, I just forgot to remove the 2 my bad

  • @AcTheMace
    @AcTheMace Год назад

    awesome. so now I just have to do all this in C++ ...

    • @insidecode
      @insidecode  Год назад

      How did it go? Did you succeed?

    • @AcTheMace
      @AcTheMace Год назад

      @@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.

    • @AcTheMace
      @AcTheMace Год назад

      @@insidecode Sorry to disappoint XD

    • @insidecode
      @insidecode  Год назад

      No problem, by the way I made 2 convex hull videos, you can check them

    • @AcTheMace
      @AcTheMace Год назад

      @@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.

  • @user-gs7ro3tl9t
    @user-gs7ro3tl9t Год назад

    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

    • @user-gs7ro3tl9t
      @user-gs7ro3tl9t Год назад

      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()

    • @insidecode
      @insidecode  Год назад +1

      Hello, yes we use numpy not Python lists

  • @aryan7069_
    @aryan7069_ 2 года назад

    good video