MIT

Studies of the ocean circulation and climate have come to be dominated by the results of complex numerical models encompassing hundreds of thousands of lines of computer code and whose physics may be more difficult to penetrate than the real system. Some insight into the large-scale ocean circulation can perhaps be gained by taking a step back and considering the gross time scales governing oceanic changes. These can derived from a wide variety of simple considerations such as energy flux rates, signal velocities, tracer equilibrium times, and others. At any given time, observed changes are likely a summation of shifts taking place over all of these time scales.

Tridiagonal matrices and three term recurrences and second order equations appear amazingly often, throughout all of mathematics. We won't try to review this subject. Instead we look in two less familiar directions.

\\

\\

Here is a tridiagonal matrix problem that waited surprisingly long for a solution. Forward elimination factors T into LDU, with the pivots in D as usual. Backward elimination, from row n to row 1, factors T into U_D_L_. Parlett asked for a proof that diag(D + D_) = diag(T) + diag(T^-1).^-1. In an excellent paper (Lin Alg Appl 1997) Dhillon and Parlett extended this four-diagonal identity to block tridiagonal matrices, and also applied it to their "Holy Grail" algorithm for the eigenproblem. I would like to make a different connection, to the Kalman filter.

\\

\\

The second topic is a generalization of tridiagonal to "tree-diagonal". Unlike the interval, the tree can branch. In the matrix T, each vertex is connected only to its neighbors (but a branch point has more than two neighbors). The continuous analogue is a second order differential equation on a tree. The "non-jump" conditions at a meeting of N edges are continuity of the potential (N-1 equations) and Kirchhoff's Current Law (1 equation). Several important properties of tridiagonal matrices, including O(N) algorithms, survive on trees.

We discuss two filters that are frequently used to smooth data.

One is the (nonlinear) median filter, that chooses the median

of the sample values in the sliding window. This deals effectively

with "outliers" that are beyond the correct sample range, and will

never be chosen as the median. A straightforward implementation of

the filter is expensive for large windows, particularly in two dimensions

(for images).

\\

\\

The second filter is linear, and known as "Savitzky-Golay". It is

frequently used in spectroscopy, to locate positions and peaks and

widths of spectral lines. This filter is based on a least-squares fit

of the samples in the sliding window to a polynomial of relatively

low degree. The filter coefficients are unlike the equiripple filter

that is optimal in the maximum norm, and the "maxflat" filters that

are central in wavelet constructions. Should they be better known....?

\\

\\

We will discuss the analysis and the implementation of both filters.

In addition to the announced topic of Pascal Matrices (abstract below) we will speak briefly about more recent work by Per-Olof Persson on generating simplicial meshes on regions defined by a function that gives the distance from the boundary. Our first goal was a short MATLAB code and we just submitted "A Simple Mesh Generator in MATLAB" to SIAM.

This is joint work with Alan Edelman at MIT and a little bit with Pascal. They had all the ideas.

Put the famous Pascal triangle into a matrix. It could go into a lower triangular L or its transpose L' or a symmetric matrix S:

These binomial numbers come from a recursion, or from the formula for i choose j, or functionally from taking powers of (1 + x).

The amazing thing is that L times L' equals S. (OK for 4 by 4) It follows that S has determinant 1. The matrices have other unexpected properties too, that give beautiful examples in teaching linear algebra. The proof of L L' = S comes 3 ways, I don't know which you will prefer:

1. By induction using the recursion formula for the matrix entries.
2. By an identity for the coefficients i+j choose j in S.
3. By applying both sides to the column vector [ 1 x x² x³ ... ]'.

The third way also gives a proof that S³ = -I but we doubt that result.

The rows of the "hypercube matrix" L² count corners and edges and faces and ... in n dimensional cubes.

An essential first step in many problems of numerical analysis and

computer graphics is to cover a region with a reasonably regular mesh.

We describe a short MATLAB code that begins with a "distance function"

to describe the region: $d(x)$ is the distance to the boundary

(with d

Study the parabolic Hitchin fibrations for Langlands dual groups. Sketch the proof of a duality theorem of the natural symmetries on their cohomology.

Extend the affine Weyl group action in Lecture I to double affine Hecke algebra action, and (hopefully) more examples.

Introduce the parabolic Hitchin fibration, construct the affine Weyl group action on its fiberwise cohomology, and study one example.