{"669854":{"#nid":"669854","#data":{"type":"event","title":"School of CSE Seminar Series: Rasmus Kyng","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ESpeaker:\u003C\/strong\u003E\u0026nbsp;Assistant Professor Rasmus Kyng, ETH Zurich\u003Cbr \/\u003E\r\n\u003Cstrong\u003EDate and Time:\u003C\/strong\u003E\u0026nbsp;September 29, 2:00-3:00 p.m.\u003Cbr \/\u003E\r\n\u003Cstrong\u003ELocation:\u003C\/strong\u003E\u0026nbsp;Coda, Room 114\u003Cbr \/\u003E\r\n\u003Cstrong\u003EHost:\u003C\/strong\u003E\u0026nbsp;School of CSE Professor Edmond Chow\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E\u003Cem\u003ERobust and Practical Solution of Laplacian Equations by Approximate Elimination\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp;\u003C\/strong\u003EIn this talk, I will describe a new algorithm for solving Laplacian (and SDDM) linear equations. We introduce a variant of the approximate Cholesky factorization of Kyng and Sachdeva (FOCS 2016), and we experimentally demonstrate that this method performs well in practice across a broad range of problem classes. Our experiments suggest that our solver is much more robust than existing solvers for Laplacian linear equations, while retaining good performance across all instances.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EOur factorization approach is simple: we eliminate matrix rows\/columns one at a time and use sampling to update the remaining entries of the matrix, approximating complete Cholesky factorization. Unlike earlier approaches, our sampled entries always maintain a connected support graph on the neighbors of the eliminated variable.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis talk is based on joint work with Yuan Gao and Daniel Spielman.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EPreprint:\u0026nbsp;\u003Ca href=\u0022https:\/\/arxiv.org\/abs\/2303.00709\u0022\u003Ehttps:\/\/arxiv.org\/abs\/2303.00709\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio:\u0026nbsp;\u003C\/strong\u003ERasmus Kyng is an assistant professor of theoretical computer science at ETH Zurich. Before joining the ETH CS department in 2019, he was a postdoctoral fellow at Harvard SEAS and the Simons Institute at UC Berkeley. In 2017, he received a PhD in computer science from Yale University, where he was advised by Daniel Spielman.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EHis work focuses on fast algorithms for solving graph problems, convex optimization, and structured linear equations. In addition, he develops hardness results for basic algorithmic problems and probability theoretic tools for algorithmic applications. His research has won the FOCS\u002722 best paper and FOCS\u002717 best student paper awards, and the ICBS 2023 Frontiers of Science Award for Best Paper in Theoretical Computer Science 2018-2022.\u003C\/p\u003E\r\n","summary":"","format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003E\u003Cstrong\u003ESpeaker:\u003C\/strong\u003E\u0026nbsp;Assistant Professor Rasmus Kyng, ETH Zurich\u003Cbr \/\u003E\r\n\u003Cstrong\u003EDate and Time:\u003C\/strong\u003E\u0026nbsp;September 29, 2:00-3:00 p.m.\u003Cbr \/\u003E\r\n\u003Cstrong\u003ELocation:\u003C\/strong\u003E\u0026nbsp;Coda, Room 114\u003Cbr \/\u003E\r\n\u003Cstrong\u003EHost:\u003C\/strong\u003E\u0026nbsp;School of CSE Professor Edmond Chow\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E\u003Cem\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003ERobust and Practical Solution of Laplacian Equations by Approximate Elimination\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/em\u003E\u003C\/p\u003E\r\n","format":"limited_html"}],"field_summary_sentence":[{"value":"School of CSE hosts a seminar from Rasmus Kyng, assistant professor at ETH Zurich"}],"uid":"36319","created_gmt":"2023-09-22 15:39:33","changed_gmt":"2023-09-22 15:41:51","author":"Bryant Wine","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2023-09-29T14:00:00-04:00","event_time_end":"2023-09-29T15:00:00-04:00","event_time_end_last":"2023-09-29T15:00:00-04:00","gmt_time_start":"2023-09-29 18:00:00","gmt_time_end":"2023-09-29 19:00:00","gmt_time_end_last":"2023-09-29 19:00:00","rrule":null,"timezone":"America\/New_York"},"location":"Coda, Room 114","extras":["free_food"],"hg_media":{"671797":{"id":"671797","type":"image","title":"Rasmus Kyng.jpeg","body":null,"created":"1695397187","gmt_created":"2023-09-22 15:39:47","changed":"1695397187","gmt_changed":"2023-09-22 15:39:47","alt":"Rasmus Kyng","file":{"fid":"254925","name":"Rasmus Kyng.jpeg","image_path":"\/sites\/default\/files\/2023\/09\/22\/Rasmus%20Kyng.jpeg","image_full_path":"http:\/\/hg.gatech.edu\/\/sites\/default\/files\/2023\/09\/22\/Rasmus%20Kyng.jpeg","mime":"image\/jpeg","size":192426,"path_740":"http:\/\/hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/2023\/09\/22\/Rasmus%20Kyng.jpeg?itok=nZcwEJul"}}},"media_ids":["671797"],"groups":[{"id":"50877","name":"School of Computational Science and Engineering"},{"id":"47223","name":"College of Computing"}],"categories":[],"keywords":[{"id":"76231","name":"Computational Science and Engineering"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"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":[{"value":"\u003Cp\u003E\u003Cstrong\u003EHost:\u003C\/strong\u003E Edmond Chow\u0026nbsp;(\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003Eechow@cc.gatech.edu\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E)\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}