COURSES

• Math 378 - Introduction to spectral graph theory and applications - Spring 2008
• Math 224 - Scientific Computing - Fall 2007
• Math 348 - Harmonic Analysis and Applications - Spring 2007
• Teaching related links (mostly for my own use)

Math 378 - Minicourse - INTRODUCTION TO SPECTRAL GRAPH THEORY AND APPLICATIONS - SPRING 2008

We will discuss the basics of spectral graph theory, which studies random walks on graphs, and related objects such as the Laplacian and its eigenfunctions, on a weighted graph. This can be thought as a discrete analogue to spectral geometry, albeit the geometry of graphs and their discrete nature gives rise to issues not generally considered in the continuous, smooth case of Riemannian manifolds. We will present some classical connections between properties of the random walks and the geometry of the graph. We will then discuss disparate applications: the solution of sparse linear systems by multiscale methods based on random walks; analysis of large data sets (images, web pages, etc...), in particular how to find systems of coordinates on them, performing dimensionality reduction, and performing multiscale analysis on them; tasks in learning, such as spectral clustering, classification and regression on data sets.

Materials:

• Code for the demo involving drawing a set a points, constructing an associated proximity graph, and computing and displaying eigenvalues/eigenfunctions of the Laplacian. You need to first download and install the general code for Diffusion Geometry (last updated on 1/29/08), and then download and install this code for running the demo I ran in class, with some images already prepared. After installing the Diffusion Geometry package, please run DGPaths in order to set the Matlab paths correctly. The script for the demo is called GraphEigenFcnsEx_01.m, and it is fairly extensively commented. I will be happy to add your own examples here! The code works best with the Approximate Nearest Neighbor Searching Library by D. Mount and S. Arya. To install this code, simply untar in a directory and run make. This should produce the file libANN.a in the lib subdirectory. This file is already included in the Diffusion Geometry package, in the MEX directory, compiled on a Unix machine at Duke Math. Copy this library libANN.a in the MEX directory, under the directory where the Diffusion Geometry package, and from the Matlab prompt run "mex ANNsearch libANN.a" and "mex ANNrsearch libANN.a". This will yield two .mexglx files, that are what Matlab will call. These two files are already included in the Diffusion Geometry package, after compilation on a Unix machine at Duke Math.

References:

• R. Diestel's book on Graph Theory is an excellent general reference. Availble online here.
• D. Spielman notes for his course on Spectral Graph Theory at Yale; several papers on specific applications, dependent on the attendant's interests.
• D. Spielman notes on his course on Graphs and Networks at Yale. Some overlap with the above, but also other references and materials.
• F. Chung's book "Spectral Graph Theory". She also wrote a book on "Complex Graphs and Networks", mostly on random graphs and their degree distribution properties, and also some spectral results for them. Visit her homepage for lots of interesting material on graphs, spectral graph theory and its applications. In particular see the gallery of graphs.
• S. Lafon's web page has some cool tutorials and interactive demos on diffusion geometry.

Math 224 - SCIENTIFIC COMPUTING - FALL 2007

Office hours: Wed 4:30-5:30, Thu 1:10-2:10, or by appointment.

Here is the synopsis.

The first part of the course will cover basic numerical linear algebra, in particular matrix factorizations, solution of linear systems and eigenproblems. The second part of the course will cover nonlinear equations, numerical integration and differentiation, basic techniques for ODEs, and the Fast Fourier Transform.

Useful links: John Trangenstein's home page contains a link to his online book on Scientific Computing, as well as several useful links to programming guides for Fortrain, C, C++ and Lapack on his page for Math 225. William Allard's home page also contains useful material, such as notes and links to online guides and materials.
Fortran tutorial: here and here.
Matlab tutorial: from Mathworks here, from the University of Florida here. Many more are available online, just use your favourite search engine to look for "matlab tutorial".

Homework sets: 1 (solution), 2 (solution), 3 (solution), 4 (solution), 5 (solution), 6 (solution), 7, 8.

Partial solution to test 1.

Fall 2007 semester schedule

Math 348 - HARMONIC ANALYSIS AND APPLICATIONS - CUR RES IN ANALYSIS - SPRING 2007

Please find the synopsis here.

I plan to develop lecture notes as the course proceeds. Last update: 1/10/07. The notes are still in a very preliminary should be downloaded and used by students of the course only, and should not be divulgated, replicated if not for purposes related to the course. When a more stable version will become available, certain of these restrictions will be removed. This link will be updated regularly. Right now they are in an extremely preliminary state, and at times they may not even be accessible through the link provided.

A list of topics for presentation suggested for the course (by instructor or students), and the students currently working on them is available here.

Presentations by students:

• Statistical Approach to Wavelet Shrinkage, Simon Lunagomez
• Semisupervised Learning on Graphs, Chungping Wang
• Markov Decision Processes, Rachel Thomas
• The Fast Multipole Method, Veronica Rozmiarek
• Multiscale Reconstruction of Hyperspectral Data , Kalyani Shivakumar and Cristina Fernandez.
• Stochastic Filtering, Zachary Harmany and William Lee.

TEACHING RELATED LINKS

Duke class schedule, and Duke math class schedule and Fall 2007 Final exam schedule.

Duke calendar.

Duke SISS storm login (instructor)

Registrar services

Advis s manual

Back to home page