Eigenvalues of Graphs with Applications
18.409 Topics in Theoretical Computer Science
Instructor:
Dan Spielman.
Wednesday 3-6 in 4-253
First meeting Feb 5th!
In this seminar, we will explore and exploit eigenvalues and
eigenvectors of graphs. We will study what eigenvalues and
eigenvectors tell us about a graph, and see how this information may
be used to design and analyze algorithms. In particular, we will
examine algorithms for solving linear systems and quantum algorithms.
While these topics might seem quite unrelated, I hope to see many
connections in their underlying mathematics.
We will begin with an examination of eigenvalues of graphs. I expect
that we will see their relation to graph cut problems, clique numbers,
coloring, and isomorphism testing. We will try to understand how
structures in a graph effect its eigenvalues.
Many theoretical computer scientists might be wondering why I want to
study algorithms for solving linear systems that don't involve fast
matrix inverse algorithms. The reason is that these algorithms give
no improvement in the solution of sparse linear systems: if a
system only has m non-zero entries, then we should find an
algorithm whose running time is small in m Two approaches we
should examine are:
- nested disection, which uses a sequence
of cuts in a graph to determine how the linear system should be
solved, and
- combinatorial preconditioners: a remarkable
innovation of Vaidya which allows the solution of linear systems in
m^(7/4) time--much less time than would be required to even
write down the inverse! Vaidya's first method used maximum spanning
trees. Recent improvements use results on routing and multicommodity
flows.
We will largely ignore numerical issues in this discussion.
Eigenvalues arise in the study of Quantum algorithms through the
Adiabatic model of quantum computing. Introduced originally as a new
way of desinging quantum algorithms, it has recently been shown that
all quantum algorithms have adiabatic realizations. The fundamental
idea in adiabatic computing is that a quantum algorithm can find the
eigenvector of an extremal eigenvalue of an exponentially large
matrix. However, the time required for the algorithm to compute this
eigenvector is related to gaps between eigenvalues. So, if we are
going to make progress on designing Adiabatic quantum algorithms, we
must first familarize ourselves with techniques for bounding
eigenvalues.
Other topics will be studied according to student interest.