Hodge Laplacians on simplicial meshes and graphs

Kalyanaraman, Kaushik

Permalink

https://hdl.handle.net/2142/89049 Copy

Description

Title

Hodge Laplacians on simplicial meshes and graphs

Author(s)

Kalyanaraman, Kaushik

Issue Date

2015-12-04

Director of Research (if dissertation) or Advisor (if thesis)

Hirani, Anil N.

Doctoral Committee Chair(s)

Hirani, Anil N.

Committee Member(s)

• Demlow, Alan
• Erickson, Jeff
• Heath, Michael

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Computational analysis
• discrete exterior calculus
• finite element exterior calculus
• harmonics
• Hodge Laplacians
• ranking on graphs

Abstract

We present in this dissertation some developments in the discretizations of exterior calculus for problems posed on simplicial discretization (meshes) of geometric manifolds and analogous problems on abstract simplicial complexes. We are primarily interested in discretizations of elliptic type partial differential equations, and our model problem is the Hodge Laplacian Poisson problem on differential k-forms on n dimensional manifolds. One of our major contributions in this work is the computational quantification of the solution using the weak mixed formulation of this problem on simplicial meshes using discrete exterior calculus (DEC), and its comparisons with the solution due to a different discretization framework, namely, finite element exterior calculus (FEEC). Consequently, our important computational result is that the solution of the Poisson problem on different manifolds in two- and three-dimensions due to DEC recovers convergence properties on many sequences of refined meshes similar to that of FEEC. We also discuss some potential attempts for showing this convergence theoretically. In particular, we demonstrate that a certain formulation of a variational crimes approach that can be used for showing convergence for a generalized FEEC may not be directly applicable to DEC convergence in its current formulation. In order to perform computations using DEC, a key development that we present is exhibiting sign rules that allow for the computation of the discrete Hodge star operators in DEC on Delaunay meshes in a piecewise manner. Another aspect of computationally solving the Poisson problem using the mixed formulation with either DEC or FEEC requires knowing the solution to the corresponding Laplace's problem, namely, the harmonics. We present a least squares method for computing a basis for the space of such discrete harmonics via their isomorphism to cohomology. We also provide some numerics to quantify the efficiency of this solution in comparison with previously known methods. Finally, we demonstrate an application to obtain the ranking of pairwise comparison data. We model this data as edge weights on graphs with 3-cliques included and perform its Hodge decomposition by solving two least squares problems. An outcome of this exploration is also providing some computational evidence that algebraic multigrid linear solvers for the resulting linear systems on Erdős-Rényi random graphs and on Barabási-Albert graphs do not perform very well in comparison with iterative Krylov solvers.

Graduation Semester

2015-12

Type of Resource

text

Permalink

http://hdl.handle.net/2142/89049

Copyright and License Information

Copyright 2015 Kaushik Kalyanaraman

Owning Collections