University of Colorado
Fox, Alyson Lindsey.
Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs.
Degree: PhD, Applied Mathematics, 2017, University of Colorado
Relational datasets are often modeled as an unsigned, undirected graph due the nice properties of the resulting graph Laplacian, but information is lost if certain attributes of the graph are not represented. This thesis presents two generalizations of Algebraic Multigrid (AMG) solvers with graph Laplacian systems for different graph types: applying Gremban’s expansion to extend unsigned graph Laplacian solvers to signed graph Laplacian systems and generalizing techniques in Lean Algebraic Multigrid (LAMG) to a new multigrid solver for unsigned, directed graph Laplacian systems. Signed graphs extend the traditional notion of connections and disconnections to in- clude both favorable and adverse relationships, such as friend-enemy social networks or social networks with “likes” and “dislikes.” Gremban’s expansion is used to transform the signed graph Laplacian into an unsigned graph Laplacian with twice the number of unknowns. By using Gremban’s expansion, we extend current unsigned graph Laplacian solvers’ to signed graph Laplacians. This thesis analyzes the numerical stability and applicability of Grem- ban’s expansion and proves that the error of the solution of the original linear system can be tightly bounded by the error of the expanded system. In directed graphs, some subset of relationships are not reciprocal, such as hyperlink graphs, biological neural networks, and electrical power grids. A new algebraic multigrid algorithm, Nonsymmetric Lean Algebraic Multigrid (NS-LAMG), is proposed, which uses ideas from Lean Algebraic Multigrid, nonsymmetric Smoothed Aggregation, and multigrid solvers for Markov chain stationary distribution systems. Low-degree elimination, intro- duced in Lean Algebraic Multigrid for undirected graphs, is redefined for directed graphs. A semi-adaptive multigrid solver, inspired by low-degree elimination, is instrumented in the setup phase, which can be adapted for Markov chain stationary distributions systems. Nu- merical results shows that NS-LAMG out performs GMRES(k) for real-world, directed graph Laplacian linear systems. Both generalizations enable more choices in modeling decisions for graph Laplacian systems. Due the successfulness of NS-LAMG and other various nonsymmetric AMG (NS-AMG) solvers, a further study of theoretical convergence properties are discussed in this thesis. In particular, a necessary condition known as “weak approximation property”, and a sufficient one, referred to as “strong approximation property” as well as the “super strong approx- imation property” are generalized to nonsymmetric matrices and the various relationships between the approximation properties are proved for the nonsymmetric case. In NS-AMG, if P ̸= R the two-grid error propagation operator for the coarse-grid correction is an oblique projection with respect to any reasonable norm, which can cause the error to increase. A main focal point of this paper is a discussion on the conditions in which the error propagation operator is bounded, as the stability of the error…
Advisors/Committee Members: Tom Manteuffel, Geoff Sanders, John Ruge, Christian Ketelsen, Francois Meyer.
Subjects/Keywords: Algebraic Multigrid; Directed graphs; Graph Laplacians; Gremban's expansion; Signed graphs; Applied Mechanics
to Zotero / EndNote / Reference
APA (6th Edition):
Fox, A. L. (2017). Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/96
Chicago Manual of Style (16th Edition):
Fox, Alyson Lindsey. “Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs.” 2017. Doctoral Dissertation, University of Colorado. Accessed March 05, 2021.
MLA Handbook (7th Edition):
Fox, Alyson Lindsey. “Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs.” 2017. Web. 05 Mar 2021.
Fox AL. Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs. [Internet] [Doctoral dissertation]. University of Colorado; 2017. [cited 2021 Mar 05].
Available from: https://scholar.colorado.edu/appm_gradetds/96.
Council of Science Editors:
Fox AL. Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs. [Doctoral Dissertation]. University of Colorado; 2017. Available from: https://scholar.colorado.edu/appm_gradetds/96