Show simple item record

dc.contributor.advisor Knepley, Matthew G
dc.creatorBuras, Eric
dc.date.accessioned 2017-08-07T18:38:59Z
dc.date.available 2017-08-07T18:38:59Z
dc.date.created 2016-05
dc.date.issued 2016-05-17
dc.date.submitted May 2016
dc.identifier.citation Buras, Eric. "A Multigrid Solver for Graph Laplacian Linear Systems on Power-Law Graphs." (2016) Master’s Thesis, Rice University. https://hdl.handle.net/1911/96624.
dc.identifier.urihttps://hdl.handle.net/1911/96624
dc.description.abstract The Laplacian matrix, L, of a graph, G, contains degree and edge information of a given network. Solving a Laplacian linear system Lx = b provides information about flow through the network, and in specific cases, how that information orders the nodes in the network. I propose a novel way to solve this linear system by first partitioning G into its maximum locally-connected subgraph and a small subgraph of the remaining so-called "teleportation" edges. I then apply optimal multigrid solves to the locally-connected subgraph, and linear algebra and a solve on the teleportation subgraph to solve the original linear system. I show results for this method on real-world graphs from the biological systems of the C. Elegans worm, Facebook friend networks, and the power grid of the Western United States.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectLaplacian
Multigrid
dc.title A Multigrid Solver for Graph Laplacian Linear Systems on Power-Law Graphs
dc.date.updated 2017-08-07T18:38:59Z
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computational and Applied Mathematics
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Masters
thesis.degree.name Master of Arts


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record