3.3 「Stanford Algorithms」Strasse

In this video, we'll apply the divide and conquer algorithm design paradigm to the problem of multiplying matrices.

This will culminate in the study of Strassen's Matrix Multiplication Algorithm.

And this is a super cool algorithm for two reasons.

First of all, Strassen's Algorithm is completely non trivial.

It is totally non-obvious, very clever.

Not at all clear how Strassen ever came up with it.

The second cool feature, is, it's for such a fundamental problem.

So computers, as long as they've been in use, from the time they were invented, up'til today, a lot of their cycles are spent multiplying matrics, 'cause it just come up all the time in important applications.

So let me first just make sure we're all clear on what the, what the problem is of.

Multiplying two matrices.

So, we're gonna be interested in three matrices, X, Y, and Z.

They're all gonna, I'm gonna assume they all have the same dimensions, N by N.

The ideas we'll talk about are also relevant for multiplying non square matrices, but we're not gonna discuss it in this video.

The entries in these matrices, you know, you could think of it as whatever you want.

Maybe they're integers, maybe they're rationals, maybe they're from some [inaudible] field.

It depends on the application.

But the point is, they're just entries that we can add and multiply.

So how is it that you take two N by N matrices, X and Y, and multiply them producing a new N by N matrix, Z? Well, recall that the IJ entry of Z, that means the entry in the Ith row and Jth column, is simply the dot product of the Ith row of X with the Jth column of Y.

So if IJ was this red square, this [inaudible] over in the Z matrix, that would be derived from the corresponding row of the X matrix, and the corresponding column of the Y matrix.

And recall what I mean by dot product.

That just means you take the products of the individual components, and then add up the results.

So ultimately, the ZIJ entry boils down to a sum over N things, where each of the constituent products is just the XIK entry.

The [inaudible] of the matrix X with the KJ entry, of the matrix Y, where your K is ranging from one to N.

So that's how ZIJ is defined for a given pair of indices, I and J.

One thing to note is where we often use N to denote the input size, here we're using N to note the dimension of each of these matricies.

The input size is not N.

The input size is quite a bit bigger than N.

Specifically, each of these are N by N matricies and contain N squared entries.

So since presumably we have to read the input which has size and square.

Which happens to produce the output that also has size and squared.

The best we can really hope for [inaudible] is multiplication hour with the running time n squared.

So the question is how close when we get to it.

Before we talk about algorithms for matrix multiplication, let me just make sure we're all crystal clear on exactly what the problem is.

So let's just actually spell out what would be the result of multiplying two different, two bytes of matrices.

So we can.

[inaudible] 21 generic 2x2 matricies by just giving the first one entries A, B, C, and D for these four entries could all be anything.

And then we're multiplying by a second 2x2 matrix, let's call it entries E, F, G, and H.

Now, what's the result of multiplying these, where again, it's going to be a 2x2 matrix for each entry, it's just the corresponding dot product of the relevant row of the first matrix and column of the second matrix.

So to get the upper left entry.

You take the doc product of the upper row of the first matrix and the first column of the left column of the second matrix.

So, that results in.

Ae plus BG.

To get the upper right entry, we take the dot product of the top row of the left matrix with the right column of the second matrix.

So that gives us AF+BH.

And then filling in the other entries the same way, we get CE+DG and DF+DH.

You know, so that's multiplying two matrices, and we've already discussed the definition in general.

Now, suppose you had to write a program to actually compute to the result of multiplying two N by N matrices.

One natural way to do that would just be to return to the definition and which defines each of the N squared entries in the Z matrix as a suitable sum of products of [inaudible] entries of the X and Y matrices.

So on the next quiz, I'd like you to.

Figure out what exactly would be the running time of that algorithm as a function of the matrix dimension N where as usual we count the addition or multiplication of two individual entries as a constant time operation.

在本视频中，我们将应用分而治之算法设计范例来解决矩阵相乘的问题。

这将在Strassen矩阵乘法算法的研究中达到高潮。

这是一个超酷的算法，有两个原因。

首先，斯特拉森算法是完全不平凡的。

这是完全不明显的，非常聪明。

完全不清楚Strassen是怎么想出来的。

第二个很酷的功能是针对这样一个基本问题。

因此，从发明以来一直使用到今天的计算机，直到今天，它们的许多周期都花在乘以矩阵上，因为它在重要的应用程序中一直存在。

因此，首先让我确保我们都清楚问题的根源。

将两个矩阵相乘。

因此，我们将对三个矩阵X，Y和Z感兴趣。

它们都是，我假设它们都具有相同的尺寸，N乘N。

我们将要讨论的想法也与非平方矩阵的乘积相关，但是我们不会在本视频中讨论。

您知道，这些矩阵中的条目可以随心所欲。

也许它们是整数，也许是理性的，也许它们来自某些[听不清]领域。

这取决于应用程序。

但关键是，它们只是我们可以相加和相乘的条目。

那么，如何取两个N×N矩阵X和Y，然后将它们相乘以产生一个新的N×N矩阵Z？好吧，回想一下Z的IJ条目，这意味着第I行和第J列中的条目只是X的第I行与Y的第J列的点积。

因此，如果IJ是这个红色正方形，则Z矩阵中的[听不清]将从X矩阵的相应行和Y矩阵的相应列派生。

并记得我所说的点积。

这只是意味着您要获取各个组件的产品，然后将结果相加。

因此，最终，ZIJ条目归结为N个事物的总和，其中每个构成产品只是XIK条目。

矩阵X的[音频不清晰]和KJ项，矩阵Y的K范围为1到N。

因此，这就是为给定索引对I和J定义ZIJ的方式。

需要注意的一件事是，我们经常使用N来表示输入大小，这里我们使用N来表示每个矩阵的维数。

输入大小不是N。

输入大小比N大很多。

具体而言，它们中的每一个都是N×N矩阵，并包含N个平方项。

因此，既然我们大概必须读取具有大小和平方的输入。

碰巧产生的输出也具有大小和平方。

我们真正希望[听不清]的最佳是运行时间为n平方的乘法小时。

所以问题是当我们接近它时有多近。

在我们讨论矩阵乘法的算法之前，让我先确保我们对问题到底是什么一清二楚。

因此，让我们实际说明将两个不同的两个字节矩阵相乘的结果。

所以我们可以。

[听不清] 21个2x2通用矩阵，只需为这四个条目指定第一个条目A，B，C和D，就可以成为任何东西。

然后我们乘以第二个2x2矩阵，我们将其称为条目E，F，G和H。

现在，将它们相乘的结果是什么，再次，每个条目将是一个2x2矩阵，它只是第一个矩阵的相关行和第二个矩阵的列的对应点积。

因此，获得左上角的条目。

您将获得第一个矩阵的上一行和第二个矩阵的左列的第一列的doc乘积。

因此，结果。

Ae加BG。

要获得右上角的条目，我们将左矩阵的顶行与第二个矩阵的右列的点积相乘。

这样就给了我们AF + BH。

然后以相同的方式填写其他条目，我们得到CE + DG和DF + DH。

您知道，所以将两个矩阵相乘，我们已经在一般性地讨论了该定义。

现在，假设您必须编写一个程序来实际计算两个N乘以N矩阵的结果。

一种自然的方法是返回定义，并将Z矩阵中N个平方项定义为X和Y矩阵[听不清]项的乘积之和。

因此，在下一个测验中，我希望您能参加。

弄清楚该算法的运行时间确切地取决于矩阵维数N的函数，在通常情况下，我们将两个单独条目的加法或乘法算作一个恒定时间操作。

Strassen's Subcubic Matrix Multiplication Algorithm - Question 1

What is the straightforward running time of the iterative algorithm for matrix multiplication?

A. 𝜃(𝑛log(𝑛))

B. 𝜃(𝑛^2)

C. 𝜃(𝑛^3)

D. 𝜃(𝑛^4)