{"607299":{"#nid":"607299","#data":{"type":"news","title":"SCS Researchers Find Closer Connections Between Geometry and Scientific Computing","body":[{"value":"\u003Cp\u003ESchool of Computer Science (SCS) researchers have made advancements in algorithms for solving structured systems of linear equations. This result, \u003Ca href=\u0022https:\/\/arxiv.org\/abs\/1805.09442\u0022\u003E\u003Cem\u003EIncomplete Nested Dissection\u003C\/em\u003E\u003C\/a\u003E, was presented at the \u003Ca href=\u0022http:\/\/acm-stoc.org\/stoc2018\/\u0022\u003E50th ACM Symposium on Theory of Computing\u003C\/a\u003E (STOC 2018) in Los Angeles from June 25\u0026ndash;29.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESCS Assistant Professor \u003Ca href=\u0022https:\/\/www.cc.gatech.edu\/~rpeng\/\u0022\u003E\u003Cstrong\u003ERichard Peng\u003C\/strong\u003E\u003C\/a\u003E, Ph.D. student \u003Cstrong\u003EPeng Zhang\u003C\/strong\u003E, master\u0026rsquo;s student \u003Ca href=\u0022https:\/\/www.linkedin.com\/in\/robert-schwieterman-b50785152\u0022\u003E\u003Cstrong\u003ERobert Schwieterman\u003C\/strong\u003E\u003C\/a\u003E, and Yale alumnus \u003Ca href=\u0022http:\/\/cs.yale.edu\/homes\/rjkyng\/\u0022\u003E\u003Cstrong\u003ERasmus Kyng\u003C\/strong\u003E\u003C\/a\u003E developed a faster algorithm for geometric 3-D truss linear equations, which is the first improvement for this class of problems since 1990.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIt follows a previous result by Kyng and Zhang that showed, among other results, that general 3-D trusses are difficult to solve. That paper, \u003Ca href=\u0022https:\/\/gatech.us1.list-manage.com\/track\/click?u=de853fab347fb5756a5423781\u0026amp;id=22d1d3106d\u0026amp;e=f040cd217b\u0022\u003E\u003Cem\u003EHardness Results for Structured Linear System\u003C\/em\u003E\u003C\/a\u003Es, won the Machtey Prize for best student paper at the 58th Annual \u003Ca href=\u0022https:\/\/focs17.simons.berkeley.edu\/\u0022\u003EIEEE Symposium on Foundations of Computer Science\u003C\/a\u003E in Berkeley in October 2017.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESolving linear equations is a central tool in statistics, machine learning, optimization, and engineering. However, since algorithms for solving general systems of linear equations are slow, practitioners use additional geometric structure in their problems to get significantly faster linear equation solvers for important cases like finite element simulation used for collision modeling.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EOne important development in this research is the creation of provably correct and fast algorithms for classes of structured linear equations related to heat diffusion and logistics problems in networks for spectral methods and semi-supervised learning on graphs. These are the most important and well-studied systems of equations, and the algorithm provably runs in time close to input size.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;This gives researchers hope that other structured linear equations in other fields\/disciplines? could also be solved quickly by provably correct methods.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ESpeeding up truss equation solvers by geometric methods\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EOne representative class of structured linear equations is truss matrices. They model connections between objects as ideal rods (a notional rod in physics that has no weight, mass, or damping loss). Truss matrices also illustrate the difficulty of designing better algorithms that work for \u003Cem\u003Eany \u003C\/em\u003Estructured input; work on designing provably efficient algorithms for trusses has been ongoing for almost three decades.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe new algorithm for geometric 3-D trusses combines two methods that are workhorses of scientific computing: the conjugate gradient (CG) algorithm and nested dissection.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ECG solves the overall linear system by repeatedly solving similar, but easier systems. Nested dissection, on the other hand, uses the underlying geometry to partition the problem. The team combines these two algorithms, leading to an algorithm that hollows out geometrically local pieces of the trusses (as in the diagram below).\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;While this small improvement is mostly of theoretical value,\u0026rdquo; Kyng said, \u0026ldquo;the directions offered by it are quite exciting. We can now quantify how much geometry helps in scientific computing, and some of the geometrically motivated ideas may extend to more general systems.\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ENot all structures help\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe new algorithm for geometric 3-D trusses comes on the heels of a recent negative result by Zhang and Kyng. In their paper, \u003Ca href=\u0022https:\/\/gatech.us1.list-manage.com\/track\/click?u=de853fab347fb5756a5423781\u0026amp;id=22d1d3106d\u0026amp;e=f040cd217b\u0022\u003E\u003Cem\u003EHardness Results for Structured Linear Systems\u003C\/em\u003E\u003C\/a\u003E, Zhang and Kyng demonstrated that many linear systems with specialized structures, including general 3-D trusses, are not significantly simpler than general systems.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThey demonstrated that any system of linear equations can be written as one with truss structure in 3-D. This gives a reduction, meaning if a better algorithm is found for solving trusses, it would immediately give a better algorithm for solving any system of linear equations. Consequently, general 3-D truss equations without geometric structures are as hard to solve as arbitrary linear equations.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;Before this hardness result, there was optimism that most classes of practically relevant systems can be solved faster,\u0026rdquo; said Peng. \u0026ldquo;The necessity of geometric structures in faster algorithms is surprising to many in the area, but also validates what scientific computing has long believed.\u0026rdquo;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"SCS researchers have made advances in solving structured systems of linear equations."}],"uid":"34541","created_gmt":"2018-06-25 21:29:43","changed_gmt":"2018-06-26 14:10:44","author":"Tess Malone","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2018-06-25T00:00:00-04:00","iso_date":"2018-06-25T00:00:00-04:00","tz":"America\/New_York"},"extras":[],"hg_media":{"607300":{"id":"607300","type":"image","title":"Truss","body":null,"created":"1529962232","gmt_created":"2018-06-25 21:30:32","changed":"1529962232","gmt_changed":"2018-06-25 21:30:32","alt":"truss","file":{"fid":"231648","name":"Trusses.png","image_path":"\/sites\/default\/files\/images\/Trusses.png","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/Trusses.png","mime":"image\/png","size":161420,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/Trusses.png?itok=pSQ_uO6n"}}},"media_ids":["607300"],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003ETess Malone, Communications Officer\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022mailto:tess.malone@cc.gatech.edu\u0022\u003Etess.malone@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E\r\n","format":"limited_html"}],"email":["tess.malone@cc.gatech.edu"],"slides":[],"orientation":[],"userdata":""}}}