Transcript:
Calculate the element-wise outer product of two matrices a and B. So the result should be a ten by three by five array where the first sub-matrix should look like this because it’s the outer product of the first row in a with the first row in B. [MUSIC] Alright. So if you did some googling for this problem, you may have stumbled across this stack overflow post, which is completely where I got this problem from and I have three solutions, but the first two solutions I give total credit to D Varchar. Hopefully I’m not butchering that name too badly. But he came up with two very elegant solutions, and then I have a third solution as well. So I kind of have those solutions organized like this, which I will copy and paste, and then I’m just going to talk about the basic strategy for each of these guys. So the first one uses broadcasting and a initially is a 10 by 3 array, so you can see that here and so if we do a square brackets and then ellipses, this is equivalent to saying a square brackets colon comma colon, but it’s sort of like shorthand notation, comma, none. Well, that’s going to insert a new last axis into a and it’s going to convert it into a 10 by 3 by 1 array and then B is a 10 by 5 array, but we give it a new second axis, so we convert it from a 10 by 5 array into a 10 by 1 by 5 array, and then when we do this multiplication between this modified version of a and B, you can imagine that a the 10 by three array A gets copied five times along the last axis to conform to B, which gets copied three times along its second axis. So if you just pick out a single row, let’s say like the first row here. This guy gets copied five times along the last axis and this guy here gets copied three times along the second axis and those get multiplied and that produces the outer product of the first element of a and B. And so hopefully you can kind of see how this works out to produce an element-wise outer product. Now the second solution here uses an Einstein sum and I like to write these out in pseudocode, so the subscripts, I and J correspond to the rows and columns of a the subscripts, I and K correspond to the rows and columns of B and the subscripts. I J and K correspond to the, uh, the indices or the axes of the output. So what I’ll say in pseudocode you could write this out as initialize output as an array of zeros with shape. Well, I is going to span 10 different rows of a so 10 J is going to span the three columns of a so it’s a 10 by 3 and then K here is going to span the five columns of B, so we initialize an array of zeros with shape ten by three by five, and then we iterate over each unique subscript, so we say for I for J for K. And then we set output underscore IJK so the IJK element of the output we set that as plus equals A I J Times b ik and I realize this is probably a little confusing, but if you just take the time to work this out in your head and maybe fix I to some particular row of a and B, you can see that this is indeed the outer product of a and B and then the last solution, which is the one that I came up with is to use the as strided function where basically, if you think about the output and let’s think about a particular element of the output, So well say, you know, output. I j k well. This is equal to some element of a times some element of B and so if you imagine we can reshape a into a an array that is the same shape as the output, so we want to reshape a into a 10 by a 3 by 5 array and we want to reshape B into a 10 by 3 by 5 array, then output. I j k. We can say is equal to a I j. K times B. I j k. So that’s really the strategy to this solution and the function as strided. If we pass in the correct parameters, we can create a view of a where the IJK element of a points to the correct element of a that we would want to multiply with the corresponding element of B to get to the corresponding output element, and so since these are not actually a and B, they’re views of a and B, We’ll call this a S and Bs and their product will give us the element wise outer product So hopefully that wasn’t too confusing. I didn’t want to go into too much depth because I talk about each of these topics in the course. And if you’re confused on any one of these, you can go back and look at the details in the course, but one last thing, so if we want to just see these in action, it’s kind of interesting to think about which one of these solutions would be fastest, so we can use the magic command percent time it and then do something like, so I’ll say op1 for outer product. One equals, uh, outer prod broadcasting a comma B and we can see how long this takes, and then we can do the same thing for the iron sum. [MUSIC] And for the, uh, stride trick version and you can see that the broadcasting and the Einstein sum are basically equivalent. This one’s a little bit faster. It seems, but they’re more or less the same, and then the stride trick is actually significantly slower. So, uh, tip your hat to devarkar, who came up with those really good solutions.