1
00:00:00,499 --> 00:00:01,950
The following
content is provided
2
00:00:01,950 --> 00:00:06,060
by MIT OpenCourseWare under
a Creative Commons license.
3
00:00:06,060 --> 00:00:08,230
Additional information
about our license
4
00:00:08,230 --> 00:00:10,490
and MIT OpenCourseWare
in general,
5
00:00:10,490 --> 00:00:12,160
is available at ocw.mit.edu.
6
00:00:17,247 --> 00:00:19,330
PROFESSOR: I thought I
would, in this last lecture
7
00:00:19,330 --> 00:00:23,780
before the break, speak
about one specific topic.
8
00:00:26,660 --> 00:00:30,050
It's often referred to
as a fast Poisson solver,
9
00:00:30,050 --> 00:00:33,920
so what does Poisson mean?
10
00:00:33,920 --> 00:00:36,350
Poisson means
Laplace's equation.
11
00:00:36,350 --> 00:00:39,870
So, this is the
five-point Laplacian,
12
00:00:39,870 --> 00:00:43,700
which could be some other
discrete Laplace matrix,
13
00:00:43,700 --> 00:00:46,760
but let's take the one we know.
14
00:00:46,760 --> 00:00:52,660
So we're in two dimensions,
and you use Poisson's name,
15
00:00:52,660 --> 00:00:55,030
instead of Laplace's
name, when there's
16
00:00:55,030 --> 00:00:57,560
a non-zero right-hand side.
17
00:00:57,560 --> 00:01:02,210
So otherwise, it's a Laplace
solver, but here Poisson.
18
00:01:02,210 --> 00:01:02,840
OK.
19
00:01:02,840 --> 00:01:05,170
So, remember that
right-hand side comes
20
00:01:05,170 --> 00:01:10,810
from maybe a right-hand side
f of x, y in the differential
21
00:01:10,810 --> 00:01:17,280
equation, but it also comes from
non-zero boundary conditions,
22
00:01:17,280 --> 00:01:21,850
because non-zero boundary
conditions, when the five
23
00:01:21,850 --> 00:01:26,580
points hit a boundary, that
known value was moved over
24
00:01:26,580 --> 00:01:29,480
to the right-hand side
and becomes part of f.
25
00:01:29,480 --> 00:01:35,370
So f comes from the non-zero
boundary conditions, as well as
26
00:01:35,370 --> 00:01:37,730
the non-zero right-hand side.
27
00:01:37,730 --> 00:01:39,840
OK.
28
00:01:39,840 --> 00:01:45,580
Important problems, but special
on a square or a rectangle
29
00:01:45,580 --> 00:01:50,040
or a cube or a box,
so we're speaking
30
00:01:50,040 --> 00:01:53,760
about special geometry.
31
00:01:53,760 --> 00:02:00,740
Today, as we've been doing,
I'll take the case on a square,
32
00:02:00,740 --> 00:02:05,410
and you will see that the
whole idea would not fly,
33
00:02:05,410 --> 00:02:12,060
if we were on an ellipse
or something like that.
34
00:02:12,060 --> 00:02:18,420
But a lot of problems on
rectangular domains do appear
35
00:02:18,420 --> 00:02:22,510
in applications,
or we could use --
36
00:02:22,510 --> 00:02:27,370
I hope you always think now
about possible preconditioners.
37
00:02:27,370 --> 00:02:29,850
Any time you have
something fast,
38
00:02:29,850 --> 00:02:33,700
it's a candidate to
be a preconditioner
39
00:02:33,700 --> 00:02:35,890
for a real problem.
40
00:02:35,890 --> 00:02:39,280
The real problem might
not be on a square,
41
00:02:39,280 --> 00:02:44,140
or the real problem might not
have the constant coefficient
42
00:02:44,140 --> 00:02:48,710
that we have in the Laplacian.
43
00:02:48,710 --> 00:02:52,970
In that case, you're not
solving the exact problem,
44
00:02:52,970 --> 00:02:56,720
but one that could be
reasonably close to it.
45
00:02:56,720 --> 00:02:59,730
OK.
46
00:02:59,730 --> 00:03:03,085
So we've discussed the
solution to this problem,
47
00:03:03,085 --> 00:03:04,460
and actually I
have a little more
48
00:03:04,460 --> 00:03:08,640
to say about the movie
that is now on the website,
49
00:03:08,640 --> 00:03:11,320
because I'm quite
excited about that movie.
50
00:03:14,320 --> 00:03:16,050
I'll come to the
movie in a second.
51
00:03:16,050 --> 00:03:20,830
Let me just say what
today's lecture would be.
52
00:03:20,830 --> 00:03:26,750
The key idea here is that the
eigenvalues and eigenvectors
53
00:03:26,750 --> 00:03:31,630
of this giant matrix of order
N squared by N squared --
54
00:03:31,630 --> 00:03:34,690
size is N squared by N squared.
55
00:03:34,690 --> 00:03:37,380
The eigenvalues and the
eigenvectors are known.
56
00:03:37,380 --> 00:03:40,270
First of all, they're known.
57
00:03:40,270 --> 00:03:44,340
The eigenvectors are nice
discrete sine functions;
58
00:03:44,340 --> 00:03:50,080
they're sines,
because I'm assuming
59
00:03:50,080 --> 00:03:52,350
they come to zero
at the boundary;
60
00:03:52,350 --> 00:03:56,410
so that's why I have a
sine, rather than a cosine.
61
00:03:56,410 --> 00:04:00,260
First, they're
known, and second, we
62
00:04:00,260 --> 00:04:05,680
can work with them very
quickly, using the FFT.
63
00:04:05,680 --> 00:04:10,710
So the point is that
it's quite exceptional;
64
00:04:10,710 --> 00:04:15,290
in fact, I don't think I
know any comparable example,
65
00:04:15,290 --> 00:04:18,990
in which a linear system is
solved by using the eigenvalues
66
00:04:18,990 --> 00:04:21,100
and eigenvectors.
67
00:04:21,100 --> 00:04:23,870
Usually eigenvalues
and eigenvectors,
68
00:04:23,870 --> 00:04:26,810
they pay off for
differential equations
69
00:04:26,810 --> 00:04:29,160
that are growing in time.
70
00:04:29,160 --> 00:04:32,170
Then it is worth computing
them, because then you can just
71
00:04:32,170 --> 00:04:35,320
multiply by e to the lambda*t,
and you know what's happening
72
00:04:35,320 --> 00:04:35,820
later.
73
00:04:38,600 --> 00:04:42,860
Eigenvectors, eigenvalues have
other purposes, but very, very
74
00:04:42,860 --> 00:04:46,230
rarely are they used to
solve a linear system.
75
00:04:46,230 --> 00:04:49,360
I mean, it's usually
far more work.
76
00:04:49,360 --> 00:04:51,800
And of course, it would
be incredibly more work
77
00:04:51,800 --> 00:04:54,380
if we had to find the
eigenvalues and eigenvectors,
78
00:04:54,380 --> 00:04:57,160
but for this problem
we know them.
79
00:04:57,160 --> 00:05:01,010
And it also would be incredibly
more work if the matrix
80
00:05:01,010 --> 00:05:05,130
of eigenvectors,
the basis matrix,
81
00:05:05,130 --> 00:05:09,600
the key matrix that
I'll denote by S --
82
00:05:09,600 --> 00:05:12,850
so the eigenvectors
go in a matrix S;
83
00:05:12,850 --> 00:05:17,430
the eigenvalues go in a
matrix capital lambda;
84
00:05:17,430 --> 00:05:19,000
so we know lambda.
85
00:05:19,000 --> 00:05:22,350
It's going to be a simple
matrix, just diagonal,
86
00:05:22,350 --> 00:05:25,520
got those N numbers -- N
squared numbers, I guess,
87
00:05:25,520 --> 00:05:28,160
because we're of size N squared.
88
00:05:28,160 --> 00:05:31,570
But these eigenvectors we know.
89
00:05:31,570 --> 00:05:35,870
So we know them, and we can
compute quickly with them,
90
00:05:35,870 --> 00:05:40,270
using the FFT, or using,
you might want me to say,
91
00:05:40,270 --> 00:05:45,210
fast sine transform,
discrete sine transform,
92
00:05:45,210 --> 00:05:48,180
rather than Fourier
transform, which
93
00:05:48,180 --> 00:05:52,400
we think of as doing
the complex exponential.
94
00:05:52,400 --> 00:05:58,890
So this is a small special
fast Fourier world.
95
00:05:58,890 --> 00:06:01,080
It's a special
fast Fourier world,
96
00:06:01,080 --> 00:06:07,690
in which the FFT and the
related sine and cosine
97
00:06:07,690 --> 00:06:13,290
give us a quick answer,
faster than elimination,
98
00:06:13,290 --> 00:06:16,240
because you all
know, it's n log n,
99
00:06:16,240 --> 00:06:19,970
if n is the number of
Fourier components,
100
00:06:19,970 --> 00:06:23,490
and that's hard to beat.
101
00:06:23,490 --> 00:06:28,170
Then I'll mention also,
for this same problem,
102
00:06:28,170 --> 00:06:33,640
there is another way in
which it can be simplified.
103
00:06:33,640 --> 00:06:41,230
It's not a Fourier way,
just a direct combining
104
00:06:41,230 --> 00:06:44,260
neighboring equations,
so that'll be number two.
105
00:06:44,260 --> 00:06:46,870
OK, but mostly the lecture
is about number one.
106
00:06:49,670 --> 00:06:53,250
The best example I know
in which you would use
107
00:06:53,250 --> 00:06:56,220
eigenvectors/eigenvalues
to solve
108
00:06:56,220 --> 00:07:00,420
an ordinary linear system,
and I'll say in a word
109
00:07:00,420 --> 00:07:04,750
just how you do it, and then
what these eigenvectors are.
110
00:07:04,750 --> 00:07:08,030
OK.
111
00:07:08,030 --> 00:07:09,180
Pause.
112
00:07:09,180 --> 00:07:12,330
Time out to say something
about the movie.
113
00:07:12,330 --> 00:07:18,200
So that movie that's
now on the website
114
00:07:18,200 --> 00:07:27,150
does sparse elimination, and
the example it takes is K2D,
115
00:07:27,150 --> 00:07:30,700
and you can make it 8
squared by 8 squared,
116
00:07:30,700 --> 00:07:34,780
10 squared by 10 squared,
20 squared by 20 squared,
117
00:07:34,780 --> 00:07:40,490
because it shows the order
that the nodes are eliminated
118
00:07:40,490 --> 00:07:47,040
and the graphs of
non-zeros in the matrix.
119
00:07:47,040 --> 00:07:49,560
It's a bit slow.
120
00:07:49,560 --> 00:07:55,900
If you do 20 by 20, you
have to go away for lunch,
121
00:07:55,900 --> 00:08:01,390
well maybe not lunch, but at
least coffee before it's done,
122
00:08:01,390 --> 00:08:05,740
but when it's done, it
counts the number of --
123
00:08:05,740 --> 00:08:14,920
it shows the non-zeros that
are in the elimination,
124
00:08:14,920 --> 00:08:17,930
in the factor L
from elimination,
125
00:08:17,930 --> 00:08:20,750
and it counts the
number of non-zeros,
126
00:08:20,750 --> 00:08:24,730
and I was just talking to
Persson about also getting it
127
00:08:24,730 --> 00:08:27,260
to count the number
of actual flops.
128
00:08:29,810 --> 00:08:33,610
Well, why am I interested?
129
00:08:33,610 --> 00:08:41,170
I'm interested, because I
don't know what power of N
130
00:08:41,170 --> 00:08:43,960
those numbers are growing with.
131
00:08:43,960 --> 00:08:47,350
I don't know whether the number
of non-zeros -- and I did 10,
132
00:08:47,350 --> 00:08:56,730
20, 30, and it looked not too
far from the power capital N
133
00:08:56,730 --> 00:09:05,240
cubed, but the notes say
for nested dissection,
134
00:09:05,240 --> 00:09:15,540
which would be another
ordering, N squared log N. So,
135
00:09:15,540 --> 00:09:19,670
and of course, what power we
get depends on what algorithm we
136
00:09:19,670 --> 00:09:23,250
use for ordering, so nested
dissection is one ordering,
137
00:09:23,250 --> 00:09:28,700
which hopefully we could
put into another movie.
138
00:09:28,700 --> 00:09:35,390
The movie now has exact
minimum degree, real MMD,
139
00:09:35,390 --> 00:09:41,520
which takes as the
next node the one
140
00:09:41,520 --> 00:09:46,670
with absolutely the minimum
degree, not just close to it.
141
00:09:46,670 --> 00:09:51,580
Anyway, have a
look at that movie,
142
00:09:51,580 --> 00:10:00,130
and if you have
any interest, see
143
00:10:00,130 --> 00:10:03,510
how the count increases
as n increases,
144
00:10:03,510 --> 00:10:07,720
and also you could
change, slightly adapt,
145
00:10:07,720 --> 00:10:11,630
the algorithm that
creates the ordering,
146
00:10:11,630 --> 00:10:15,370
creates the permutation
and see what happens there.
147
00:10:15,370 --> 00:10:20,540
There's a lot to do with that,
and it's a pretty fundamental
148
00:10:20,540 --> 00:10:21,430
problem, actually.
149
00:10:21,430 --> 00:10:26,930
We're talking there about what
MATLAB's backslash operation
150
00:10:26,930 --> 00:10:29,970
will do for this equation.
151
00:10:29,970 --> 00:10:33,100
So MATLAB'S backslash
operation will use elimination;
152
00:10:33,100 --> 00:10:35,470
it won't use fast
Poisson solvers,
153
00:10:35,470 --> 00:10:38,760
but now let me come to
the fast Poisson solver.
154
00:10:38,760 --> 00:10:39,870
OK.
155
00:10:39,870 --> 00:10:42,800
So I guess the main
point is I have
156
00:10:42,800 --> 00:10:45,910
to say what are the
eigenvalues and eigenvectors,
157
00:10:45,910 --> 00:10:47,270
and how do they get used.
158
00:10:47,270 --> 00:10:49,250
So let me say, how
do they get used.
159
00:10:49,250 --> 00:10:52,390
So how can I use
eigenvalues and eigenvectors
160
00:10:52,390 --> 00:10:55,870
to solve a problem like that.
161
00:10:55,870 --> 00:10:58,080
Let me just call it
K rather than K2D.
162
00:10:58,080 --> 00:11:02,380
So K*U equals F. OK.
163
00:11:04,970 --> 00:11:06,740
By eigenvectors.
164
00:11:09,780 --> 00:11:12,100
OK, there are three steps.
165
00:11:12,100 --> 00:11:12,890
Step one.
166
00:11:15,400 --> 00:11:20,530
Expand the right-hand
side as a combination
167
00:11:20,530 --> 00:11:22,070
of the eigenvectors.
168
00:11:22,070 --> 00:11:22,850
OK.
169
00:11:22,850 --> 00:11:28,840
So expand F, this
right-hand side vector,
170
00:11:28,840 --> 00:11:34,250
as some combination of
the first eigenvector,
171
00:11:34,250 --> 00:11:41,570
maybe I'm going to call it
y_1, second eigenvector,
172
00:11:41,570 --> 00:11:48,412
n-th eigenvector, OK, good.
173
00:11:48,412 --> 00:11:49,620
That means -- what do I mean?
174
00:11:49,620 --> 00:11:54,000
I mean you have to find those
c's, that's the job there.
175
00:11:54,000 --> 00:11:58,170
Find the coefficients.
176
00:11:58,170 --> 00:12:03,780
So that's a job, a numerical --
it's a linear system to solve
177
00:12:03,780 --> 00:12:05,860
and we'll see what
it amounts to.
178
00:12:05,860 --> 00:12:08,230
OK, but suppose
the right-hand side
179
00:12:08,230 --> 00:12:10,300
is a combination of
the eigenvectors,
180
00:12:10,300 --> 00:12:11,600
how can you use that?
181
00:12:11,600 --> 00:12:14,320
Well, step two is
the real quick step.
182
00:12:14,320 --> 00:12:30,910
Divide each c_i by the
eigenvalue lambda_i.
183
00:12:30,910 --> 00:12:36,580
OK, so it's by eigenvector,
so I'm assuming that K*y_i is
184
00:12:36,580 --> 00:12:41,890
lambda_i*y_i and that
we know these guys.
185
00:12:41,890 --> 00:12:44,670
So this is known.
186
00:12:44,670 --> 00:12:48,820
And now the question, I'm just
saying, how do we assume known?
187
00:12:53,340 --> 00:12:55,250
So my question now
is how do we use it?
188
00:12:55,250 --> 00:12:59,540
OK, step one -- the idea is
going to be write everything
189
00:12:59,540 --> 00:13:01,850
in terms of eigenvectors.
190
00:13:01,850 --> 00:13:04,490
Work with the eigenvectors,
because if I've
191
00:13:04,490 --> 00:13:09,990
got eigenvectors,
the step is scalar;
192
00:13:09,990 --> 00:13:12,610
I just divide these
numbers by those numbers,
193
00:13:12,610 --> 00:13:15,370
and then I've got the answer.
194
00:13:15,370 --> 00:13:21,230
And then construct -- the
correct answer will be U will
195
00:13:21,230 --> 00:13:32,680
be c_1 over lambda_1 y_1 and
c_2 over lambda_2 y_2 up to c_n
196
00:13:32,680 --> 00:13:41,120
over lambda_n y_n, a combination
of those same eigenvectors with
197
00:13:41,120 --> 00:13:43,740
the same coefficients,
just divided by lambda.
198
00:13:47,310 --> 00:13:50,790
But this is, of course,
another numerical job;
199
00:13:50,790 --> 00:13:54,540
this is like adding
up a Fourier series;
200
00:13:54,540 --> 00:13:56,650
this is like finding the
Fourier coefficients,
201
00:13:56,650 --> 00:14:00,980
this is like
reconstructing the input.
202
00:14:00,980 --> 00:14:04,150
Only because I've
divided by lambda_i,
203
00:14:04,150 --> 00:14:07,080
I'm getting the
output here is U,
204
00:14:07,080 --> 00:14:10,700
when the input was F.
And do you see that that
205
00:14:10,700 --> 00:14:13,690
is the correct answer?
206
00:14:13,690 --> 00:14:16,840
All I have to do is
check that K*U equals F.
207
00:14:16,840 --> 00:14:26,040
So check that this answer from
step three is the right answer.
208
00:14:26,040 --> 00:14:34,960
OK, so I multiply by K.
When I multiply y_1 by K,
209
00:14:34,960 --> 00:14:39,850
a factor lambda_1 appears, the
eigenvalue; it cancels that;
210
00:14:39,850 --> 00:14:42,480
well that's y divided,
so it would cancel,
211
00:14:42,480 --> 00:14:44,640
and I have c_1*y_1.
212
00:14:44,640 --> 00:14:49,940
When I multiply this by
K, K*y_2 is lambda_2*y_2;
213
00:14:49,940 --> 00:14:54,250
cancel the lambda_2's, and
you're left with c_2*y_2,
214
00:14:54,250 --> 00:14:55,000
and so on.
215
00:14:55,000 --> 00:15:02,250
So, when I multiplied by
K, I got F. That's it.
216
00:15:02,250 --> 00:15:09,760
So that's the whole idea
written out, but now,
217
00:15:09,760 --> 00:15:14,430
what actual computations go
into steps one and three?
218
00:15:14,430 --> 00:15:15,840
Step two is pretty simple.
219
00:15:15,840 --> 00:15:19,740
Well, actually this is
a good way to look it.
220
00:15:19,740 --> 00:15:23,790
I want to write that same
algorithm in matrix language.
221
00:15:23,790 --> 00:15:29,790
OK, so in matrix form.
222
00:15:29,790 --> 00:15:31,850
We have the matrix
of eigenvectors,
223
00:15:31,850 --> 00:15:37,320
and that's what I'm
calling S. And it's
224
00:15:37,320 --> 00:15:43,320
got the eigenvectors y_1,
y_2, y_n in its columns.
225
00:15:43,320 --> 00:15:52,090
And the eigenvalue matrix,
we need a name for that too,
226
00:15:52,090 --> 00:15:54,860
and that we decided
to call lambda,
227
00:15:54,860 --> 00:16:01,480
and that's got the
eigenvalues on its diagonal.
228
00:16:01,480 --> 00:16:08,030
So this is 18.06,
linear algebra.
229
00:16:08,030 --> 00:16:16,020
The matrix of eigenvectors,
if I multiply K by S,
230
00:16:16,020 --> 00:16:21,770
then I'm multiplying K by
all its little eigenvectors,
231
00:16:21,770 --> 00:16:26,280
and K times this
gives me lambda_1*y_1,
232
00:16:26,280 --> 00:16:29,250
K times y_2 gives
me lambda_2*y_2,
233
00:16:29,250 --> 00:16:38,250
K*y_n is lambda_n*y_n, and if
I look to see what this is,
234
00:16:38,250 --> 00:16:44,060
this is the same as y_1 to
y_n multiplied by lambda.
235
00:16:44,060 --> 00:16:47,070
If I just multiply on
the right by lambda,
236
00:16:47,070 --> 00:16:49,420
it will take lambda_1
times the first column,
237
00:16:49,420 --> 00:16:53,650
lambda_2 times the second,
lambda_n times the last,
238
00:16:53,650 --> 00:16:56,050
which is what we want,
so it's S*lambda.
239
00:16:58,660 --> 00:17:04,810
This is all n eigenvalues and
eigenvectors in one matrix
240
00:17:04,810 --> 00:17:07,330
equation, that's all that is.
241
00:17:07,330 --> 00:17:17,790
It's just K*S equal S*lambda_i
just says this for all i
242
00:17:17,790 --> 00:17:20,470
at once, all i at the same time.
243
00:17:20,470 --> 00:17:21,320
OK.
244
00:17:21,320 --> 00:17:26,000
So if I use these
matrices in describing
245
00:17:26,000 --> 00:17:29,040
steps one, two,
three, I'll see what's
246
00:17:29,040 --> 00:17:32,740
happening matrix language.
247
00:17:32,740 --> 00:17:34,770
OK, let me just do that.
248
00:17:34,770 --> 00:17:41,550
Step one: step one
is looking for F
249
00:17:41,550 --> 00:17:46,230
as a combination of
the columns of S.
250
00:17:46,230 --> 00:17:52,220
So step one is just
F equals S times c.
251
00:17:52,220 --> 00:18:00,110
The vector of coefficients
multiplies the columns of S
252
00:18:00,110 --> 00:18:07,700
and adds to give
F. Then step two,
253
00:18:07,700 --> 00:18:15,310
which just divides everything
by -- divides by the lambdas.
254
00:18:15,310 --> 00:18:20,310
Step two just creates
lambda inverse S*c.
255
00:18:22,850 --> 00:18:30,880
So I took what I had
-- let's see, no,
256
00:18:30,880 --> 00:18:34,500
the lambda inverse better
be multiplying the c.
257
00:18:34,500 --> 00:18:41,150
Well, actually I can do it
all in -- well step two,
258
00:18:41,150 --> 00:18:43,930
that's the easiest step,
I should be able to do it.
259
00:18:43,930 --> 00:18:52,150
c is changed to
lambda inverse c,
260
00:18:52,150 --> 00:18:56,030
so that c becomes
lambda inverse c, OK.
261
00:18:56,030 --> 00:19:01,600
And then step three
uses lambda inverse c
262
00:19:01,600 --> 00:19:11,190
to construct U. So step
three is: the answer
263
00:19:11,190 --> 00:19:14,540
U, what do I have here?
264
00:19:14,540 --> 00:19:16,740
I've got a combination
of these vectors,
265
00:19:16,740 --> 00:19:20,580
so they're the columns of S,
and what are they multiplied by?
266
00:19:20,580 --> 00:19:22,980
They're multiplied by
the c's over lambdas,
267
00:19:22,980 --> 00:19:24,610
which is what I have here.
268
00:19:24,610 --> 00:19:33,650
That's S lambda inverse c.
269
00:19:33,650 --> 00:19:36,840
Those are the three steps.
270
00:19:36,840 --> 00:19:42,900
And what's the work involved?
271
00:19:42,900 --> 00:19:47,410
Here, the work is solving a
linear system with the matrix
272
00:19:47,410 --> 00:19:53,670
S. Here, the work is
taking a combination
273
00:19:53,670 --> 00:19:59,650
of the columns of s, doing
a matrix multiplication.
274
00:19:59,650 --> 00:20:06,820
Those two steps are usually
full-scale matrix operations,
275
00:20:06,820 --> 00:20:10,610
and of course, the S --
if I just complete this,
276
00:20:10,610 --> 00:20:12,220
I'll see that I get
the right thing,
277
00:20:12,220 --> 00:20:22,910
that's S lambda inverse
and c is S inverse F.
278
00:20:22,910 --> 00:20:24,360
There's the answer.
279
00:20:24,360 --> 00:20:31,200
U is S lambda inverse -- that's
a lambda inverse there --
280
00:20:31,200 --> 00:20:37,091
S inverse F. That's the correct
answer in matrix language.
281
00:20:37,091 --> 00:20:37,590
Right.
282
00:20:40,390 --> 00:20:43,850
This is K inverse,
that's K inverse.
283
00:20:43,850 --> 00:20:54,570
K is S*lambda S inverse, and
if I take the inverse of that,
284
00:20:54,570 --> 00:21:03,830
I get S lambda inverse S
inverse to multiply F. Well,
285
00:21:03,830 --> 00:21:07,230
I doubt if you're much
impressed by this lower board,
286
00:21:07,230 --> 00:21:13,800
because the upper board was
the same thing written out.
287
00:21:13,800 --> 00:21:21,390
It took some indication of
what the separate pieces were,
288
00:21:21,390 --> 00:21:23,420
but it's pretty clear.
289
00:21:23,420 --> 00:21:33,910
OK, now the million dollar
question is, is it fast?
290
00:21:33,910 --> 00:21:37,930
And the answer is,
almost certainly no.
291
00:21:37,930 --> 00:21:45,690
But for the particular matrix
S, which by good fortune,
292
00:21:45,690 --> 00:21:50,720
S could also stand
for sine, this matrix
293
00:21:50,720 --> 00:21:57,130
of eigenvectors for this
particular problem are sines.
294
00:21:57,130 --> 00:22:00,230
These are the discrete sines,
so this is the discrete sine
295
00:22:00,230 --> 00:22:01,600
transform.
296
00:22:01,600 --> 00:22:05,630
That's we're doing, we're doing
the discrete sine transform,
297
00:22:05,630 --> 00:22:08,430
because those discrete
sine vectors are
298
00:22:08,430 --> 00:22:17,590
the eigenvectors of K. OK, now
let me say what that means.
299
00:22:17,590 --> 00:22:21,180
First I'm thinking of K in 1D.
300
00:22:21,180 --> 00:22:28,960
So this is my 2's and
minus 1's and minus 1's.
301
00:22:28,960 --> 00:22:31,540
Its eigenvectors
are discrete sines,
302
00:22:31,540 --> 00:22:38,530
if I multiply that
by sine k*h -- well,
303
00:22:38,530 --> 00:22:44,070
let me just take the first
one, sine h, sine 2h,
304
00:22:44,070 --> 00:22:52,640
sine n minus 1 h, that will
turn out to be an eigenvector.
305
00:22:56,620 --> 00:23:02,630
So this is K*y, K*y_1,
the first eigenvector.
306
00:23:02,630 --> 00:23:05,270
The eigenvectors are
-- let me draw them.
307
00:23:05,270 --> 00:23:13,960
The eigenvectors for that second
difference matrix K are --
308
00:23:13,960 --> 00:23:18,620
here's the interval, 0 to 1,
I chop it up in steps of h,
309
00:23:18,620 --> 00:23:26,700
and I plot the sine, which
starts at zero and ends
310
00:23:26,700 --> 00:23:28,960
at zero, because those are
the boundary conditions,
311
00:23:28,960 --> 00:23:34,500
and here is sine h, sine 2h,
sine 3h, sine 4h, sine 5h,
312
00:23:34,500 --> 00:23:39,880
so for the five by five case --
maybe I should just be using n
313
00:23:39,880 --> 00:23:45,890
here, or maybe I should
even be using capital N,
314
00:23:45,890 --> 00:23:49,220
so capital N is 5
in this example.
315
00:23:53,770 --> 00:23:56,250
Good.
316
00:23:56,250 --> 00:23:59,670
What's on the other side
of that equals sign?
317
00:23:59,670 --> 00:24:06,940
Some eigenvalue times the
same vector, sine h, sine 2h,
318
00:24:06,940 --> 00:24:11,890
down to sine N*h, and
that eigenvalue -- oh,
319
00:24:11,890 --> 00:24:16,230
let me just write
lambda 1 for it.
320
00:24:16,230 --> 00:24:18,270
We know what it is.
321
00:24:18,270 --> 00:24:24,900
The fact that this is an
eigenvector is just trig;
322
00:24:24,900 --> 00:24:29,670
you know, I multiply minus 1
of that plus 2 of that minus 1
323
00:24:29,670 --> 00:24:35,050
of sine 3h, and I use
a little trig identity.
324
00:24:35,050 --> 00:24:38,280
So minus that, 2 of
that, minus that,
325
00:24:38,280 --> 00:24:41,250
turns out that to be
a multiple of sine 2h.
326
00:24:41,250 --> 00:24:47,770
Well, the 2 sine 2h give us a
2, and then the minus sine h
327
00:24:47,770 --> 00:24:54,650
and the minus sine 3h
combine into sine 2h times,
328
00:24:54,650 --> 00:25:00,210
I think, it's a cosine
of h or something,
329
00:25:00,210 --> 00:25:07,290
it's that eigenvector
that's near zero,
330
00:25:07,290 --> 00:25:10,150
because the cosine
of h is near 1.
331
00:25:10,150 --> 00:25:11,320
Does that look familiar?
332
00:25:11,320 --> 00:25:16,610
That a combination
of sine h and sine 3h
333
00:25:16,610 --> 00:25:21,760
should give us twice sine
2h times some cosine,
334
00:25:21,760 --> 00:25:28,320
yep, Elementary trig identity.
335
00:25:28,320 --> 00:25:31,000
OK, so those are eigenvectors.
336
00:25:31,000 --> 00:25:36,230
That's the first one, the
next one would have h times --
337
00:25:36,230 --> 00:25:42,260
the k-th one would have h times
k instead of just h itself,
338
00:25:42,260 --> 00:25:47,200
it would take jumps
of every k -- sine.
339
00:25:47,200 --> 00:25:52,560
and then a cosine h*k
would show up there,
340
00:25:52,560 --> 00:25:56,290
and this would still
be an eigenvector.
341
00:25:56,290 --> 00:25:59,240
OK.
342
00:25:59,240 --> 00:26:06,820
I'm making a little bit
explicit these vectors,
343
00:26:06,820 --> 00:26:10,570
but the main point
is they're sines,
344
00:26:10,570 --> 00:26:14,570
they're discrete sines
at equally spaced points.
345
00:26:14,570 --> 00:26:22,600
That's what the real version
of the FFT just lives on.
346
00:26:22,600 --> 00:26:25,020
And it would also live
on discrete cosines;
347
00:26:25,020 --> 00:26:26,710
if we had different
boundary conditions,
348
00:26:26,710 --> 00:26:28,280
we could do those, too.
349
00:26:28,280 --> 00:26:34,170
So this isn't the only -- these
zero boundary conditions are
350
00:26:34,170 --> 00:26:40,240
associated with the
name of Dirichlet,
351
00:26:40,240 --> 00:26:44,350
where zero slopes are associated
with the name of Neumann,
352
00:26:44,350 --> 00:26:49,830
and both -- this one gives
sines, Neumann gives cosines,
353
00:26:49,830 --> 00:26:52,160
the FFT deals with both.
354
00:26:52,160 --> 00:26:53,600
OK.
355
00:26:53,600 --> 00:27:00,840
So, that's the fast solution,
and it would take N squared --
356
00:27:00,840 --> 00:27:02,890
well I have to go to 2D.
357
00:27:02,890 --> 00:27:05,330
sorry, I guess I
have a little more
358
00:27:05,330 --> 00:27:12,020
to say because I have to get
from this one-dimensional
359
00:27:12,020 --> 00:27:15,510
second difference to the
five-point two-dimensional
360
00:27:15,510 --> 00:27:17,530
second difference,
and that's what's
361
00:27:17,530 --> 00:27:21,080
going to happen over here.
362
00:27:21,080 --> 00:27:28,400
I wrote up some stuff about
the Kronecker operation, which
363
00:27:28,400 --> 00:27:33,000
is the nifty way for
these special problems
364
00:27:33,000 --> 00:27:36,740
to go from 1D to 2D.
365
00:27:36,740 --> 00:27:42,880
You remember the deal,
that K2D, our 2D matrix,
366
00:27:42,880 --> 00:27:51,380
was this Kronecker product
of K and I, that gave us
367
00:27:51,380 --> 00:27:54,410
second differences
in one direction,
368
00:27:54,410 --> 00:27:59,040
and then we have to add in the
Kronecker product of I and K
369
00:27:59,040 --> 00:28:02,150
to get second differences
in the other direction.
370
00:28:02,150 --> 00:28:06,845
And then we better print --
because that matrix is going
371
00:28:06,845 --> 00:28:12,680
to be large, I don't
want to print it.
372
00:28:12,680 --> 00:28:13,660
Yeah.
373
00:28:13,660 --> 00:28:15,080
What's the point?
374
00:28:15,080 --> 00:28:19,970
The point is that if I
know the eigenvectors of k,
375
00:28:19,970 --> 00:28:24,130
then I can find the -- if
I know the 1D eigenvectors,
376
00:28:24,130 --> 00:28:27,390
I can find the 2D eigenvectors,
and you don't have to know
377
00:28:27,390 --> 00:28:29,380
Kronecker products to do that.
378
00:28:29,380 --> 00:28:32,780
All you have to do is just
make a sensible guess,
379
00:28:32,780 --> 00:28:42,170
so the eigenvectors in 2D, are
-- so they have a double index,
380
00:28:42,170 --> 00:28:57,430
k and l, and their components
are sines in one direction
381
00:28:57,430 --> 00:29:00,160
times sines in the
other direction.
382
00:29:00,160 --> 00:29:02,410
So what are those sines?
383
00:29:02,410 --> 00:29:06,810
There's a k*h, I guess, l*h.
384
00:29:14,080 --> 00:29:18,860
Those are the first components,
I guess I have to tell you what
385
00:29:18,860 --> 00:29:26,640
all the components are: k --
the seventh component in the x
386
00:29:26,640 --> 00:29:34,840
direction, there'd be a factor
7 -- so k*m*h sine l*n*h.
387
00:29:34,840 --> 00:29:41,810
This is the (m, n)
component of y_(k, l).
388
00:29:48,720 --> 00:29:50,680
It's just what we had in 1D.
389
00:29:50,680 --> 00:29:56,510
In 1D there was no l, the
components were just sine
390
00:29:56,510 --> 00:29:58,130
k*m*h.
391
00:29:58,130 --> 00:30:05,320
Now we've got two, one
in the x direction --
392
00:30:05,320 --> 00:30:13,400
These are the analogs of the
-- the continuous case would be
393
00:30:13,400 --> 00:30:21,120
sine k*pi*x times sine l*pi*y.
394
00:30:24,740 --> 00:30:29,380
Those are the eigenvectors
as eigenfunctions,
395
00:30:29,380 --> 00:30:31,000
functions of x and y.
396
00:30:31,000 --> 00:30:35,300
And the point is
that, once again,
397
00:30:35,300 --> 00:30:37,930
with these beautiful
matrices, I can
398
00:30:37,930 --> 00:30:43,120
sample these at the
equally spaced points,
399
00:30:43,120 --> 00:30:47,940
and I get discrete
sines that the FFT is
400
00:30:47,940 --> 00:30:49,620
ready to go with, OK.
401
00:30:54,670 --> 00:31:04,770
I'm giving this much detail
partly because the continuous
402
00:31:04,770 --> 00:31:09,730
case, of course, our operators
d second by the dx squared and d
403
00:31:09,730 --> 00:31:17,820
second by dy squared, and
the whole idea of separating
404
00:31:17,820 --> 00:31:24,700
variables, of looking
for solutions u --
405
00:31:24,700 --> 00:31:28,380
here is the eigenvalue problem,
the continuous eigenvalue
406
00:31:28,380 --> 00:31:28,930
problem.
407
00:31:28,930 --> 00:31:32,300
The Laplacian of u,
maybe I do a minus,
408
00:31:32,300 --> 00:31:35,670
the Laplacian of
u equal lambda*u,
409
00:31:35,670 --> 00:31:38,760
and that's a partial
differential equation,
410
00:31:38,760 --> 00:31:45,540
usually it's not easy to
solve, but if I'm on a square,
411
00:31:45,540 --> 00:31:48,700
and I have zero
boundary conditions,
412
00:31:48,700 --> 00:31:52,430
then I've solved it, by
separation of variables,
413
00:31:52,430 --> 00:31:55,600
a function of x times
a function of y.
414
00:31:55,600 --> 00:31:57,760
And that function of
x times function of y
415
00:31:57,760 --> 00:32:00,110
is exactly what
Kronecker product
416
00:32:00,110 --> 00:32:03,480
is doing for matrices, yep.
417
00:32:08,730 --> 00:32:15,960
I thought maybe this is good to
know when the problem is easy,
418
00:32:15,960 --> 00:32:23,750
and as I say, the possibility of
using the easy case on a square
419
00:32:23,750 --> 00:32:29,560
for preconditioning a not
so easy case is attractive.
420
00:32:29,560 --> 00:32:31,920
All right, so
that's what I wanted
421
00:32:31,920 --> 00:32:38,820
to say about number one,
that's the main suggestion,
422
00:32:38,820 --> 00:32:46,400
and again, the point was just to
take these three simple steps,
423
00:32:46,400 --> 00:32:51,730
provided we know and
like the eigenvectors.
424
00:32:51,730 --> 00:32:55,300
Here we know them and
we like them very much,
425
00:32:55,300 --> 00:32:57,580
because they're
those discrete sines.
426
00:32:57,580 --> 00:33:02,810
OK, now just to
finish comes, what's
427
00:33:02,810 --> 00:33:06,480
up with odd-even reduction.
428
00:33:06,480 --> 00:33:11,040
I'll use the same
1D problem first.
429
00:33:11,040 --> 00:33:14,440
It works great in --
that's not good English,
430
00:33:14,440 --> 00:33:20,680
but it works very well in
1D, odd-even reduction,
431
00:33:20,680 --> 00:33:23,980
you'll see it, you'll
see, oh boy, simple idea.
432
00:33:23,980 --> 00:33:27,430
But of course, don't forget
that ordinary elimination
433
00:33:27,430 --> 00:33:33,210
is a breeze with a tri-diagonal
matrix, so nothing I could do
434
00:33:33,210 --> 00:33:35,240
could be faster than that.
435
00:33:35,240 --> 00:33:37,300
But let's see what you can do.
436
00:33:37,300 --> 00:33:40,250
I just want to write
down the -- OK,
437
00:33:40,250 --> 00:33:48,150
keep your eye on this matrix,
so I'm going to write out
438
00:33:48,150 --> 00:33:49,350
the equations.
439
00:33:49,350 --> 00:33:59,080
So it'll be minus U_(i-2)
plus 2*U_(i-1) minus U_i,
440
00:33:59,080 --> 00:34:03,840
that would be F_(i-1); that
would be equation number i
441
00:34:03,840 --> 00:34:04,960
minus 1, right?
442
00:34:04,960 --> 00:34:09,900
With a minus 1, 2,
minus 1, centered there.
443
00:34:09,900 --> 00:34:17,200
And then the next one will be
a minus U_(i-1) plus 2*U_i --
444
00:34:17,200 --> 00:34:27,270
I better move this guy over
further -- minus U_(i+1),
445
00:34:27,270 --> 00:34:31,340
that will be F_i, right?
446
00:34:31,340 --> 00:34:34,180
That's equation number i,
and now I just want to look
447
00:34:34,180 --> 00:34:36,450
at equation number
-- the next equation,
448
00:34:36,450 --> 00:34:44,850
minus U_i plus 2*U_(i+1)
minus U_(i+2) is F_(i+1).
449
00:34:49,350 --> 00:34:55,390
So I've written down three
consecutive equations,
450
00:34:55,390 --> 00:35:04,240
three consecutive rows
from my simple matrix:
451
00:35:04,240 --> 00:35:09,420
a row, the next row,
and the next row.
452
00:35:09,420 --> 00:35:12,350
So the right-hand sides
are coming in order,
453
00:35:12,350 --> 00:35:17,520
and the diagonals are there,
and if I look at that,
454
00:35:17,520 --> 00:35:18,510
do I get any idea?
455
00:35:21,400 --> 00:35:29,030
Well, there is an idea here.
456
00:35:31,900 --> 00:35:39,330
I'd like to remove these
guys, the U_(i-1)'s and the
457
00:35:39,330 --> 00:35:43,710
U_(i+1)'s, so that's where
this word odd-even reduction is
458
00:35:43,710 --> 00:35:44,210
coming in.
459
00:35:44,210 --> 00:35:46,820
I'm going to reduce
this system by keeping
460
00:35:46,820 --> 00:35:53,750
only every second unknown
and eliminating those.
461
00:35:53,750 --> 00:35:55,480
How to do that?
462
00:35:55,480 --> 00:35:57,260
Well, you can see
how to eliminate.
463
00:35:57,260 --> 00:36:01,050
If I multiply this
equation by 2.
464
00:36:01,050 --> 00:36:03,090
If I multiply that
middle equation
465
00:36:03,090 --> 00:36:07,380
by 2, that becomes a 4,
this becomes a minus 2,
466
00:36:07,380 --> 00:36:10,120
this becomes a 2, and
now what shall I do?
467
00:36:12,950 --> 00:36:14,720
Add.
468
00:36:14,720 --> 00:36:20,510
If I add the equations
together, I get minus U_(i-2) --
469
00:36:20,510 --> 00:36:25,270
these cancel, that was the
point -- plus 4 minus a couple,
470
00:36:25,270 --> 00:36:30,550
so that's two u_i's,
minus this guy,
471
00:36:30,550 --> 00:36:44,200
u_(i-2) is that sum F_(i-1),
two F_i's, and F_(i+1).
472
00:36:47,270 --> 00:36:52,680
Well, sorry it's squeezed down
here, but this is the point.
473
00:36:52,680 --> 00:36:56,800
The main point is look at this.
474
00:36:56,800 --> 00:37:00,050
What do we have?
475
00:37:00,050 --> 00:37:06,880
We've got a typical
equation, but now we've
476
00:37:06,880 --> 00:37:09,720
removed half the unknowns.
477
00:37:09,720 --> 00:37:12,030
The problem is now half-sized.
478
00:37:12,030 --> 00:37:16,450
We've only got the
even-numbered unknowns
479
00:37:16,450 --> 00:37:24,590
at a small cost in updating
the right-hand side,
480
00:37:24,590 --> 00:37:27,280
and the problem's cut in half.
481
00:37:27,280 --> 00:37:30,250
So that's this
odd-even reduction,
482
00:37:30,250 --> 00:37:35,400
and it cuts a problem in
half, and everybody knows
483
00:37:35,400 --> 00:37:38,820
right away what to do next.
484
00:37:38,820 --> 00:37:43,670
The one mantra of computer
science, "Do it again."
485
00:37:43,670 --> 00:37:48,760
So that is the same
problem on the even,
486
00:37:48,760 --> 00:37:51,910
we do it again,
so I should really
487
00:37:51,910 --> 00:37:57,440
call it cyclic reduction, we
just cycle with this reduction,
488
00:37:57,440 --> 00:38:01,140
and in the end, we
have a 2 by 2 problem.
489
00:38:04,700 --> 00:38:10,200
That seems pretty smart,
pretty successful move,
490
00:38:10,200 --> 00:38:12,730
and I guess if we do
an operation count,
491
00:38:12,730 --> 00:38:14,970
well, I haven't
thought that through.
492
00:38:14,970 --> 00:38:18,530
What does the operation
count look like?
493
00:38:18,530 --> 00:38:21,860
It must be pretty quick, right?
494
00:38:21,860 --> 00:38:25,200
Well, undoubtedly we're
solving this linear system
495
00:38:25,200 --> 00:38:27,620
in O of N steps.
496
00:38:27,620 --> 00:38:32,330
Well, no big surprise to be able
to deal with that matrix in O
497
00:38:32,330 --> 00:38:37,740
of N steps, because elimination
would take O of N steps,
498
00:38:37,740 --> 00:38:44,390
it's size N, but it's bandwidth
is 1, so 2N or something steps
499
00:38:44,390 --> 00:38:46,670
would do it, and
maybe, I don't know
500
00:38:46,670 --> 00:38:50,090
how many steps we have here.
501
00:38:50,090 --> 00:38:54,020
I guess, when we cut it
in half, that required
502
00:38:54,020 --> 00:38:56,370
us to do that much.
503
00:38:56,370 --> 00:39:03,920
It's order N, it's order N.
504
00:39:03,920 --> 00:39:10,580
So the key question
is, can we do it 2D?
505
00:39:10,580 --> 00:39:13,790
Can we do the same thing in 2D?
506
00:39:13,790 --> 00:39:20,330
So I want to follow that
plan in two dimensions
507
00:39:20,330 --> 00:39:25,960
where now U will be a
whole row at a time,
508
00:39:25,960 --> 00:39:30,700
so I'm doing block 2D, block 2D.
509
00:39:30,700 --> 00:39:34,430
So, can I write down the
equations in block 2D,
510
00:39:34,430 --> 00:39:36,030
for whole rows?
511
00:39:36,030 --> 00:39:42,590
So U_i is the vector -- So
now this is the 2D problem,
512
00:39:42,590 --> 00:39:45,450
so it'll be minus
the identity --
513
00:39:45,450 --> 00:39:48,860
where instead of instead of 1,
I have to write the identity --
514
00:39:48,860 --> 00:39:56,800
U_(i-2) and 2K, right?
515
00:39:56,800 --> 00:40:03,650
Oh no, what is the middle
-- what's on the --
516
00:40:03,650 --> 00:40:08,040
so multiplying U_i, U_(i-1).
517
00:40:08,040 --> 00:40:09,540
I wanted to just
say the same thing,
518
00:40:09,540 --> 00:40:15,300
but I have to write down the --
this is going to be N squared
519
00:40:15,300 --> 00:40:19,720
equations N at a time,
a whole row at a time,
520
00:40:19,720 --> 00:40:23,050
and what's on the
diagonal of K2D?
521
00:40:23,050 --> 00:40:27,310
Not 2K.
522
00:40:27,310 --> 00:40:32,190
It's 2I, is it 2I plus K?
523
00:40:32,190 --> 00:40:32,800
Yeah.
524
00:40:32,800 --> 00:40:36,150
Yeah, K plus 2I.
525
00:40:36,150 --> 00:40:42,860
Isn't that what we have on
the diagonal of the K2D one?
526
00:40:42,860 --> 00:40:53,960
Times U_(i-1) minus
I*U_i is equal to some --
527
00:40:53,960 --> 00:40:55,670
that's a whole row at a time.
528
00:40:55,670 --> 00:41:02,320
These are all vectors with
N components now, right?
529
00:41:02,320 --> 00:41:06,500
The minus i, the 2I, and
the minus I are the second
530
00:41:06,500 --> 00:41:10,420
differences of one of
rows, they're difference is
531
00:41:10,420 --> 00:41:14,560
in the vertical direction,
and this K*U_i the second
532
00:41:14,560 --> 00:41:15,840
difference is along the row.
533
00:41:19,340 --> 00:41:23,160
OK, so same equation
at the next row.
534
00:41:23,160 --> 00:41:34,880
So the next row is minus
I*U_(i-1), K plus 2 U_i --
535
00:41:34,880 --> 00:41:37,020
because that's now
the diagonal block --
536
00:41:37,020 --> 00:41:42,760
minus I*U_(i+1) is F_(i+1).
537
00:41:42,760 --> 00:41:46,640
And it'll just take me a
second to write this one.
538
00:41:46,640 --> 00:41:57,690
This is K plus 2I U_(i+1),
minus I*U_(i+2) is F_(i+2).
539
00:41:57,690 --> 00:41:58,190
OK.
540
00:42:01,290 --> 00:42:08,980
Exactly the same, but now
a row at a time in 2D.
541
00:42:08,980 --> 00:42:11,620
So the same idea is
going to work, right?
542
00:42:11,620 --> 00:42:13,280
What do I do?
543
00:42:13,280 --> 00:42:20,990
I want to cancel this, so I
multiply that row by K plus 2I.
544
00:42:20,990 --> 00:42:23,060
Before I multiplied
it by 2, but now
545
00:42:23,060 --> 00:42:26,300
I have to multiply
it by K plus 2I.
546
00:42:26,300 --> 00:42:29,700
Times the row, the whole row.
547
00:42:32,350 --> 00:42:36,480
So when I do that this
cancels, so I have minus this,
548
00:42:36,480 --> 00:42:40,240
this guy wasn't affected.
549
00:42:40,240 --> 00:42:44,100
And this will
cancel, the K plus 2I
550
00:42:44,100 --> 00:42:46,460
will cancel this
one, just as before.
551
00:42:46,460 --> 00:42:53,640
This will not be
affected, U_(i+2),
552
00:42:53,640 --> 00:43:07,220
and I have F_i and K plus
2I F_(i+1) and F_(i+2).
553
00:43:10,830 --> 00:43:14,640
That should have been i minus
1, and this should have been i,
554
00:43:14,640 --> 00:43:16,220
and this should
have been i plus 1,
555
00:43:16,220 --> 00:43:24,630
sorry, mis-labeled the
F's, but no big deal.
556
00:43:24,630 --> 00:43:27,650
The point is the left
side, and the point
557
00:43:27,650 --> 00:43:30,160
is what's in that space.
558
00:43:32,860 --> 00:43:34,080
What goes in that space?
559
00:43:34,080 --> 00:43:41,140
Well, it's minus I, K
plus 2I, squared, minus I,
560
00:43:41,140 --> 00:43:49,670
so this is K plus 2I squared,
which before was so easy,
561
00:43:49,670 --> 00:43:53,850
and then the minus I, and
the minus I is the minus 2I,
562
00:43:53,850 --> 00:43:55,390
is multiplying the U_i.
563
00:43:55,390 --> 00:44:00,490
Yeah, that was minus I.
564
00:44:00,490 --> 00:44:09,640
OK, this is my matrix
from odd-even reduction.
565
00:44:09,640 --> 00:44:12,620
It's just natural
to try the idea,
566
00:44:12,620 --> 00:44:18,540
and the idea works,
but not so perfectly,
567
00:44:18,540 --> 00:44:26,330
because previously in 1D, that
just gave us the answer 2;
568
00:44:26,330 --> 00:44:28,180
it was 4 minus 2.
569
00:44:28,180 --> 00:44:34,150
But now in 2D, we have a
matrix, not surprising,
570
00:44:34,150 --> 00:44:36,460
but what we don't
like is the fact
571
00:44:36,460 --> 00:44:40,690
that the bandwidth is
growing. k was tri-diagonal,
572
00:44:40,690 --> 00:44:44,290
but when we square it, it
will have five diagonals,
573
00:44:44,290 --> 00:44:49,430
and when we repeat the odd-even
cycles, when we do it again,
574
00:44:49,430 --> 00:44:56,070
those five diagonals will be
nine diagonals, and onwards.
575
00:44:56,070 --> 00:45:04,380
So, I'm getting
half-sized problems.
576
00:45:04,380 --> 00:45:11,400
All the odd-numbered rows
in my square are eliminated,
577
00:45:11,400 --> 00:45:13,970
this just involves the
even-numbered rows,
578
00:45:13,970 --> 00:45:21,500
but the matrix is not
tri-diagonal anymore,
579
00:45:21,500 --> 00:45:24,640
it's growing in bandwidth.
580
00:45:24,640 --> 00:45:28,480
So, and then you have
to keep track of it,
581
00:45:28,480 --> 00:45:37,650
so the final conclusion is that
this is a pretty good idea,
582
00:45:37,650 --> 00:45:41,800
but it's not quite
as good as this one.
583
00:45:41,800 --> 00:45:45,330
It's not as good as
the FFT-based idea.
584
00:45:45,330 --> 00:45:50,230
Also, if you look to see
what is most efficient --
585
00:45:50,230 --> 00:45:52,540
see the eigenvectors
are still here,
586
00:45:52,540 --> 00:45:59,690
so I could do three steps of
this and then go to Fourier,
587
00:45:59,690 --> 00:46:03,360
and that probably
is about right.
588
00:46:03,360 --> 00:46:09,100
So, if you really wanted to
polish off a fast Poisson
589
00:46:09,100 --> 00:46:13,760
solver, you could do
maybe two steps or three
590
00:46:13,760 --> 00:46:18,390
of odd-even cyclic
reduction, but then
591
00:46:18,390 --> 00:46:27,010
your matrix is getting messy and
you switch to the fast Poisson
592
00:46:27,010 --> 00:46:27,510
solver.
593
00:46:27,510 --> 00:46:30,060
So it's not quite
Poisson anymore,
594
00:46:30,060 --> 00:46:32,970
because it's has
a messier matrix,
595
00:46:32,970 --> 00:46:38,440
but it still has the
same eigenvectors.
596
00:46:38,440 --> 00:46:41,880
As long as we stay
with the matrix K,
597
00:46:41,880 --> 00:46:48,410
we know its eigenvectors, and
we know that they're sines
598
00:46:48,410 --> 00:46:51,170
and that they're
quick to work with.
599
00:46:51,170 --> 00:46:52,300
OK.
600
00:46:52,300 --> 00:46:53,510
Anyway, there you go.
601
00:46:53,510 --> 00:47:00,780
That's a fast algorithm for
the lecture before the spring
602
00:47:00,780 --> 00:47:02,590
break.
603
00:47:02,590 --> 00:47:08,210
So after the break is, first
of all, discussion of projects.
604
00:47:08,210 --> 00:47:13,070
If your project could
include a page --
605
00:47:13,070 --> 00:47:19,240
and you could maybe email
the whole project to Mr. Cho.
606
00:47:19,240 --> 00:47:27,100
Maybe also, could you email
to me a sort of summary page
607
00:47:27,100 --> 00:47:31,040
that tells me what you did, so
I'll save the summary pages,
608
00:47:31,040 --> 00:47:37,540
and I'll have for Mr. Cho the
complete project with printout
609
00:47:37,540 --> 00:47:42,030
and graph, as far
as appropriate,
610
00:47:42,030 --> 00:47:44,490
and so we'll spend
some time on that,
611
00:47:44,490 --> 00:47:53,850
and then move to the big topic
of the rest of the course,
612
00:47:53,850 --> 00:48:00,450
which is solving optimization
problems, minimization,
613
00:48:00,450 --> 00:48:05,660
maximization in many variables.
614
00:48:05,660 --> 00:48:14,830
OK, so have a good spring
break and see you a week
615
00:48:14,830 --> 00:48:16,120
from Wednesday.
616
00:48:16,120 --> 00:48:17,370
Good.