Minor 3: A term paper on generalized eigenvalues of graph Laplacians

In class we saw how one method of speeding up Laplacian solvers based on the Conjugate Gradient method was to precondition them with the Laplacian of a subgraph of the original graph. Specifically we saw that if we precondition using a tree that does not badly "stretch" the metric induced by effective resistance, the preconditioning gives us a speed-up.

This argument essentially depends on the so-called generalized eigenvalues of the Laplacian. In general, given a matrix A, its generalized eigenvalues are described vis-a-vis another matrix B as those values λ for which A - λ B has a non-empty kernel, reducing to the usual definition of eigenvalues if B = I. In the case of the preconditioning argument the matrix A is the Laplacian of the graph we are working with and "preconditioning" it with a subgraph involves working with the generalized eigenvalues, with B being the Laplacian of a subgraph.

For this term paper I would like you to research all you can find about the uses of generalized eigenvalues of graph Laplacians in the specific setting where the second matrix is subgraph of the original graph. Apart from presenting what you find in the literature I also want you to work out interesting examples using simple subgraphs apart from trees, and try to present a picture of what such generalized eigenvalues look like.

Grading parameters

Grading will be subjective and will look at the following parameters: Clarity, flow, depth of investigation and effort put in. Lack of citations will lead to penalties, so please make sure you cite wherever required.

Supporting files

Download the tex template and bib file here. To read further instructions, look at the pdf here.

Deadline

Please submit on moodle by 11:55PM, 11 April 2018.

Return to course page.


Updated: Sun Mar 25 14:08:32 IST 2018
Amitabha Bagchi