Title:

Algorithm and Hardness for Graph-Structured Linear Systems

Peng Zhang

Ph.D. Student

School of Computer Science

College of Computing

Georgia Institute of Technology

Date: Thursday, December 7th, 2017

Time: 1:00PM (EST)

Location: KACB 3402

Committee:

Dr. Richard Peng (Advisor, School of Computer Science, Georgia Institute of Technology)

Dr. Edmond Chow (School of Computational Science and Engineering, Georgia Institute of Technology)

Dr. Milena Mihail (School of Computer Science, Georgia Institute of Technology)

Dr. Santosh Vempala (School of Computer Science, Georgia Institute of Technology)

Dr. Petros Drineas (Department of Computer Science, Purdue University)

Abstract:

We study graph-structured linear systems. In this proposal, we mainly focus on linear systems in truss stiffness matrices, and we believe the same ideas extensible for more general graph-structured linear systems. Linear systems in truss stiffness matrices arise from linear elasticity problems, for simulating forces on 2D or 3D embedded objects. Truss stiffness matrices are a special case of PSD-Graph-Structured Block Matrices (PGSBM). PGSBMs can be viewed as generalizations of graph Laplacians, by extending a single label per vertex to multiple labels per vertex. These matrices have been studied in scientific computing and optimizations.

I will present an algorithm for solving linear systems in well-shaped 3D trusses, which are meshes of tetrahedrons of constant volume and constant aspect ratio each. By utilizing the geometric structures, we combine nested dissection and support theory. Both are well-studied techniques but usually applied separately.

In addition, I will show that these geometric structures are ``necessary`` for designing fast solvers for truss linear systems. Specifically, solving linear systems in general trusses is as hard as solving linear systems over the reals. This is different from the existing nearly-linear time solvers for some PGSBMs, e.g., graph Laplacians, connection Laplacians. Furthermore, I will give more examples of PGSBMs such that solving these linear systems is as hard as solving linear systems over the reals.

Based on joint works with Rasmus Kyng, Richard Peng and Robert Schwieterman.