Quarter
Course Type
Course Area
Foundations
Enrollment Code
60681
Location
Phelps 2510
Units
4
Day and Time
T/R 3-4:50pm
Course Description

Perhaps the most powerful of the many connections between graphs and matrices is the Laplacian matrix of a graph.

The definition is easy -- start with an undirected graph, put the vertex degrees on the diagonal, and put -1 in each off-diagonal position where there's an edge. The consequences are profound, ranging from data mining and analysis (spectral clustering, Fourier analysis on graphs), to parallel computing (spectral partitioning), to graph algorithms (flows in networks), to topological graph theory (the planar separator theorem), to applications in ecology (genetic connectivity of populations), electrical engineering (resistive networks, graph signal processing), PDEs (Laplacians on manifolds), and many more.

The material of this course will range over both theoretical and applied aspects of graph Laplacians. What can they be used for? What is the mathematics behind them? How can we compute with them in practice?

The prerequisites are some basic knowledge of linear algebra and graph theory. While this background is elementary, the course will move at a quick pace. The work for the course will consist of approximately 5 problem sets, plus a final project that may be either computational or theoretical.