*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
