MATH Seminar
| Title: A Multilevel Subgraph Preconditioner for Linear Equations in Graph Laplacians |
|---|
| Seminar: Numerical Analysis and Scientific Computing |
| Speaker: Junyuan Lin of Loyola Marymount University |
| Contact: Elizabeth Newman, elizabeth.newman@emory.edu |
| Date: 2021-10-29 at 12:30PM |
| Venue: https://emory.zoom.us/j/94914933211 |
| Download Flyer |
| Abstract: We propose a Multilevel Subgraph Preconditioner (MSP) to efficiently solve linear equations in graph Laplacians corresponding to general weighted graphs. The MSP preconditioner combines the ideas of expanded multilevel structure from multigrid (MG) methods and spanning subgraph preconditioners (SSP) from Computational Graph Theory. To start, we expand the original graph based on a multilevel structure to obtain an equivalent expanded graph. Although the expanded graph has a low diameter, which is a favorable property for the SSP, it has negatively weighted edges, which is an unfavorable property for the SSP. We design an algorithm to properly eliminate the negatively weighted edges and theoretically show that the resulting subgraph with positively weighted edges is spectrally equivalent to the expanded graph. Then, we adopt algorithms to find SSP, such as augmented low stretch spanning trees, for the positively weighted expanded graph and, therefore, provide an MSP for solving the original graph Laplacian. MSP is practical to find thanks to the multilevel property and has provable theoretical convergence bounds based on the support theory for preconditioning graphs. |
See All Seminars