PhD Proposal by Peng Zhang

Event Details
  • Date/Time:
    • Thursday December 7, 2017
      1:00 pm - 3:00 pm
  • Location: KACB 3402
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: Algorithm and Hardness for Graph-Structured Linear Systems

Full Summary: No summary paragraph submitted.

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.

 

Additional Information

In Campus Calendar
No
Groups

Graduate Studies

Invited Audience
Faculty/Staff, Public, Graduate students, Undergraduate students
Categories
Other/Miscellaneous
Keywords
Phd proposal
Status
  • Created By: Tatianna Richardson
  • Workflow Status: Published
  • Created On: Nov 30, 2017 - 10:34am
  • Last Updated: Nov 30, 2017 - 10:34am