answer, that the running time of the straightforward [inaudible] algorithm runs in cubic time relative to the matrix dimension n.
To see this let's just recall what the definition of the matrix multiplication was.
The definition tells us each entry zij of the output matrix z is defined as the sum from k=1 to n of.
Xik times YKJ.
That is the [inaudible] product of the [inaudible] row of the X matric and the J column of the Y matrix.
Certainly assuming that we have the matrices represented in a way that we can access a given entry in constant time.
And under that assumption, remember each of these, each of these products.
Only takes constant time.
And so then to compute ZIJ we just have to add up these end products.
So that's gonna be theta of N time to compute a given ZIJ and then there's an N squared [inaudible] that we have to compute.
There's N choices for I, N choices for J, so that gives us N squared times N or cubic running time overall for the natural algorithm, which is really just a triple for-loop which computes each entry of the output ray separately using the dot product.
So the question as always for the keen algorithm designer is.
Can we do better? Can we beat, in cube time, by multiplying two matrices? And we might be especially emboldened with the progress that we've already seen in terms of multiplying two integers.
We apply the divide and conquer algorithm, to problem multiplying two end digit integers.
And we had, both a naive recursive algorithm, and a seemingly better.
Algorithm due to [inaudible], which made only three recursive calls.
Now we haven't yet analyzed the running time of that algorithm.
But as we'll see later, that does indeed beat the quadratic running time of the grade school algorithm.
So it's very natural to ask, can we do exactly the same thing here? There's the obvious [inaudible] algorithm, which follow straight from the definition.
Perhaps analogous to [inaudible], we could have some clever divide and conquer method, which beats cubic times.
So that's what we're gonna explore next.
[sound].
Let's recall the divide and conquer paradigm, what does it mean to use it.
Well, we first have to identify smaller problems.
So if we want to multiply by two NxN matricies we have to identify multiplications of smaller matricies that we can solve recursively.
Once we've figured out how we want to divide the given problem into smaller ones, then in the conquer step we simply invoke our own algorithm recursively that's going to recursively multiply the smaller matricies together.
And then, in general, we'll have to combine the results of the recursive calls to get the solution for the original problem, in our case, to get the product of the original two matricies.
From the product of what ever sub matrices we identify.
So how would be apply the divide and conquer paradigm to matrices? So we're given two N by N matrices, and we have to somehow identify smaller pairs of square matrices that we can multiply recursively.
So the idea, I think, is fairly natural.
So we start with a big N by N matrix X.
And so those N rows and N columns, we have to somehow divide into smaller pieces.
Now, the first thing you might think about is that you put it in its left half and its right half and now it goes into what we've been doing with the rays, but then we're going to break X into two matrices which are no longer squared which are N over two in one dimension and have length N in the other dimension and we want to recursively call a subroutine that multiplies square matrices.
So what seems like the clear thing to do is to divide X into quadrants.
Okay, so we have four pieces of X.
Each is gonna be N over two by N over two, corresponding to the different quarters of this matrix.
So let's call these different quadrants or blocks, in matrix terminology, A, B, C, and D.
All of these are N over two by N over two matrices.
As usual, for simplicity, I'm assuming that N is even, and as usual, it doesn't really matter.
And we can do the same trick with Y.
So we'll divide Y into quadrants.
And number two by N number two matrices which we'll call E, F, G and H.
So one thing that's cool about matrices, is when you split them into blocks, and you multiply them, the blocks just behave as if they were atomic elements.
So what I mean by that is that the product of X and Y can be expressed in terms of its quadrants and each of its four quadrants, each of its four corners can be written as a suitable arithmetic expression of the quadrants of X and Y.
So here's exactly what those formulas are.
They are exactly analogous to when we just multiplied pair of two by two matrices.
So I'm not going to formally prove this fact.
I'm sure many of you, have seen it before or are familiar with it.
And if you haven't, it's actually quite easy to prove.
It's not obvious, you can't see it off the top of your head, necessarily.
But if you go back to the definition, it's quite easy to verify.
The D, when you multiple X and Y, you can express as quadrants to blocks, in terms of the blocks of X and Y.
So what we just did is completely analogous to when talking about integer multiplication and you wanted to multiply two integers, little x and little y, and we broke them into pairs of N over two digits.
And then we just took the expansion and we observed how that expansion could be written in terms of products of N over two digit numbers.
Same thing going on here except with matrices.
So now, we're in business, as far as a recursive approach.
We wanna multiply X and Y.
They're N by N matrices.
We recognize we can express that product X times Y, in terms of the products of N over two by N over two matrices.
Things we're able to multiply recursively, plus additions.
And additions [inaudible] clearly easy to multiply two different matrices with say, N squared entries each, it's gonna be linear in the number of entries.
So it's gonna be N squared [inaudible] add two matrices that are N by N.
So this immediately leads us to our first recursive algorithm.
To describe it, let me quickly rewrite that expression we just saw on the previous slide.
And now, our first recursive algorithm is simply to evaluate all of these expressions in the obvious way.
So specifically, in step one, we recursively compute all of the necessary products, and observe that there are eight products that we have to compute.
Eight products of N over two by N over two matrices.
There are four entries in this expansion of X times Y.
Each of the, each of the blocks is the sum of two products, and none of the products re-occurred, they're all distinct.
So, naively, if you wanna evaluate this, we have to eight different products of N over two by N over two matrices.
Once those recursive calls complete, then all we do is do the, necessary four additions.
As we discussed, that takes time proportional to the number of entries in a matrix.
So this is gonna take quadratic time overall, quadratic [inaudible] N, linear in the number of entries.
Now, the question you should be asking is.
Is this a good algorithm? Was this good for anything, this recursive approach, splitting X and Y into these blocks, expanding the product in terms of these blocks, the recursively computing each of the blocks.
And I want to say it's totally not obvious, it is not clear what the running time of this recursive algorithm is.
I'm going to go ahead and give you a spoiler which is going to follow from the master method that we'll talk about in the next lecture.
But it turns out with this kind of recursive algorithm where you do eight recursive calls, each on a problem with dimensions half as much as what you started with, and then do quadratic [inaudible] outside.
The right time is going to be.
Cubic.
So exactly the same as with the straightforward iterative algorithm that follows from the definition.
That was cubic, it turns out, and that was clearly cubic.
This one, although it's not obvious, is cubic as well.
So no better, no worse than the straightforward iterative algorithm.
So in case you're feeling disappointed that we went through all this work and this sort of seemingly clever divide and conquer approach for matrix multiplication, and, and came out at the end no better than the interactive algorithm.
Well, there's really no reason to despair, cause remember, back in integer multiplication, we had a straightforward recursive algorithm where we had to do four recursive calls, products of N over two digit numbers.
But then, we had [inaudible] trick which said, oh, if we only did more clever products and more clever additions and subtractions, then we can get away with only three recursive calls.
And we'll see later that, that isn't even significant savings, in the time [inaudible] multiplication.
And we've done nothing analogously.
[inaudible] douse's trick, it was matrix multiplication problem.
All we did is the naive expansion in terms of sub-matrices, and the naive evaluation of the resulting expressions.
So.
$64,000 question is then, can we do something clever to reduce the number of recursive calls from eight down to something lower and that is where Strassen's algorithm comes in.
So at a high level, Strassen's algorithm has two steps, just like the first recursive algorithm that we discussed.
It recursively computes some products of smaller matrices and over two [inaudible] by two matrices.
[sound] But there's only going to be seven of them.
But they will be much less straightforward, they will be much more cleverly chosen than in the first recursive algorithm.
[sound].
And step two, then, is to actually produce the product of X and Y, produce each of those four blocks that we saw, with suitable, additions and subtractions of these seven products.
And again, these are much less straightforward than in the first recursive algorithm.
[sound].
And so while the additions and tractions involved will be a little bit more numerous, then they were in the naive recursive algorithm.
It's only gonna change the work in that part of the algorithm by a constant factor.
So we'll still spend only theta even squared work adding and subtracting things.
And we get a huge win in decreasing the number of recursive calls from eight to seven.
Now, just in case you have the intuition that shaving off one of the recursive calls.
Should only decrease the running time of an algorithm by one-eighth, by 12.
5%, in fact it has a tremendously more amplified effect because we do one less recursive call over and over and over again as we keep recursing in the algorithm.
So it makes a fundamental difference in the eventual running time of the algorithm, as we'll explore in detail in the next set of lectures, when we discuss the master method.
So again.
A bit of a spoiler alert.
What you're gonna see in the next set of lectures is indeed.
[inaudible] Rhythm does beat [inaudible].
It's better than [inaudible].
You'll have to watch the next set of lectures just so you know what the running time is.
When right now, that [inaudible] call is what changes the [inaudible] cubic.
Now, 1969 was obviously, quite a bit before my time, but.
By all accounts, from people I've talked to who were around then, and from, you know, what the books say, Strassen's Algorithm totally blew people's minds at the time.
Everybody was assuming that there's no way you could do better than the iterative algorithm, the cubic algorithm.
It just seemed that matrix multiplication intuitively fundamentally required all of the calculations that are spelled out in the definition.
So Strassen's Algorithm is an early glimpse of the magic and of the power.
Of clever algorithm design.
That if you really have a serious ingenuity, even for super fundamental problems, you can come up with fundamental savings over the more straightforward solutions.
So those are the main points I wanted to talk about Strassen's Algorithm, how you can beat cubic time by saving a recursive call with soon to be chosen clever products and clever addition subtractions.
Maybe a few of you are wondering, you know, what are these cleverly chosen products? Can you really do this? And I don't blame you.
There's no reason to believe me, just cuz I sort of spelled out this [inaudible] idea.
It's not obvious this should work.
You might actually want to see the products.
So, for those of you like that, this last slide is for you.
So here is Straus' algorithm in it's somewhat gory detail.
So let me tell you what the seven products are that we are going to form.
I'm going to label them P1 through P7 and they're all going to be defined in terms of the blocks of the inter-matrices X and Y.
So let me just remind you that we think of X in terms of it's blocks, A B C D.
And we think of Y in terms of its blocks E, F, G, H.
And remember, A through H are all N over two by N over two sub-matricies.
So here are the seven products, P1 through P7.
P1 is A times quantity F minus H.
P2 is quantity A plus B times H.
P3 is C plus D times E.
[sound].
P4 is D times G - E, P5 is quantity A+D + quantity A+H.
P six is quantity B minus D times quantity G plus H and finally P seven is quantity A minus C E plus F.
So I hope you'll agree that these are indeed only seven products, and we could compute these with seven recursive calls.
We've preprocessed with a little bit of additions and subtractions.
We have to compute F minus H, A plus B, C plus D and so on.
We compute all these new matrices from the blocks, and we can then recursively, with seven recursive calls, do these seven products that operate on N over two by N over two matrices.
Now, the question is, why is this useful? Why on Earth would we wanna know the [inaudible] of these seven products? So the amazing other part of the algorithm is that from just these seven products, we can, using only addition and subtraction, recover all four of the blocks of.
A X times Y So x times y.
You'll recall we expanded because of the blocks.
So we previously computed this to be AE+BG in the upper left corner, and [inaudible] expressions for the upper right, lower left, and lower right blocks.
So this we already know.
So the content of the claim is that these four blocks also arise from the seven products in the following way.
So the claim here is that these two different expressions for X times Y are exactly the same and they're the same block by block.
So in other words, what the claim is then this.
Crazy expression.
P five plus P four minus P two plus P six.
Where those were four of the products we listed above.
That is precisely A plus B G.
Similarly we're, we're claiming that P1 plus P2 is exactly AF plus BH.
That's actually easy to see.
P3 plus P4 is CE plus DG.
That's also easy to see, and then the other [inaudible] one is that P1 plus P5 minus P3 minus P7 is exactly the same as CF plus DH, so all four of those hold.
So let me just so you believe me cuz I don't know why you would believe me unless I actually showed you some of this derivation.
Let's just look at the proof of one of the cases of the upper left corner.
So that is, let's just expand out this crazy expression.
P5+P4-P2+P6, what do we get? Well, from P5, we get AE+AH+D+DH, and we add P4, so that's gonna give us, Plus DG minus DE, then we subtract P2, so that it gives us a minus, minus DH and then we add in P6.
So that gives us a PG plus BH minus DG minus DH.
Okay, so what happens next, well now we look for cancellations.
So we cancel the H's.
We cancel the D.
E.
's, we cancel the D.
H.
's.
We cancel the DGs.
We cancel the BHs.
And holy cow what do we get, we get A, E.
Plus B G.
That is, we get exactly what we were suppose to.
In.
The upper left block of X times Y.
So we just actually verified that this equation holds for the upper left block.
It's quite easy to see that it holds for the upper right and lower left blocks and a comparable calculation verifies it for the lower right blocks of the two.
So summarizing, because this claim holds.
>> Because, actually, we can recover the four blocks of S times Y from the seven products.
Strauss' algorithm works in the following way: you compute the seven products, P1 through P7, using seven recursive calls.
Then you just compute the four blocks using some extra additions and subtractions as shown in the claim.
So seven recursive calls on a number two by number two matrices, plus.
N squared work to do the necessary additions as we'll see on the master method lecture that is actually sufficient for.
Sub humid time.
Now I sympathize with you if you have the following question.
Which is how on Earth did Strauson come up with this? And indeed, this sort of illustrates, the difference between checking somebody's proof, and coming up with a proof.
Given that I told you the magical seven products and how you, from them, can recover the four desired blocks of x times y, it's really just mechanical to see that it works.
It's a totally different story of how you come up with p1 through p7 in the first place.
So how did Strassen come up with them? Honestly, your guess is as good as mine.
答案是，简单的[听不清]算法的运行时间相对于矩阵维数n以立方时间运行。
看到这一点，让我们回想一下矩阵乘法的定义。
该定义告诉我们输出矩阵z的每个条目zij被定义为k = 1至n的总和。
Xik时代YKJ。
这是X矩阵的[听不清]行与Y矩阵的J列的[听不清]乘积。
当然，假设我们以可以在恒定时间内访问给定条目的方式表示矩阵。
在此假设下，请记住其中的每个产品。
只需要恒定的时间。
因此，要计算ZIJ，我们只需要累加这些最终产品。
因此，这将是N时间来计算给定ZIJ的theta，然后我们必须计算N平方的[听不清]。
I有N个选择，J有N个选择，因此自然算法的总运算时间为N平方乘以N或三次运行时间，实际上这只是一个三重for循环，使用点分别计算输出射线的每个项产品。
因此，对于敏锐的算法设计人员来说，问题一如既往。
我们可以做得更好吗？我们是否可以通过将两个矩阵相乘来以立方时间击败？我们可能会特别感到鼓舞，因为我们已经看到了将两个整数相乘的进步。
我们将分而治之算法应用于将两个末尾数字整数相乘的问题。
而且，我们既有天真的递归算法，又有看似更好的算法。
由于[音频不清晰]的算法，该算法仅进行了三个递归调用。
现在我们还没有分析该算法的运行时间。
但是，正如我们稍后将看到的，这的确确实超过了小学算法的二次运行时间。
因此，很自然地要问，我们可以在这里做完全相同的事情吗？有一个显而易见的[听不清]算法，该算法直接从定义中得出。
也许类似于[听不清]，我们可以有一些巧妙的分而治之的方法，它可以击败三次。
这就是我们接下来要探讨的内容。
[声音]。
让我们回想一下分而治之的范式，使用它意味着什么。
好吧，我们首先必须确定较小的问题。
因此，如果我们想乘以两个NxN矩阵，就必须确定可以递归求解的较小矩阵的乘法。
一旦确定了如何将给定问题分解为较小的问题，然后在征服步骤中，我们简单地递归调用自己的算法，该算法将递归地将较小的矩阵相乘。
然后，通常，我们必须结合递归调用的结果来获得原始问题的解决方案（在我们的情况下），以获取原始两个矩阵的乘积。
从子矩阵的乘积中我们可以确定。
那么如何将分而治之范式应用于矩阵呢？因此，我们得到了两个N x N的矩阵，我们必须以某种方式确定可以递归相乘的较小的平方矩阵对。
因此，我认为这个想法很自然。
因此，我们从一个大的N×N矩阵X开始。
因此，这N行N列，我们必须以某种方式分成较小的部分。
现在，您可能要考虑的第一件事是将其放在左半部分和右半部分中，然后进入我们一直在处理的光线中，然后将X分解为两个矩阵不再是平方的，在一维上为N的二维，而在另一维上为N的长度，我们想递归地调用一个乘以平方矩阵的子例程。
因此，看起来很清楚的事情是将X划分为多个象限。
好的，我们有四个X。
每个将是N乘以N乘以2乘以N，对应于此矩阵的不同季度。
因此，用矩阵术语A，B，C和D称这些不同的象限或块。
所有这些在两个矩阵上都是N乘以N乘以N。
与往常一样，为简单起见，我假设N为偶数，并且与往常一样，这并不重要。
我们可以用Y做同样的技巧。
因此，我们将Y划分为四个象限。
第二个乘以N第二个矩阵，我们称其为E，F，G和H。
因此，关于矩阵很酷的一件事是，将矩阵拆分为块，然后将它们相乘，块的行为就好像它们是原子元素一样。
所以我的意思是，X和Y的乘积可以用其象限及其四个象限中的每一个来表示，其四个角中的每个角都可以写成X和Y象限的适当算术表达式。
这就是这些公式的确切含义。
它们与我们将两个数乘以两个矩阵相乘时完全相似。
因此，我不会正式证明这一事实。
我敢肯定，你们中的很多人以前都看过或熟悉它。
而且，如果您还没有的话，实际上很容易证明。
这不是显而易见的，您不一定无法从头顶看到它。
但是，如果您返回定义，则很容易验证。
D，当您将X和Y乘以多个时，可以按照X和Y的块表示为块的象限。
因此，我们所做的完全类似于谈论整数乘法时的情况，您想将两个整数（小x和小y）相乘，然后将它们分成两对N，两位数。
然后我们只是进行了扩展，我们观察了如何用N的两位数乘积来表示该扩展。
除了矩阵之外，这里同样发生了事情。
所以现在，就递归方法而言，我们正在开展业务。
我们想乘以X和Y。
它们是N×N矩阵。
我们认识到可以用乘以N乘以N乘以两个矩阵的乘积来表示乘积X乘以Y。
我们能够递归地乘以事物，加上加法。
加法[听不清]显然很容易将两个不同的矩阵相乘，每个矩阵有N个平方的条目，条目的数量将是线性的。
因此它将被N平方[听不清]加两个N乘N的矩阵。
因此，这立即导致我们进入第一个递归算法。
为了描述它，让我快速重写刚才在上一张幻灯片中看到的表达式。
现在，我们的第一个递归算法只是简单地以显而易见的方式评估所有这些表达式。
因此，具体地说，在第一步中，我们递归计算所有必需的乘积，并观察到必须计算八种乘积。
N在两个矩阵上乘以N的乘积为N的8乘积。
X乘以Y的扩展有四个项。
每个块都是两个乘积的总和，并且没有重复出现的乘积，它们都是不同的。
因此，天真的，如果您想对此进行评估，我们必须对N乘以2乘以N乘以两个矩阵得出8个不同乘积。
一旦这些递归调用完成，那么我们要做的就是做必要的四个附加操作。
正如我们所讨论的，这花费的时间与矩阵中条目的数量成正比。
因此，这将整体上采用二次时间，即二次[听不清] N，且条目数量呈线性。
现在，您应该问的问题是。
这是一个好的算法吗？这对任何东西都有好处，这种递归方法将X和Y分成这些块，就这些块扩展乘积，然后递归地计算每个块。
我想说的是完全不明显，还不清楚此递归算法的运行时间。
我将继续向您介绍一个扰流板，该扰流板将按照我们在下一讲中将要讨论的主要方法进行操作。
但是事实证明，使用这种递归算法，您需要进行八个递归调用，每个调用的问题尺寸都是开始时的一半，然后在外部进行二次[听不清]。
正确的时间将会到来。
立方体。
因此，与定义中的简单迭代算法完全相同。
事实证明，那是立方的，而且显然是立方的。
这个虽然不明显，但也是三次的。
因此，没有什么比简单的迭代算法更好，更糟糕了。
因此，如果您对我们完成了所有这些工作以及这种看似聪明的分而治之的矩阵乘法方法感到失望，那么最终并没有比交互式算法好。
好吧，确实没有理由感到绝望，请记住，回到整数乘法中，我们有一个简单的递归算法，其中我们必须进行四个递归调用，N的乘积为两位数。
但是，然后，我们有了[听不清]的把戏，它说，哦，如果我们只做更多聪明的乘积，做更多聪明的加法和减法，那么我们就只能摆脱三个递归调用。
稍后我们将看到，在[听不清]乘法中，这甚至不是很大的节省。
而且，我们也没有做任何类似的事情。
[听不清] douse的把戏，这是矩阵乘法问题。
我们所做的只是在子矩阵方面的天真扩展，以及对所得表达式的天真评估。
所以。
$ 64,000的问题是，我们可以做些聪明的事情来将递归调用的数目从八个减少到更低的数目，这就是Strassen算法的用武之地。
因此，从高层次来看，斯特拉森算法有两个步骤，就像我们讨论的第一个递归算法一样。
它递归计算一些较小矩阵的乘积，以及两个矩阵乘以两个[听不清]的乘积。
[声音]但是只有七个。
但是与第一种递归算法相比，它们将变得不那么直接，它们将被更明智地选择。
[声音]。
然后，第二步是实际产生X和Y的乘积，产生我们看到的这四个块中的每一个，并适当地对这七个积进行加法和减法。
同样，这些方法比第一种递归算法简单得多。
[声音]。
因此，虽然所涉及的增加和牵引会更多一些，但它们却属于幼稚的递归算法。
这只会使算法那部分的工作量变一个常数。
因此，我们仍然只会花费theta甚至平方运算来增加和减少事物。
而且我们在将递归调用的数量从8个减少到7个方面获得了巨大的胜利。
现在，以防万一，您有个直觉，可以减少一个递归调用。
应该只将算法的运行时间减少八分之一，即12。
5％，实际上，它具有更大的放大效果，因为在保持算法递归的过程中，我们一次又一次地减少了递归调用。
因此，它在算法的最终运行时间上有根本的不同，正如我们在讨论主方法时将在下一组讲座中详细探讨的那样。
再说一遍。
有点剧透警报。
在下一组演讲中，您将会看到的确实是。
[听不清]节奏确实打败[听不清]。
比[听不清]好。
您只需要观看下一组讲座，就可以知道开始时间。
现在，该[音频不清晰]调用会更改[音频不清晰]三次方。
现在，很明显，1969年比我早了很多。
大家都说过，从我曾经与之交谈过的人那里，以及从书中所说的，您知道，史特拉森的算法当时完全让人震惊。
每个人都认为，没有什么可以比迭代算法（三次算法）做得更好。
看起来矩阵乘法从根本上来说从根本上需要定义中阐明的所有计算。
因此，斯特拉森的算法是魔术和力量的早期发现。
巧妙的算法设计。
如果您确实有足够的才智，即使是对于超级基本问题，也可以比更简单的解决方案节省很多。
因此，这些就是我要谈论的Strassen算法的要点，如何通过节省递归调用来节省三次时间，并很快选择了聪明的乘积和聪明的加法减法。
也许你们当中有些人想知道，这些精心挑选的产品是什么？你真的能做到吗？而且我不怪你。
没有理由相信我，只是因为我有点阐明了这个[听不清]的想法。
显然这应该工作。
您可能实际上希望查看产品。
因此，对于您这样的人，最后一张幻灯片适合您。
因此，这是Straus的算法，其中有些细节。
因此，让我告诉您我们将要形成的七个产品是什么。
我将它们标记为P1到P7，它们都将根据矩阵X和Y的块进行定义。
因此，让我提醒您，我们想到的是X，即ABCD。
我们从Y，F，G，H的角度来考虑Y。
记住，A到H在两个子矩阵上都等于N乘以N。
因此，这是从P1到P7的七个产品。
P1是A乘以F减去H。
P2是数量A加B乘以H。
P3是C加D乘以E。
[声音]。
P4是D乘以G-E，P5是数量A + D +数量A + H。
P六是数量B减去D乘以G加上H，最后P七是数量A减去CE加上F。
因此，我希望您会同意这些确实只是七个产品，并且我们可以使用七个递归调用来计算它们。
我们已经进行了一些加减法的预处理。
我们必须计算F减去H，A加B，C加D等等。
我们从这些块中计算出所有这些新矩阵，然后我们可以通过七个递归调用来递归地执行这七个乘积在两个矩阵上乘以N乘以N的两个乘积。
现在的问题是，为什么这有用？为什么我们要在地球上想知道这七个产品的[听不清]？因此，该算法的令人惊奇的另一部分是，仅从这七个乘积中，我们就可以仅使用加法和减法来恢复其全部四个块。
AX乘以Y，所以x乘以y。
您会记得我们由于块而扩大了。
因此，我们先前将其计算为左上角的AE + BG，以及右上，左下和右下块的[听不清]表达式。
因此，我们已经知道了。
因此，权利要求书的内容在于，这四个区块也以下列方式来自于七个产品。
因此，这里的主张是，这两个不同的表达式在X乘以Y时是完全相同的，并且每个块都是相同的。
因此，换句话说，这是什么。
疯狂的表情。
P 5加P 4减去P 2加P 6。
这些是我们上面列出的四种产品。
就是A加BG。
同样，我们声称P1加P2恰好是AF加BH。
这实际上很容易看到。
P3加P4为CE加DG。
这也很容易看到，然后另一个[听不清]是P1加P5减P3减P7与CF加DH完全相同，因此所有这四个都成立。
因此，请允许我让您相信我，因为除非我实际向您展示了一些此类推导，否则我不知道您为什么会相信我。
让我们看一下左上角情况之一的证明。
就是说，让我们扩展这个疯狂的表情。
P5 + P4-P2 + P6，我们得到什么？好吧，从P5中，我们得到AE + AH + D + DH，然后加上P4，这样就给了我们，加上DG减去DE，然后减去P2，所以它得出的是负号，减去DH，然后加在P6中。
因此，我们得到了PG加BH减去DG减去DH。
好的，接下来会发生什么，现在我们要寻找取消。
因此，我们取消了H。
我们取消D。
是。
的，我们取消D。
H。
的。
我们取消总干事。
我们取消BH。
而圣牛，我们得到什么，我们得到A，E。
更多BG。
也就是说，我们得到的正是我们想要的。
在。
X的左上块乘以Y。
因此，我们实际上只是验证了该等式适用于左上方的块。
可以很容易地看出，它适用于右上和左下块，并且通过可比较的计算验证了这两个块的右下块。
总结一下，因为这种说法成立。
因为实际上，我们可以从七个乘积中恢复四个S乘以Y。
Strauss的算法以下列方式工作：使用七个递归调用来计算七个乘积，从P1到P7。
然后，您只需使用一些额外的加法和减法来计算这四个块，如权利要求中所示。
因此，对第二个乘第二个矩阵进行七个递归调用。
N平方的工作来做必要的加法，正如我们将在主方法讲课上看到的那样，实际上已经足够了。
亚湿时间。
如果您有以下问题，我现在很同情您。
Strauson在地球上是怎么想到的？确实，这种说明说明了检查某人的证明与提出证明之间的区别。
鉴于我已经告诉您神奇的七种产品，以及您如何从中获得四个所需的x乘以y的块，因此看到它确实是机械的。
首先，您是如何想到p1到p7的完全不同的故事。
那么Strassen是如何提出来的呢？老实说，你的猜测和我的一样好。
网友评论