This page is out of date and reflects the content from 2009

Description

This class will cover material from three areas: Spectral Graph Theory, Numerical Linear Algebra, and Biomedical Applications. The central issue in spectral graph theory is understanding, estimating, and finding eigenvectors and eigenvalues of graphs. The study of random walks on a graph was one of the first users of spectral graph theory. Answering such questions as: How many times should you shuffle a deck of cards to insure that the deck is "well shuffled"? More recent application include Google's page rank algorithm which performs a random walk on the hyperlink graph of the Internet. It has also been applied to the problem of finding these eigenvectors as well as solving related linear systems.

Scientific computation is the broad field concerned with the design and analysis of numerical algorithms. The simplest examples are solving a linear system of equations or finding the eigenvalue and eigenvectors of a matrix. These numerical algorithms are central to design, testing, and understanding of enumerable physical objects. These methods are also central to other areas such as fast LP solvers, applications in machine learning. The design of building, ships, artificial organs, to ink jet printers all use these algorithms. Numerical algorithms also appear in other parts of science and engineering. Google uses eigenvectors of graphs to rank pages on the Internet. Eigenvectors are used to partition large graphs for storage over multiple machines.

On the other hand, computer science algorithm theory is playing a larger role in the design of new faster numerical algorithms. As an example in the 1970's researcher showed how efficient algorithms for Gaussian elimination could be expressed as a purely graph theoretic problem. This formulation dramatically changed how we view Gaussian elimination and how we design algorithms for it.

More recently, the focus has been on iterative system solvers. Here again, at least for some very important special cases, the problem can be expressed in graph theoretic ways. In this case understanding eigenvalues of graphs plays an important role.



Grading

There will be about five graded problem sets. Students will be expected to take and prepare notes for one or two lectures. There will be no exams.



Tentative list of topics

  • Resistive Networks and Rayleigh's Monotonicity Law.
  • Random walks on graphs
    • Basic issues about random walks
    • The steady state and the Perron-Frobenius Theorem
    • Mixing time and the spectral gap
    • The symmetric case
      • Computing the commute and hitting time using graph Laplacians
      • Coupling arguments for estimating mixing times
  • Solving Sparse Linear Systems
    • Direct Methods and Pivot Strategies
      • For fill: Nested Dissection.
      • For Numerical Stability
    • Iterative Methods
      • General Framework
      • Chebyshev Method
      • Conjugate Gradient
      • Preconditioners for iterative methods
  • Eigenvalue Calculations and Estimation
    • QR Algorithm
    • The Singular Value Decomposition
    • Lanczos Algorithm
    • Graph Embeddings as an Eigenvalue Estimator
    • Cheeger inequality
  • Graph Separators
    • Spectral Methods
    • Geometric Methods
    • Multi-Commodity Flow
    • Application to Linear Equations
  • Graph Partitioning Using Spectral Rounding
The following topics will NOT be covered this year unless if there is sufficient student interest. Meshing has been covered in my Computational Geometry class

Mesh Generation
Related Computational Geometry
Delaunay Triangulations
Voronoi Diagrams
Convex hull
Quadtree Based Methods
Delaunay Based Methods
Conformal Mapping Methods

Algorithms for Approximating PDEs
Structure of Elliptic PDEs
Finite Element
Finite Difference
Control Volume