Transcript

The following content is provided under a Creative Commons License. Your support will help MIT OpenCourseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseware at ocw.mit.edu. All right, let's get started. I'm Eric Demaine. You can call me Eric. And today we're going to do another divide and conquer algorithm called the fast Fourier transform. It's probably the most taught algorithm at MIT. It's used in all sorts of contexts. Especially digital signal processing like MP3 compression, all sorts of things.

But we're going to think about it today in the context of divide and conquer and polynomials. So, let me remind you. I mean, this class is all about polynomial time, but usually with polynomial time we only care about the lead term. Today, and today only pretty much, we're going to be thinking about all the terms in a polynomial. So, my I'll talk about polynomials mostly A and B. You have a constant term and then linear term and a quadratic term and so on. Up to I will say that there are N terms, which means the last one is A N minus 1. So, normally the degree of the polynomial here is N minus 1.

I wish the degree was defined to be N here, but whatever. That's I don't I can't change the definitions in algebra. So, this is the traditional algebraic way of thinking about a polynomial. Of course, you can write it with summation notation. A K X to the K K equals 0 to N minus 1. We'll jump back and forth between them. I'm also going to introduce a vector notation for polynomials because So, the A I's are real numbers typically. We might change that at some point. But usually a common reason, maybe you don't care much about polynomials, but you definitely care about vectors. Any kind of one-dimensional data set is a string of real numbers.

Like if you're sampling audio, like right now we're recording this microphone, you're seeing lots of different uh the movement of the membrane in this microphone over time. You're sampling whatever 40,000 times a second. Each one you're measuring a real number about where that thing is. That is a sequence of real numbers. Now, you can convert it into a polynomial if you want. They're the same thing. X is not necessarily meaningful here. What we really care about are the coefficients. Okay, now given such a polynomial, there are three typical things we want to do. So, these are the operations on polynomials.

I'll say why we want to do them in a second. So, the obvious one if you do care about X is some kind of evaluation. So, maybe I give you a polynomial A of X and I give you a number, let's call it X0, and I want to compute what is A of X0. So, if I plug in X here is a general variable, but if I give you an actual real number, say, for the X's, what does that add up to? Okay. So, how how would you solve evaluation before we go to the other operations? I mean, there's an obvious way. We you know, you compute all the terms and add them up. But if you do that naively, computing uh X to the K, well, let's in this form, maybe computing X to the K maybe takes K multiplications.

And so, the total running time will be quadratic. But we can do better than that. I know it's 11:00 too early in the morning to think, but Yeah. If you already calculated X to the I, you can calculate X to the I plus 1 by 1. Good. Once you've computed X to the K, you can compute X to the K plus 1 in with one multiplication. And so, you can compute all X to the N's in linear time. And then do the all the then you're basically doing a dot product between the X to the K's and the A vector. Cool. My first frisbee. So, that's one way to do it. There's a slightly slicker way to write it called Horner's rule, but it's doing exactly the same thing that you said.

It's a This is just a nice algebraic way of writing it. A of X is the same as A0 plus X times A1 plus X times A2 plus and so on. X times A N minus 1 and then lots of close parentheses. So, this is a of course equivalent to that expression by the just law of distribution. And this is essentially doing the X's X products one at a time. So, this is clearly order N additions and multiplications, so we get order N time. In this lecture, time is the number of arithmetic operations. It's our model. Assume it takes constant time to multiply or add two real numbers. Okay. Um Cool. So, evaluation. That's easy.

Linear time for today is good. Quadratic is bad. We want to beat quadratic. Okay, second thing you might want to do with polynomials is add them. The third thing is multiply them. So, we're given two polynomials A of X and B of X and we want to compute a new polynomial C of X that is the summation. Now, how do you define the summation? Well, you would like C of X to equal A of X plus B of X for all X. That's the definition. Of course, we can do it algebraically as well because these are numbers in the end for any X this evaluates to a number. So, if we add two polynomials of this form, one with A I's, one with the B I's, all we're doing is adding corresponding A I's and B I's.

So, this is easy. We just need C K to equal A K plus B K. For all K. So, again, linear time, no problem. Okay, third operation is the exciting one, the hard one to get good. Otherwise, this lecture would be over in a couple more minutes. So, multiplication, same deal. We're given A of X, B of X and we want to convert that into some C of X that for all X evaluates to the product of those two polynomials. Okay. How do we do this? We can't just multiply corresponding A K's and B K's. In fact, if you take a big thing like this, you multiply it by a corresponding big thing, let's do it. This doesn't look like fun.

We get, let's see. So, the constant term is just the product. That's easy of the constant terms. But then if I take this product or this product, I get linear terms. It's going to be A1 B0 plus A0 B1 times X. And then there's a quadratic term, which I get from switch colors. This and this and this. So, there's three things times X squared. And that's where I get tired. I'm going to switch to the summation notation. I didn't go to high school, but I assume in high school algebra you learn this. C K is the sum of J equals 0 to K A J B K minus J. That's the general form because A J came from an X to the J term, B K minus J came from an X to the K minus J term.

When you multiply those together, you get X to the K. So, this is the coefficient of X to the K. Cool. So, that's what we'd like to compute. Given A and B, we want to compute this polynomial C. How long does it take? We have to do this for all K. So, to compute the Kth term takes order K time. So, total time is N squared. So, that's not good for this lecture. We want to do better. Uh in fact, today we will achieve uh n log n. That's our goal. Polynomial multiplication in n log n. Why do we care about polynomial multiplication? Uh because it's equivalent to another operation which we use all the time in digital signal processing, image editing, all sorts of different things, which is convolution.

Uh convolution is usually thought of as an operation on vectors. Uh so remember this vector notation where we're just thinking about the coefficients, x's are kind of irrelevant, just thinking about a sequence of real numbers. Uh so maybe that sequence of real numbers for a represents some, I don't know, waveform. Maybe this is the audio that I'm speaking now. And then I take some other waveform. Here I have a Gaussian function, e to the minus x squared, and I want to take uh for all possible shifts of this Gaussian, I want to compute the dot product between the blackboard and the piece of paper.

Okay, that's some kind of smoothing function if I wanted to clean up noise or something like that. You can do the same thing on a two-dimensional image. It's a little harder to think about, but you can map a two-dimensional image to a one-dimensional vector, and you have a two-dimensional Gaussian if you ever do Gaussian blur in Photoshop, uh this is what you're doing, a convolution, uh and it's used to like as if your pretend that your lens was out of focus when you do that. Uh it's done in in audio processing and all sorts of things. Uh so formally, you're given two vectors, and you want to take all possible shifts of one vector and take the dot product with the other one.

I have that written down. I just uh dot product, same thing as inner product, which just means multiply corresponding uh positions and add them up. And if you ignore this minus sign, that's exactly what this is doing. This is taking a j versus b k, pretend it's plus j. So that's the b j vector, but with all possible shifts k. We compute this for all k. That's really cool. We're going to compute it in n log n time. All different n shifts of b will take the dot product with a. It's kind of magical cuz it looks like you're doing n squared work, but we will do it in n log n time. Uh the only issue is we have to reverse b.

Uh then the minus signs turn into plus signs. Okay, and there's some boundary conditions, but it's basically the same. If we can solve polynomial multiplication, we can solve convolution. Cool? So that's why we care about multiplication. Uh so how are we going to solve this? What I'd like to do is talk about alternate representations of polynomials. That's next thing here. We just did operations. Let's talk about different representations. So we talked about this one representation. It's one way to represent a polynomial, but it's not the only one. You probably know others. So on the one hand, we have uh representation a is uh coefficient vector.

So we can write down the a i's. That was just one way to represent a polynomial. Can anyone give me another way to represent polynomial? I have two ways in mind. Yeah. Generating function? Generating function. Isn't that the same Oh, I guess uh in principle, you could imagine like writing a recurrence on the generating function or something. It's possible. In general, generating functions are polynomials if you know what that they are cool. Um so that doesn't quite answer the question. Yeah? Sure. Point representation? Sorry? Point? Point representation, yeah. I call them samples. Uh I'm going to put that under c.

A bunch of samples, a bunch of points on the polynomial. Uh so like x k uh y k for How many do we need? I think n minus one should do it. We'll check. Yep. Uh and if we are told that a of x k equals y k, and we're told that all the x k's are distinct, then this uniquely determines polynomial. You have a degree n minus one polynomial, and you have n samples, there's only one polynomial that passes through all those points. That's uh it's a consequence of the fundamental theorem of of algebra that gives you uniqueness. Existence, I think was proved by Legendre in 17-1800s, long time ago. This is good.

This is what we're going to use. There's another answer. I should give you a Frisbee first. I'm so excited. You're just wait till I hit you. Then be less excited. Okay. So samples, coefficients, anything else? Yeah. Roots, yeah. Roots is the other answer I was looking for, but it's not going to be so good algorithmically as we'll see. It's all right. Um so I could give you a sequence of roots. This is the fundamental theorem of algebra that every polynomial is uniquely determined by its set of roots if you allow roots with multiplicity. Uh then every polynomial degree n has exactly n roots. So this would be some sequence of uh r one up to r n minus one.

Um and the polynomial would be given as you actually need a constant multiplier, but x minus r zero, x minus r one. That would be polynomial. The trouble with roots is that if I give you a coefficient vector, and I want to compute the roots, not only is it hard to do, it's impossible to do in our model. If you're only allowed to add, subtract, multiply, divide, take square roots, take k-th roots, uh there is no way to solve a polynomial of degree five or larger. You know, there's quadratic formula, cubic formula, quartic formula. There is no quintic formula. That's an old result, 1800s. So uh going from coefficient vector to roots takes infinite time.

It's not so good. Uh and in particular, if we think about our operations, uh addition becomes really difficult. Uh multiplication is easy. If I have two uh polynomials represented as a sequence of roots, I want to multiply them, that's just concatenating the vectors, uh taking the union the vectors of the of the root lists. So that's cool, and multiplying the c's, I guess. But addition is really hard because addition is sort of fundamentally about coefficient vectors, uh and then once you go there, you can go from roots to coefficient vectors and add them up, but then there's no relation between the roots of the sum of the polynomials versus the roots of the original.

So uh it's I don't know for sure that that's impossible. It's definitely very, very hard, probably impossible. So uh let me draw a little table. Each of these representations has some advantages and a disadvantage in terms of these three operations. So on the one hand, we have uh the sort of algorithms we care about. Uh evaluation, addition, and multiplication. And on the other axis, we have our representations, which are coefficient vectors, uh roots, and samples. You'll see why I chose this order in a moment. It makes for a nice pretty matrix. Uh so we've talked about almost every cell in this matrix, uh but let me just summarize.

So we started out just thinking about uh coefficient vector, and evaluation was linear time. Addition was linear time. Multiplication so far is quadratic, although our goal is to make n log n. For roots, uh I just said multiplication is easy, that's linear time. Addition is really hard. Like infinite time. And evaluation, I guess that's linear time. In fact, the way it's written, you only have a linear number of subtractions and multiplications, so it's really easy to evaluate. Uh and then sample vectors, we haven't talked much about that. Um so the idea is suppose you're given two polynomials with the same x k's.

We're going to fix x k's. All we need is that they're distinct. So, x k could equal k, for example. Just a bunch of integers. And then we are told what polynomial A evaluates to at every x k, and we're told what polynomial B evaluates to at every x k. So, we're given some y k's and some z k's. And then we want to compute, say, the the sum or the product of those two vectors. What do we do? Just add or multiply the corresponding uh y k and z k's. Right? Cuz if we're told we want uh c of x to equal a of x times b of x or c of x to equal a of x plus b of x for all x. Well, now we know what x's we care about.

We just do it at the x k's. That's what we're told for a and for b. And so, to compute c of x k is just the sum or the product of y k and z k. Okay, so multiplication is really easy in the sample view, and this is why we are going to use this view. We're also going to use this view because, as we'll see, there's a problem. Uh addition is easy. Multiplication is easy. Evaluation is annoying. How I can evaluate a of x k at or a of x at x k for any k, but I can't evaluate it at some at some arbitrary value of x. Okay? That's annoying. I'm told at these finite sample points, but now I have to somehow interpolate.

This is called polynomial interpolation. Well studied in numerical analysis and so on. You can do it. But uh it takes quadratic time in general. Best known algorithms are quadratic. So, this is bad. This is bad, and this is bad. So, no representation is perfect. Life sucks. Uh what we'd like is to get the best. Now, this one is really hard to work with because converting into roots is sort of impossible is impossible in our in an arithmetic model. So, we're going to focus on column A and column C. We kind of like to take the min of those two columns. We won't quite get that. What we will get is a an algorithm for converting between these two representations in n log n time.

So, not quite linear, but close. And once we can do that, if we want to multiply two things in the coefficient land, we can convert to sample land, do it in linear time, and then convert back. So, uh that's the magical transformation we're going to cover, and it is called the fast Fourier transform. Fast Fourier transform is the algorithm. Discrete Fourier transform is that transformation um mathematically. Cool. So, the whole name of the game is converting uh from coefficient representation to samples or vice versa. Turns out they're almost the same, though that won't be obvious for a long time, till the end of the class.

Any questions before we proceed? Yeah. Um so, for polynomial multiplication, why not we evaluate A and B first, then multiply? Ah. Uh so, okay, the question is uh if I want to we'll we'll get there in a second, but if I want to multiply uh and it's so easy to do in sample land, why don't I just sample A and B, and then multiply them? That's right. Uh but in fact, sampling is not so easy. It takes quadratic time. Let's go there now. Cuz we have n samples to do. Each one will cost linear time. Uh remember to evaluate a polynomial takes linear time. If you want to think of it in a matrix that's entered the matrix, uh then we get a big matrix.

So, we're given the x i's, and we just want to evaluate a given polynomial uh whose coefficients are given by a zero, a one, a two, and minus one. Our goal is to compute the y i's, y zero, y one, y two, to y n minus one. Uh and so, you can if you know a matrix vector product, you take this row with that column, you take the dot product, that multiplies corresponding entries, you get y zero. That is the definition of the polynomial evaluation. I'm just going to write a bunch of these rows. You get the pattern. Pretty simple. Okay, this is called the Vandermonde matrix. I'll call it V. And in general, uh I I have room for it, so let me go.

In general, if we look at uh v i j, it's just um sorry. The you may notice I'm not using the letter i. We'll we'll get to why in a moment. v j k, uh row j, column k, that's going to be x sub j to the power k. That's the Vandermonde matrix. Um we can compute it in quadratic time. It has quadratic entries. We can use the trick suggested earlier, compute each term from the previous one uh by multiplying by x j. Uh and then we want to compute this matrix vector product, and you can clearly do it in quadratic time, uh just computing each thing correspondingly. And that's sort of the best you can do without any further assumptions.

So, this takes uh So, if I I want to compute this product, that's the uh coefficients to samples problem. Uh this is the same thing as computing V times the A vector. So, this is a matrix vector multiplication, which takes uh n squared time. Okay. Um on the other hand, so that's a problem cuz we're trying to beat quadratic multiplication. So, if we spend quadratic time to convert over here, it doesn't matter if this is linear time. There are two problems. One is that conversion costs too much. The other is we don't yet know how to convert backwards. Uh but this matrix view gives us also the reverse transformation.

If we want to convert samples to coefficients, uh this is uh the best notation I know is from MATLAB. How many people know MATLAB? A bunch. So, for you, it's V backslash A. But uh usually in linear algebra, like 1806, you see you have you have uh some matrix V times some unknown vector, usually it's called x, here it's called a, and you know the right-hand side, you want to solve for this. How do you do it? Sorry? Multiply by the inverse. Yeah. How do you do it in computer science? Gaussian elimination. Turns out inverse is the right answer here, but uh Gaussian elimination would be the standard way to solve a linear system like that.

Trouble with Gaussian elimination is it takes cubic time in its in its normal form. Uh in this case, it's a little bit special because this matrix is essentially fixed. The x i's don't need to change. It could be x i is just i or something. Uh so, we can in this case, it's a little better to compute the inverse first. Uh so, we could also just do V inverse times A. Uh from a numerical analysis standpoint, this is very bad, but don't worry about it for now. We're going to get a better algorithm today anyway that doesn't involve matrices at all. But the nice thing is if computing V inverse, that takes n cubed time, but you only have to do it once.

So, if you have to do this many times, uh you can do this product in n squared time. You just have to maintain that V inverse for once and for all. Okay. Uh great. So, we got quadratic algorithms to go back and forth between these representations. That at least tells us it's doable, but uh we we of course need better than quadratic to improve on the naive um multiplication algorithm. So, that's what we're going to do. Uh in general, we can't do any better. But we have one freedom, which is we have said nothing about the x k's. We can choose them to be whatever they we want them to be. I keep saying x k equals k.

That seems fine. It's actually really bad choice for a reason we will get to. Uh but there is a choice where magically this transformation becomes easy, and you can do it in n log n time. Before we get there, uh I want to give you some motivation for how how this could possibly work. And as you might expect, even just from the n log n running time, we're going to be using divide and conquer. So, let's just think about how divide and conquer could work. Uh and I'm going to show you an idea and then we'll figure out how that idea could possibly work. At the mo- it doesn't work at the moment, but we will be able to choose the x case so that it works.

So, let's say uh the goal I mean, what we want to do is compute this uh v * a. Uh but I'm going to convert think of that back into matri- into polynomial uh land. So, our goal is to compute a of x uh for all x in some set x. Okay, this is uh taking a bunch of samples. So, uh the set x is just the set of the x case. But I'm going to change that set in a moment uh using recursion. So, I want to think So, the input to this algorithm is a polynomial a of x and it's a set capital x of positions that I'd like to evaluate that polynomial at. This is clearly more general than the problem we're trying to solve.

And I'm going to solve it with divide and conquer. So, in divide and conquer, there are three steps: divide, conquer, and combine. All right. So, uh let's start with divide. Here's the big idea. Uh I would say there are two natural ways to divide a vector. One is in the middle. That's what we've always seen with merge sort and divide and conquer uh and uh convex hull from last time. But there's another way which will work better here, which is the even entries and the odd entries. So, I'm going to divide into even and odd coefficients. So, let me write that down. Uh one of them is called a sub even of x.

That's a polynomial. It's going to have half the degree. So, it's going to be sum from k equals zero to I wrote n here, but I think I want something like n over two minus one n minus one over two, one of those things. Uh of a 2k x to the k. So, really really what I want, which is easier to write in the vector notation, I want all the even entries. Okay, I won't try to figure out what the last one is, but it's roughly n over two ish. I'll just write that. Uh you can go a little bit extra, it's fine. Uh if you define a sub n to be zero and a sub n plus one to be zero, all those to be zero, those terms will disappear.

So, uh the key thing here is I'm taking the even entries, but I'm I'm I'm not I don't have 2k up here. All right. So, this is the x to the zero term, this is the x to the one term, this is the x to the two term. So, there's a difference between x to the k's and the the a uh sub 2k. But uh I mean, just think about it in vector form. Don't worry about the algebra for now. We're going to have to worry about it in a second, but intuitively, what I want to do is extract from the vector of all the a i's uh these two vectors the odd coefficients in order n and the even coefficients in order. But I'm going to need the algebraic form in a moment for the combined step.

So, this should be 2k plus one x to the k. Okay. That's step one. Easy to do, linear time, of course. Uh let's jump ahead to step three, combine. In order to compute a of x from What I'd like to do is recursively compute a even of x and a odd of x for some values x. It's not going to be x and x, it's going to be some other set. And let's think about how I could compute a of x given some solutions to a even of x and a odd of x. So, this is step three. Combine. So, uh I would like a of x over here and I want a even of something and a odd of something and something in here. Uh anyone see the algebra?

Maybe start with this. I hear a mumble. Yeah. x squared x squared, exactly. Time for purple one. Getting better. Uh why x squared? Because we have this mismatch here. We have a sub 2k, we want x to the 2k. How could we do that? Well, we could put x squared to the 2k. Uh and you know, x squared Oh, sorry. x squared to the k is the same thing as x to the 2k. Okay. And so, magically, this transforms into the even entries of a of x. That's half of them. We do the same thing for the odd ones and we're almost there. Now we have a sub 2k plus one times x to the 2k, no plus one. So, how can I turn it at a plus one?

Multiply by x. Out here. Take the whole thing, multiply by x. Then I get all of the odd terms of a of x. I add these together. I get a of x. Okay, it's uh I mean, you could prove this more carefully, but uh sort of that's just algebra to see that this is correct. Once you have this, it tells you what I need to do is compute a even of x squared for all x in x. So, this is uh for x in x. There's a for loop for you. So, that's going to take linear time. If I already know this value and I already know this value, I do one multiplication, one addition, and boom, I get a of x. So, in the conquer step I want to uh recursively compute uh this I'll call it a even of y and a odd of y for y in x squared.

x squared is the set of squares of all numbers in x. Okay. So, I'm changing my set x. I started with a polynomial a and a set x. Recursively, I'm doing a different polynomial of half the degree half the number of terms. Uh but with a different set of the same size. Okay, I started with x. x squared has the same size as x, right? So, let's try to figure out how fast or slow this algorithm is. But that is a divide and conquer. That is going to be our golden ticket. Pretty simple. Uh but we're going to need another trick. So, uh I'm going to write a recurrence. Now, this this recurrence depends kind of on two things.

One is how many terms are there in a that we've been calling n. And the other is how many numbers are there in x. How many different places do I have to evaluate my polynomial? So, we've got t of n I always call it size of x. Okay. Uh so, divide and conquer goes hand in hand with recurrences. Generally, you've got the recursive part. So, that's just how big are the sub problems? How many are there? There are two sub problems. They have half the size in terms of n. But they have the same size in terms of x. So, all right. Two times cuz there's two sub problems, each of size n over two uh and size x.

Okay. Plus what goes here is however much it costs to do the divide step plus however much it costs to do the combine step, all the non-recursive parts. Well, this is just partitioning the vectors, linear scan, linear time. Uh this is we we talked about it's a constant number of arithmetic operations for each X. So, this costs order X time. This costs order N time. Right? So, in general, we get N plus X. Now, this is not again not a recurrence solvable by the master method because it has two variables. And uh So, probably the Usually, when you're faced with this sort of thing, you want to do kind of back of the envelope picture.

Uh draw a recursion tree. Good way to go. So, at the root, now I know that initially X equals N. Right? When I start out, I have N coefficients. I have N different positions I want to evaluate at them at because that's what I want to do to do this conversion from coefficients to samples. So, at the root of the recursion tree, I'm just going to write N. Order N work to get started and to the do the recursions. There are two recursive calls. One has Both have size N over two in terms of A. And they have size the same X, which is also known as N in those two recursions. So, in fact, the linear work here will be N and N.

And then we'll get N and N. X never goes down, so X always remains N. The original value of N. This is a bad recurrence. Uh there are N Sorry, there are log N levels. That's the good news. Once we get down to constant size, we can kind of stop. When there's only one coefficient, I know how to evaluate the polynomial with with just A0. That's easy. Uh so, uh down at the bottom here at the last level, so, this is height log N. The last level is just it's again going to be a whole bunch of N's. They're all the same N. Here, N is the original value of X cuz we haven't changed that. How many N's are there down here?

Hm? Two to the log N, also known as N. Yeah. Good. So, we had uh cuz we had log N levels, we had binary branching, so it's two to the number of levels, which is just N. So, this is N squared. All this work, still N squared. Clearly, what we need is for X to get smaller, too. Right? If X if in this recursion, let me uh in red draw the recursion I would like to have. If X became X over two here, that's the only change we'd need. Then N and X change in exactly the same way. And so, then we can just forget about X. It's going to be the same as N. Then we get two times N over two plus order N. Look familiar?

It is our bread and butter recurrence, merge sort recurrence. That's N log N. That's what we need to do somehow. When we convert our set X to X squared, I want X to get smaller. Is that at all plausible? Let's think about it. What's the base case? Um Keep things simple. Let's say the base case when uh X equals one, I'll just let X be Let's say I want to compute uh my A at one. Keep it simple. Okay? What if I What if I want two values in X? I'd like to have the feature that when I square all the values in X, so, I want two values, but when I square them, I only have one value. Solve for X. Yeah?

Negative one and one. Negative one and one. Tough one. Uh not bad. Good catch. Negative one and one. That could work. Right? What are negative one and one? They are the square roots of one. Right? Negative one squared is one. One squared is one. There's two square roots for every number. Two square roots for every number. Interesting. So, that means if I just keep taking square roots, when I square them, it collapses by factor of two. Uh let me Let me go to another board. Define something. You're all anticipating what's going to happen, but I'm going to say a collapsing set X uh or a set is collapsing if either um the size of X squared is the size of X divided by two uh and recursively X squared is collapsing.

Cuz I need this to work all the way down the recursion, or I need a base case, which is just X equals one. There's a single item in X. So, I happen to start with X equals the item one. It didn't have to be one. Could have been seven. It couldn't be zero cuz zero uh you won't get two numbers. There's only one square root of zero. Okay, so I lied a little bit. Other than zero, every number has exactly two square roots. So, what's the square root of negative one? I. I. So, complex numbers. So, if I take square roots of these guys, I get I and negative I. And again, I get minus one and one. Okay, that's when X equals four.

Turns out this is only going to work for powers of two. But hey, if N isn't a power of two, just round up to the next power of two. That only hurts me by a factor of two. Okay? Complex numbers. Okay, every time I said real number in the past, pretend I said complex number. Everything I said is still true. Actually, the root thing is only true when you allow complex numbers. Some polynomials have complex roots. Okay, so pretend I said complex. We're going to need complex numbers. This is why. Because when we start taking square roots, we immediately get uh complex numbers. Okay, next would be X equals eight.

Uh yeah. Square root of I. Square root of I, see if I can do it. Should be root two over two times one plus I. And then this one is just the square root of negative I is going to be root two over two times one minus I. And then we have all our old guys. Uh Oh, and then I can write plus or minus in front of each of these. Like, there weren't enough terms there. Okay, now I've got eight Sorry, I've got four numbers here. I've got four numbers there. How in the world could I remember this? Maybe I memorized it. No, I didn't memorize it. It's actually really easy to figure this out if you know geometry.

Geometry. Let's do geometry over here. It's convenient. I'm actually a geometer. Uh So, you know, complex numbers have two parts, right? The real part and the complex part. I'm going to draw that in what's called the complex plane, where we draw the real part here and I guess it's usually called the imaginary part on the Y axis. Every point in this plane is a complex number and vice versa. They're the same thing. Okay? So, what did we start with? We started with the number one. Number one uh would be here. It has no imaginary part, so it's on the X axis. That's This is the real line down here.

And it's at position one, which I'm going to just define to be right there. Okay? Then we got negative one. That's over here. Then we got I. That's here. One times I. Then we got negative I. That's here. Hm. Then we got root two over two times I plus one. That's here. Root two over two by root two over two. What is the property of root two over two, comma root two over two? It has distance exactly one to the origin. Right? If I draw this triangle, root two over two by root two over two. Uh I square this, I get a half. I square this, I get a half. I add them together, I get one. Take the square root, I still get one.

So, this distance is one. Hm, interesting. Uh and then I got the negative of that, which is over here. And negative of that. And then this is the with a negative Did I get it wrong? Yep. Sorry. It doesn't matter, but I'll think of it as I minus Kill it shock. I minus one. It's the same cuz I have the plus and minus, but I like the geometry. So, this point is uh negative root two over 2 by root 2 over 2 and then there's the negative over here. What properties do these points have? I heard a word. Unit circle. Good. Who said unit circle? Nice. It's a unit circle, right? Clearly that deserves a free at the end.

Okay. Unit circle. Hmm. Circle. It seems good. Uh, what's going on here is I took this number. I claimed it was the square root of I because it turns out if you take points on the unit circle in the complex plane, when you square a number, it's like doubling the angle relative to the x-axis. This is angle zero. This is angle, we call 45°. Uh, this is angle 90°. So when I square this number, I get 90°. That's why this number is a square. Sorry, it's a square root of I. I probably should have labeled some of these. This is I. This is minus I. This is minus one. And this is one. In general, we get something called uh Yeah.

So let's These are called the nth roots of unity. Unity is just a fancy word for one. Uh, one is here. And first we computed the square roots of one. They were minus one and one. Then we compute computed the fourth roots of one. All of these numbers, if you take the fourth roots, or sorry, if you take the fourth power, you get one. Then we computed the eighth roots of one. All of these numbers, if you take the eighth power, you get one again. So in general, nth roots of unity. We're going to assume n is a power of two, but this notion actually makes sense for any n. And they're just uniformly spaced around the circle, and if you know some geometry and how it relates to trig, you know that a general point on the circle is cos theta {comma} sin theta.

X coordinate is cos theta, y coordinate is sin theta. This is also a funny notation for complex numbers. Not so funny. This is the geometric interpretation of uh cos theta uh plus i sin theta. Okay, and if I want them uniformly spaced around the circle and I want to include this point, also known as theta equals zero, because when theta equals zero, cos theta is one, sin theta is zero, right? Uh, then So I want to say for theta equals to zero and then uh Here I'm going to get fancy. Tau over n, two tau over n, up to n minus one over n times tau. What's tau? Two pi. Thank you. This is modern notation.

Just over the last couple years. But I believe in tau so much, I got a tattooed on my arm. Okay? Tau is is the fundamental constant. Screw pi. Uh, none of that three and change. Six and change is where it's at. Uh So, tau. Clearly this is much nicer. Tau over n, not two pi over n. Tau is a whole circle. Okay? This is one nth of a circle, two nths of a circle, n minus one over nths of a circle. I didn't do n nths of a circle because that's also the same as zero. Okay? Now, why uh why did I introduce this notation? Cuz there's this other great thing called Euler's formula, uh which is that this this equals e to the i uh theta.

Right? Double check. It's It's so rare that I get to do real uh calculus. This is Euler's formula. E E for Euler. Another number, two and change. Uh, e to the i. This is funny cuz it's complex times theta is equal to cos theta plus i sin theta. This is the relation between exponentials and trigonometry. That's big thing Euler did. Cool. Uh, so what? Because this lets us understand how squares work. Not squares the shape, but squares the operation. When I take squares, uh So if I take e to the i theta, this is uh one of my roots of unity. Let me Let me expand out what theta is. So theta is some k times tau over n.

Yeah, let's do it this way first. So in reality we have uh k tau over n. When I square it, that's the same thing as putting the two right here. It's the same thing as e to the i times two theta. Bingo. I get what I was claiming that if I start at some angle theta relative to the x-axis, when I square the number, I just double the angle. This is why. Okay, this is obvious uh and just from regular algebra. And then this thing, Euler's formula, tells me that corresponds to doubling the angle on a circle. So it only works for points on the circle, but uh so when I go here, I get, you know, e to the i k uh I guess two k times tau over n.

Twice as far around the circle. All right. Uh, fine. What happens if I take this number and I square it? So this has a really big angle. This is uh It's 1/2 + 1/8, whatever that is. Uh, 5/8 times tau. When I double that angle, I go to here. Right? Now, this you might call it 10/8 or you might also call it 1/4. So there's a cuz when you go around the circle, you stay on the circle. So there's another thing going on, which is really um this is e to the i times two theta mod tau. Usually we think of mods as relative to integers, but uh the What I mean is every time I add a multiple of tau, nothing changes.

If I go around the circle five times and then do something, it's the same as just doing the something. Okay, so I kind of need that. Um and this is true because uh e to the i tau equals one. You may know it as e to the i pi equals negative one, but clearly this is the superior formula. So superior, I got a tattooed on my other arm. Uh It's amazing what you can do with a laser printer and a temporary tattoo kit. Sadly, these won't last, but definitely try it at home. Um Cool. So e to the i tau equals one. So going around the circle, same thing as not. All right. So uh you can draw on this picture for every number, what is its square?

Um and in general, if you look at these four guys, their squares are just going to be these two guys. If you look at these four guys, their squares are going to be among these four guys. So I started with eight guys, I square them, I get four, I square them, I get two, I square them, I get one. That's how we constructed it. Uh but you can see it works not only for this eight-point set that we constructed sort of by hand, uh but it works for the nth roots of unity as long as n is a power of two, this set of points will be collapsing. Okay, so uh if n is a power of two, some integer k, then uh nth roots of unity are collapsing according to this definition.

And that's what we want. Then this divide and conquer algorithm runs in n log n time because every time we square it, the set x, we reduce its size by a factor of two. So we get t of n equals two times t of n over two plus n plus order n, and that's order n log n. And so this whole thing, we compute, in other words, we set xk to be um e to the i k tau over n. Now, I should say how to compute that, but let's just say that's given to you for free. It takes constant time to compute each root of unity. In fact, again, we only need to do this once and for all uh for each value of n. So you can think of it as just being part of the algorithm.

These are the xks we use. I said xk could be anything we want as long as they're all different. So, I'm going to choose them to be N uniformly spaced points around the complex unit circle. And then magically, this algorithm runs in N log N time. It's pretty cool. Uh intuitively, you think of real numbers X squared, of course it has the same size as X. But, once you go to complex numbers, there's this nifty trick where you start with 1/N of the circle and you uniformly space points. After the first level of recursion, you'll only have to be be dealing with N/2 of those points, namely the even ones, also known as the N/2 roots of unity.

And after the next level of recursion, it's the N/4 roots of unity and so on. So, this recursion is well defined. When you have a vector of size N, you just have to deal with the N roots of unity and you're happy. That is fast Fourier transform. That algorithm with these XIs is FFT. So, let me write this somewhere. It kind of snuck up on us. This is the algorithm we were aiming to to find. Fast Fourier transform. Uh is that divide and conquer algorithm on the right. I'll write it abstractly uh for something called the DFT, the discrete Fourier transform. Is the corresponding mathematical transformation.

Fast is about an algorithm. Discrete is about discrete math. Uh so, DFT is uh this thing that we wanted to compute, which was basically the product V * A. Remember, V was the Vandermonde matrix. Uh but, and it was a it depended on all these XKs. Uh and we're going to set XK to be this E to the I K tau over N. So, uh if you remember the uh V K uh VJK here was uh XJ to the Kth power. So, this just becomes uh E to the I J K tau over N. Uh it's a little funny these are all consecutive cuz this is a totally different, but uh that's the matrix. If you take that matrix times a vector, that is called the discrete Fourier transform of that vector.

And FFT is a way to compute it in N log N time. You just run this algorithm and for those XKs, it'll just work in N log N time. Cool. But, if you remember way back to the beginning, what we needed is a way this converts a coefficient vector into a sample vector. Then we can multiply the matrices, but we then need to trans Sorry, multiply the polynomials. Then we need to transform the sample vector that results back into a coefficient vector. So, we're only half done. I only have 15 minutes. Luckily, the other half is almost identical to this half. So, let's do that next. Maybe over here. So, we've got our great divide and conquer algorithm.

What we need now Let me give you the polynomial multiplication algorithm. All right, let's call this Let's write more exotic. Fast polynomial multiplication. Fast meaning N log N. Let's say that we're given two uh polynomials A and B represented in coefficient form. What we need uh is I'll call A star which is the result of running FFT on A. What's the it's the discrete Fourier transform of A. B star uh do the same thing. So, we know what this means is convert A from a coefficient vector into a sample vector. Convert B from a coefficient vector into a sample vector. Now, I have the samples of A star at the Nth roots of unity.

These guys. And I have the the samples of B at the exact same points, the Nth roots of unity. So, I can compute C star the the transform version, the the DFT of C is just the uh I mean, C star K equals A star K * B star K. This is the multiplication algorithm uh for sample vectors, right? We started with that. That has that's linear time. And then, the missing piece is I need to recompute C, which is the inverse fast Fourier transform of C star. So, this is the missing link, so to speak. We need to be able to go backwards in this transformation. Good news is the algorithm's not going to change.

What we're computing isn't going to change. Uh all that's going to change are the XKs. Why? Because uh remember uh from the top, what Right now, we know how to compute V * A. What we now need to compute is V inverse * A. So, the only question is what is V inverse? This matrix has a super special structure. It's symmetric, looks lots of crazy lots of points on a circle. Maybe V inverse has a nice structure. And it does. Claim is V inverse is V complex conjugate divided by N. Uh what's complex conjugate? Uh for a geometer, it's reflection through the X axis. For an algebraic person, uh huh A + I B, the complex conjugate is A - I B.

Okay, so just apply that to every entry in the matrix and then divide all the entries by N. You get the inverse. Cool. Very cool. Because uh what this tells us is we run exactly the same algorithm and do exactly the same transformation. If we want to do the inverse, we can actually just use V, but with a different choice of XK, namely um for the inverse, call it XK inverse. Uh we just take the complex conjugate of this thing which turns out to be um E to the minus I J K tau over N and then divide the whole thing by N. Okay, I'm using a fact here, which is that the complex conjugate of this number is actually just you put a minus sign here.

Why does that hold? Because geometry, right? If you uh theta is usually measuring the counterclockwise angle from the X axis. If you take the complex conjugate, you go from up here to down here. The reflection through the X axis. That's the same thing as if you measure theta as a clockwise angle from the X axis. That's the same thing as negating the angle. Okay, so that's just a little geometry. You can prove it algebraically, although I don't know how uh off hand. It's not not hard. Uh so, if I want to take some angle and then flip it through the X axis, it's the same as the negative of the angle.

So, complex conjugate of this number is same thing with a minus sign. And then we have to divide by N. If I just uh Did I lie? Uh I can't divide by N, sorry. It's in the wrong spot. I use these XKs. And then uh I apply the transform. I take this uh thing, I get not quite V inverse, but I end up getting N V inverse. I multiply that by my A star. That's going to give me N * A. Okay? Uh So, uh then I just take that vector, I divide by N. Boom, I've got the inverse transform. So, this is how you do uh inverse fast Fourier transform. You just flip the sign in the exponent in the XKs. Then you do the same uh matrix vector product and then you divide by N.

And then you've done the inverse. So, that's how you do uh if you believe this claim, that's how you do this last step. Question? What's the J in the X A in there? Oops, no J, sorry. Uh I was imagining the these guys. Yeah, it's just K. Thank you. No questions? Okay, so what remains is to prove this claim. Everybody happy if I uh I should probably have better Well, anyway. It's not the best. I'm going to call this uh VK prime uh XK prime. Then when I do that when I plug that in, I get a different matrix V prime. And what I'm claiming what this claim says is that V prime is equal to N times V inverse.

Okay, so I apply the same FFT algorithm, but with V prime instead of V, then I get not quite the product I want, but just N times the product I want. Divide every term by N, and we get the inverse. This cool thing about complex numbers here, we get another cool thing. All right, uh but we have to prove this claim. So, let's do a little bit of algebra. No pain, no gain, right? Uh good. So, uh let's look at VJK prime. So, Oh, sorry. So, let's uh Fine. Let's look at P, the product of V and V complex conjugate. Okay, what I was calling V prime up there. Uh I claim that this thing is N times the identity matrix with ones down the diagonal and zeros everywhere else.

Okay, so let's look at this product. In general, let's look at the uh say the JKth item in the product. That's going to come from row J of V uh dot product with column K of V complex conjugate. Now, the matrices here are symmetric, so actually rows and columns are the same, but that's the general definition of a cell in the product of two matrices. Uh so, let's write it out as a summation. We have from M equals zero. It's so hard not to use I for my summations. It's the only class I have to do it cuz I is already taken, but I guess I used to use capital I, but uh we'll use M cuz I is complex number today.

Uh so, we have um E to the I tau J M over N times E to the minus I tau M K over N. I don't know why I changed the order. I put the tau here instead of there, but same thing. Okay, this is just the for every uh position M in the cell and corresponding position M in sorry, M in the row, corresponding position M in the column, I have JM and I have MK. Again, the order doesn't matter, it's symmetric, but I'm getting it right here. This is we're using this formula. Okay, I put a minus sign here because this is V com V complex conjugate. Okay, so now I just do some algebra. These share a lot, they share I, they share M, and they share the divided by N.

Okay, so this is sum M equals zero N minus one E to the I Oh, they also share tau. Uh tau M over N times J minus K. Please correct me if I make any mistakes. Uh cool. So, it depends how J and K relate, of course. Um If J equals K, that's also that's also known as something on the diagonal. I want this I want the matrix N N N N 0 0, right? So, J equals K, that's the diagonal, that's where I want to get N. And indeed, if J equals K, this becomes zero, so all this becomes zero. E to the zero is one. And so I'm summing up one N times, I get N. Okay, cool. It's one case. This is N if J equals K. And somehow I claim that everywhere else I get zeros.

So, let's prove that. So, if J does not equal K, I'm going to rewrite this a little bit. J and K are fixed. Okay, M is changing in the sum. So, I want to write this as sum M equals zero to N minus one E to the I tau uh J minus K over N times M. Okay, in other words, this thing raised to the Mth power. What is this series? One word? Geometric. Thank you. This is a geometric series. And uh I guess I should have waited uh to give you the frisbee until you tell me how do you solve a geometric series of with a finite term? So, think of this as Z to the M. Do you know the formula? It's E to the I tau uh Just Z.

Oh, this is Z. Z to the N minus one. Z to the N minus one, almost. Over Z minus one, yep. That's if you have sum of Z to the K, K equals zero to N minus one, that's that. It's in the appendix of your textbook. So, we just plug that in, uh and we get uh oh boy. E to the There you go. E to the I tau J minus K over N to the Nth power minus one over E to the I. Actually, the denominator doesn't really matter because this is supposed to be zero. So, it's all about the numerator. Uh so, but it's same thing minus one. Okay? Where's my red? Red. The N cancels with the N. This is an integer not equal to zero.

So, we have E to the I tau to an integer power. What's E to the I tau? One. Okay? Convenient that I had that there. One minus one is zero, so we get zero. Satisfying. Okay? So, that proves this claim. We proved that on the diagonal we get N cuz we had N copies of one. Off the diagonal we get zero. Like this. Therefore, V complement uh sorry, V complex conjugate times N is V inverse. Therefore, this algorithm actually computes the inverse fast Fourier transform. So, that's it for algorithms today. Um but let me quickly tell you about some applications. Uh you've probably taken other classes that use applications of fast Fourier transform, so I will just summarize.

Uh if you've ever edited audio, you probably did it in uh unless you're just like pasting audio clips together, uh you probably did it in what's called frequency space. So, you know that uh as I talked about in the beginning, when we're measuring where the membrane on this microphone goes over time, that is in ti- in the time domain. For every time, we sample where physically this thing is. If you apply I think the way I define it here is the inverse fast Fourier transform, usually it's called Fourier transform. Uh to that uh time domain vector, you get a new vector. Now, it's a complex vector.

See, you can't start with real numbers, you get complex numbers. So, uh for every uh position in the vector, what it corresponds to, the the X axis is no longer time, now it's frequency. For every frequency, you're measuring uh essentially, you're viewing this this vector, the waveform, as a bunch of trigonometric functions. Say, sine of something times theta. If you look at one of the entries in the vector, and it's a complex number, if you compute the magnitude of the complex number, the length of the vector, uh of length of that two-coordinate vector, that is how much uh stuff of that frequency you have.

And then the angle of the vector in 2D is uh how that uh trigonometric function is shifted in time. So, if you take a pure note, like if I was uh, playing a bell and it was exactly C major, you uh, you know, it looks it looks really wavy. It's actually a nice perfect uh, sine curve with some offset depending on when I hit it. Um, and then if you apply the Fourier transform, what you get is zeros everywhere except for the one frequency that's appearing and there you get one and everywhere else you get zero. Well, one possibly rotated depending on the phase. And you can take any audio stream, convert it via Fourier transform, do manipulations there.

For example, you've probably heard of high-pass filters that removes all the high frequencies or low-pass filters remove all the low frequencies. You just convert to the space, you zero out the parts you want and then you convert back with inverse Fourier transform. Uh, if you've used Adobe Audition or Audacity, they can all do these things. Uh, and there are tons of contexts where converting to Fourier space makes life easy. And in general, if you have any time-based signal, you should always think about what do you get with FFT when you transform to uh, frequency-based signal and you can do lots of cool things you couldn't do otherwise.

And it only takes n log n time plus people do it in hardware. There's a fast implementation called FFTW, the fastest Fourier transform in the west, which is made here at MIT bunch of years ago and is still the best uh, software implementation of FFT. So, people use it everywhere. Uh, your head your noise-canceling headsets probably use it. MP3 uses it. It's a cool algorithm.