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.

答案是，簡單的[聽不清]算法的運行時間相對于矩陣維數(shù)n以立方時間運行。

看到這一點，讓我們回想一下矩陣乘法的定義。

該定義告訴我們輸出矩陣z的每個條目zij被定義為k = 1至n的總和。

Xik時代YKJ。

這是X矩陣的[聽不清]行與Y矩陣的J列的[聽不清]乘積。

當(dāng)然，假設(shè)我們以可以在恒定時間內(nèi)訪問給定條目的方式表示矩陣。

在此假設(shè)下，請記住其中的每個產(chǎn)品。

只需要恒定的時間。

因此，要計算ZIJ，我們只需要累加這些最終產(chǎn)品。

因此，這將是N時間來計算給定ZIJ的theta，然后我們必須計算N平方的[聽不清]。

I有N個選擇，J有N個選擇，因此自然算法的總運算時間為N平方乘以N或三次運行時間，實際上這只是一個三重for循環(huán)，使用點分別計算輸出射線的每個項產(chǎn)品。

因此，對于敏銳的算法設(shè)計人員來說，問題一如既往。

我們可以做得更好嗎？我們是否可以通過將兩個矩陣相乘來以立方時間擊敗？我們可能會特別感到鼓舞，因為我們已經(jīng)看到了將兩個整數(shù)相乘的進步。

我們將分而治之算法應(yīng)用于將兩個末尾數(shù)字整數(shù)相乘的問題。

而且，我們既有天真的遞歸算法，又有看似更好的算法。

由于[音頻不清晰]的算法，該算法僅進行了三個遞歸調(diào)用。

現(xiàn)在我們還沒有分析該算法的運行時間。

但是，正如我們稍后將看到的，這的確確實超過了小學(xué)算法的二次運行時間。

因此，很自然地要問，我們可以在這里做完全相同的事情嗎？有一個顯而易見的[聽不清]算法，該算法直接從定義中得出。

也許類似于[聽不清]，我們可以有一些巧妙的分而治之的方法，它可以擊敗三次。

這就是我們接下來要探討的內(nèi)容。

[聲音]。

讓我們回想一下分而治之的范式，使用它意味著什么。

好吧，我們首先必須確定較小的問題。

因此，如果我們想乘以兩個NxN矩陣，就必須確定可以遞歸求解的較小矩陣的乘法。

一旦確定了如何將給定問題分解為較小的問題，然后在征服步驟中，我們簡單地遞歸調(diào)用自己的算法，該算法將遞歸地將較小的矩陣相乘。

然后，通常，我們必須結(jié)合遞歸調(diào)用的結(jié)果來獲得原始問題的解決方案（在我們的情況下），以獲取原始兩個矩陣的乘積。

從子矩陣的乘積中我們可以確定。

那么如何將分而治之范式應(yīng)用于矩陣呢？因此，我們得到了兩個N x N的矩陣，我們必須以某種方式確定可以遞歸相乘的較小的平方矩陣對。

因此，我認為這個想法很自然。

因此，我們從一個大的N×N矩陣X開始。

因此，這N行N列，我們必須以某種方式分成較小的部分。

現(xiàn)在，您可能要考慮的第一件事是將其放在左半部分和右半部分中，然后進入我們一直在處理的光線中，然后將X分解為兩個矩陣不再是平方的，在一維上為N的二維，而在另一維上為N的長度，我們想遞歸地調(diào)用一個乘以平方矩陣的子例程。

因此，看起來很清楚的事情是將X劃分為多個象限。

好的，我們有四個X。

每個將是N乘以N乘以2乘以N，對應(yīng)于此矩陣的不同季度。

因此，用矩陣術(shù)語A，B，C和D稱這些不同的象限或塊。

所有這些在兩個矩陣上都是N乘以N乘以N。

與往常一樣，為簡單起見，我假設(shè)N為偶數(shù)，并且與往常一樣，這并不重要。

我們可以用Y做同樣的技巧。

因此，我們將Y劃分為四個象限。

第二個乘以N第二個矩陣，我們稱其為E，F(xiàn)，G和H。

因此，關(guān)于矩陣很酷的一件事是，將矩陣拆分為塊，然后將它們相乘，塊的行為就好像它們是原子元素一樣。

所以我的意思是，X和Y的乘積可以用其象限及其四個象限中的每一個來表示，其四個角中的每個角都可以寫成X和Y象限的適當(dāng)算術(shù)表達式。

這就是這些公式的確切含義。

它們與我們將兩個數(shù)乘以兩個矩陣相乘時完全相似。

因此，我不會正式證明這一事實。

我敢肯定，你們中的很多人以前都看過或熟悉它。

而且，如果您還沒有的話，實際上很容易證明。

這不是顯而易見的，您不一定無法從頭頂看到它。

但是，如果您返回定義，則很容易驗證。

D，當(dāng)您將X和Y乘以多個時，可以按照X和Y的塊表示為塊的象限。

因此，我們所做的完全類似于談?wù)撜麛?shù)乘法時的情況，您想將兩個整數(shù)（小x和小y）相乘，然后將它們分成兩對N，兩位數(shù)。

然后我們只是進行了擴展，我們觀察了如何用N的兩位數(shù)乘積來表示該擴展。

除了矩陣之外，這里同樣發(fā)生了事情。

所以現(xiàn)在，就遞歸方法而言，我們正在開展業(yè)務(wù)。

我們想乘以X和Y。

它們是N×N矩陣。

我們認識到可以用乘以N乘以N乘以兩個矩陣的乘積來表示乘積X乘以Y。

我們能夠遞歸地乘以事物，加上加法。

加法[聽不清]顯然很容易將兩個不同的矩陣相乘，每個矩陣有N個平方的條目，條目的數(shù)量將是線性的。

因此它將被N平方[聽不清]加兩個N乘N的矩陣。

因此，這立即導(dǎo)致我們進入第一個遞歸算法。

為了描述它，讓我快速重寫剛才在上一張幻燈片中看到的表達式。

現(xiàn)在，我們的第一個遞歸算法只是簡單地以顯而易見的方式評估所有這些表達式。

因此，具體地說，在第一步中，我們遞歸計算所有必需的乘積，并觀察到必須計算八種乘積。

N在兩個矩陣上乘以N的乘積為N的8乘積。

X乘以Y的擴展有四個項。

每個塊都是兩個乘積的總和，并且沒有重復(fù)出現(xiàn)的乘積，它們都是不同的。

因此，天真的，如果您想對此進行評估，我們必須對N乘以2乘以N乘以兩個矩陣得出8個不同乘積。

一旦這些遞歸調(diào)用完成，那么我們要做的就是做必要的四個附加操作。

正如我們所討論的，這花費的時間與矩陣中條目的數(shù)量成正比。

因此，這將整體上采用二次時間，即二次[聽不清] N，且條目數(shù)量呈線性。

現(xiàn)在，您應(yīng)該問的問題是。

這是一個好的算法嗎？這對任何東西都有好處，這種遞歸方法將X和Y分成這些塊，就這些塊擴展乘積，然后遞歸地計算每個塊。

我想說的是完全不明顯，還不清楚此遞歸算法的運行時間。

我將繼續(xù)向您介紹一個擾流板，該擾流板將按照我們在下一講中將要討論的主要方法進行操作。

但是事實證明，使用這種遞歸算法，您需要進行八個遞歸調(diào)用，每個調(diào)用的問題尺寸都是開始時的一半，然后在外部進行二次[聽不清]。

正確的時間將會到來。

立方體。

因此，與定義中的簡單迭代算法完全相同。

事實證明，那是立方的，而且顯然是立方的。

這個雖然不明顯，但也是三次的。

因此，沒有什么比簡單的迭代算法更好，更糟糕了。

因此，如果您對我們完成了所有這些工作以及這種看似聰明的分而治之的矩陣乘法方法感到失望，那么最終并沒有比交互式算法好。

好吧，確實沒有理由感到絕望，請記住，回到整數(shù)乘法中，我們有一個簡單的遞歸算法，其中我們必須進行四個遞歸調(diào)用，N的乘積為兩位數(shù)。

但是，然后，我們有了[聽不清]的把戲，它說，哦，如果我們只做更多聰明的乘積，做更多聰明的加法和減法，那么我們就只能擺脫三個遞歸調(diào)用。

稍后我們將看到，在[聽不清]乘法中，這甚至不是很大的節(jié)省。

而且，我們也沒有做任何類似的事情。

[聽不清] douse的把戲，這是矩陣乘法問題。

我們所做的只是在子矩陣方面的天真擴展，以及對所得表達式的天真評估。

所以。

$ 64,000的問題是，我們可以做些聰明的事情來將遞歸調(diào)用的數(shù)目從八個減少到更低的數(shù)目，這就是Strassen算法的用武之地。

因此，從高層次來看，斯特拉森算法有兩個步驟，就像我們討論的第一個遞歸算法一樣。

它遞歸計算一些較小矩陣的乘積，以及兩個矩陣乘以兩個[聽不清]的乘積。

[聲音]但是只有七個。

但是與第一種遞歸算法相比，它們將變得不那么直接，它們將被更明智地選擇。

[聲音]。

然后，第二步是實際產(chǎn)生X和Y的乘積，產(chǎn)生我們看到的這四個塊中的每一個，并適當(dāng)?shù)貙@七個積進行加法和減法。

同樣，這些方法比第一種遞歸算法簡單得多。

[聲音]。

因此，雖然所涉及的增加和牽引會更多一些，但它們卻屬于幼稚的遞歸算法。

這只會使算法那部分的工作量變一個常數(shù)。

因此，我們?nèi)匀恢粫ㄙMtheta甚至平方運算來增加和減少事物。

而且我們在將遞歸調(diào)用的數(shù)量從8個減少到7個方面獲得了巨大的勝利。

現(xiàn)在，以防萬一，您有個直覺，可以減少一個遞歸調(diào)用。

應(yīng)該只將算法的運行時間減少八分之一，即12。

5％，實際上，它具有更大的放大效果，因為在保持算法遞歸的過程中，我們一次又一次地減少了遞歸調(diào)用。

因此，它在算法的最終運行時間上有根本的不同，正如我們在討論主方法時將在下一組講座中詳細探討的那樣。

再說一遍。

有點劇透警報。

在下一組演講中，您將會看到的確實是。

[聽不清]節(jié)奏確實打敗[聽不清]。

比[聽不清]好。

您只需要觀看下一組講座，就可以知道開始時間。

現(xiàn)在，該[音頻不清晰]調(diào)用會更改[音頻不清晰]三次方。

現(xiàn)在，很明顯，1969年比我早了很多。

大家都說過，從我曾經(jīng)與之交談過的人那里，以及從書中所說的，您知道，史特拉森的算法當(dāng)時完全讓人震驚。

每個人都認為，沒有什么可以比迭代算法（三次算法）做得更好。

看起來矩陣乘法從根本上來說從根本上需要定義中闡明的所有計算。

因此，斯特拉森的算法是魔術(shù)和力量的早期發(fā)現(xiàn)。

巧妙的算法設(shè)計。

如果您確實有足夠的才智，即使是對于超級基本問題，也可以比更簡單的解決方案節(jié)省很多。

因此，這些就是我要談?wù)摰腟trassen算法的要點，如何通過節(jié)省遞歸調(diào)用來節(jié)省三次時間，并很快選擇了聰明的乘積和聰明的加法減法。

也許你們當(dāng)中有些人想知道，這些精心挑選的產(chǎn)品是什么？你真的能做到嗎？而且我不怪你。

沒有理由相信我，只是因為我有點闡明了這個[聽不清]的想法。

顯然這應(yīng)該工作。

您可能實際上希望查看產(chǎn)品。

因此，對于您這樣的人，最后一張幻燈片適合您。

因此，這是Straus的算法，其中有些細節(jié)。

因此，讓我告訴您我們將要形成的七個產(chǎn)品是什么。

我將它們標記為P1到P7，它們都將根據(jù)矩陣X和Y的塊進行定義。

因此，讓我提醒您，我們想到的是X，即ABCD。

我們從Y，F(xiàn)，G，H的角度來考慮Y。

記住，A到H在兩個子矩陣上都等于N乘以N。

因此，這是從P1到P7的七個產(chǎn)品。

P1是A乘以F減去H。

P2是數(shù)量A加B乘以H。

P3是C加D乘以E。

[聲音]。

P4是D乘以G-E，P5是數(shù)量A + D +數(shù)量A + H。

P六是數(shù)量B減去D乘以G加上H，最后P七是數(shù)量A減去CE加上F。

因此，我希望您會同意這些確實只是七個產(chǎn)品，并且我們可以使用七個遞歸調(diào)用來計算它們。

我們已經(jīng)進行了一些加減法的預(yù)處理。

我們必須計算F減去H，A加B，C加D等等。

我們從這些塊中計算出所有這些新矩陣，然后我們可以通過七個遞歸調(diào)用來遞歸地執(zhí)行這七個乘積在兩個矩陣上乘以N乘以N的兩個乘積。

現(xiàn)在的問題是，為什么這有用？為什么我們要在地球上想知道這七個產(chǎn)品的[聽不清]？因此，該算法的令人驚奇的另一部分是，僅從這七個乘積中，我們就可以僅使用加法和減法來恢復(fù)其全部四個塊。

AX乘以Y，所以x乘以y。

您會記得我們由于塊而擴大了。

因此，我們先前將其計算為左上角的AE + BG，以及右上，左下和右下塊的[聽不清]表達式。

因此，我們已經(jīng)知道了。

因此，權(quán)利要求書的內(nèi)容在于，這四個區(qū)塊也以下列方式來自于七個產(chǎn)品。

因此，這里的主張是，這兩個不同的表達式在X乘以Y時是完全相同的，并且每個塊都是相同的。

因此，換句話說，這是什么。

瘋狂的表情。

P 5加P 4減去P 2加P 6。

這些是我們上面列出的四種產(chǎn)品。

就是A加BG。

同樣，我們聲稱P1加P2恰好是AF加BH。

這實際上很容易看到。

P3加P4為CE加DG。

這也很容易看到，然后另一個[聽不清]是P1加P5減P3減P7與CF加DH完全相同，因此所有這四個都成立。

因此，請允許我讓您相信我，因為除非我實際向您展示了一些此類推導(dǎo)，否則我不知道您為什么會相信我。

讓我們看一下左上角情況之一的證明。

就是說，讓我們擴展這個瘋狂的表情。

P5 + P4-P2 + P6，我們得到什么？好吧，從P5中，我們得到AE + AH + D + DH，然后加上P4，這樣就給了我們，加上DG減去DE，然后減去P2，所以它得出的是負號，減去DH，然后加在P6中。

因此，我們得到了PG加BH減去DG減去DH。

好的，接下來會發(fā)生什么，現(xiàn)在我們要尋找取消。

因此，我們?nèi)∠薍。

我們?nèi)∠鸇。

是。

的，我們?nèi)∠鸇。

H。

的。

我們?nèi)∠偢墒隆?/p>

我們?nèi)∠鸅H。

而圣牛，我們得到什么，我們得到A，E。

更多BG。

也就是說，我們得到的正是我們想要的。

在。

X的左上塊乘以Y。

因此，我們實際上只是驗證了該等式適用于左上方的塊。

可以很容易地看出，它適用于右上和左下塊，并且通過可比較的計算驗證了這兩個塊的右下塊。

總結(jié)一下，因為這種說法成立。

因為實際上，我們可以從七個乘積中恢復(fù)四個S乘以Y。

Strauss的算法以下列方式工作：使用七個遞歸調(diào)用來計算七個乘積，從P1到P7。

然后，您只需使用一些額外的加法和減法來計算這四個塊，如權(quán)利要求中所示。

因此，對第二個乘第二個矩陣進行七個遞歸調(diào)用。

N平方的工作來做必要的加法，正如我們將在主方法講課上看到的那樣，實際上已經(jīng)足夠了。

亞濕時間。

如果您有以下問題，我現(xiàn)在很同情您。

Strauson在地球上是怎么想到的？確實，這種說明說明了檢查某人的證明與提出證明之間的區(qū)別。

鑒于我已經(jīng)告訴您神奇的七種產(chǎn)品，以及您如何從中獲得四個所需的x乘以y的塊，因此看到它確實是機械的。

首先，您是如何想到p1到p7的完全不同的故事。

那么Strassen是如何提出來的呢？老實說，你的猜測和我的一樣好。