5th HLF – Lecture: Approximate Elimination

Bewegte Bilder

We provide context for and explain the recent Approximate Gaussian Elimination algorithm of Kyng and Sachdeva. Gaussian Elimination is the first algorithm most of us learn for solving systems of linear equations. While it is simple and elegant, it can also be impractically slow. Kyng and Sachdeva show that, after carefully modifying elimination to randomly drop and rescale entries, it can provide very fast approximate solutions to systems of equations in Laplacian matrices. Our implementation of a refinement of this algorithm is now among the best Laplacian solvers in practice. We will explain what Laplacian matrices are, what it means to approximately solve a system of linear equations over the reals, and how one analyzes this algorithm using recent results in Random Matrix Theory. We will also discuss what is means for an algorithm to be the "best in practice." The opinions expressed in this video do not necessarily reflect the views of the Heidelberg Laureate Forum Foundation or any other person or associated institution involved in the making and distribution of the video.

Objekt anzeigen

• Standort: Hannover TIB
• Umfang: 303MB, 00:30:38:00 (unknown)
• Sprache: Englisch
• Anmerkungen: Audiovisuelles Material

Verweise und Beziehungen

• Erschienen in: 5th Heidelberg Laureate Forum (HLF), 2017 ; (Jan. 2017)

Beteiligte, Orts- und Zeitangaben

• Ereignis: Veröffentlichung
• (wer): Heidelberg Laureate Forum Foundation
• (wann): 2017-01-01
• Beteiligte Personen und Organisationen: Spielman, Daniel A.

Weitere Informationen

• DOI: 10.5446/40131