{"599294":{"#nid":"599294","#data":{"type":"event","title":"PhD Proposal by Peng Zhang","body":[{"value":"\u003Cp\u003ETitle:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAlgorithm and Hardness for Graph-Structured Linear Systems\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EPeng Zhang\u003C\/p\u003E\r\n\r\n\u003Cp\u003EPh.D. Student\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESchool of Computer Science\u003C\/p\u003E\r\n\r\n\u003Cp\u003ECollege of Computing\u003C\/p\u003E\r\n\r\n\u003Cp\u003EGeorgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDate:\u0026nbsp;Thursday, December 7th, 2017\u003C\/p\u003E\r\n\r\n\u003Cp\u003ETime:\u0026nbsp;1:00PM (EST)\u003C\/p\u003E\r\n\r\n\u003Cp\u003ELocation: KACB 3402\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003ECommittee:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Richard Peng (Advisor, School of Computer Science, Georgia Institute of Technology)\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Edmond Chow (School of Computational Science and Engineering, Georgia Institute of Technology)\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Milena Mihail (School of Computer Science, Georgia Institute of Technology)\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Santosh Vempala (School of Computer Science, Georgia Institute of Technology)\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Petros Drineas (Department of Computer Science, Purdue University)\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAbstract:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe 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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EI 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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn 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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EBased on joint works with Rasmus Kyng, Richard Peng and Robert Schwieterman.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Algorithm and Hardness for Graph-Structured Linear Systems"}],"uid":"27707","created_gmt":"2017-11-30 15:34:35","changed_gmt":"2017-11-30 15:34:35","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2017-12-07T13:00:00-05:00","event_time_end":"2017-12-07T15:00:00-05:00","event_time_end_last":"2017-12-07T15:00:00-05:00","gmt_time_start":"2017-12-07 18:00:00","gmt_time_end":"2017-12-07 20:00:00","gmt_time_end_last":"2017-12-07 20:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"102851","name":"Phd proposal"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}