CS COLLOQUIUM: Solving Linear Equations -- Rasmus Kyng
Solving systems of linear equations is one of the most fundamental algorithmic problems. In the past fifteen years, theoretical computer scientists have made tremendous progress in developing provably correct, asymptotically fast algorithms for solving structured linear equations.
Linear equations of a type known as Laplacians are extremely useful for analyzing graphs and networks, and they have become a central algorithmic building block of modern fast graph algorithms. Laplacian linear equation solvers also have many applications in scientific computing and engineering. I will present my 'Approximate Gaussian Elimination' algorithm, a very simple procedure for solving Laplacian linear equations. This algorithm may finally give us a practical, fast, and robust solver for these systems, making theoretical developments in the area relevant in practice. We will see some experimental evidence for this.
I will survey my research developing the asymptotically fastest known algorithms for solving linear equations in matrix families known as Laplacians, Connection Laplacians, Directed Laplacians, and 3D truss stiffness matrices. These linear equations are used in algorithms for numerous problems in optimization, engineering, statistics, and data science broadly.
Next, I will explain limits on fast algorithms for solving structured linear equations. My work on complexity lower bounds for solving structured linear equations shows that several classes of linear equations that seem only slightly more general than Laplacians are in fact as hard to solve as arbitrary linear equations.
Finally, I will discuss the future of linear equation solvers, and how ideas from the area can be generalized beyond this setting to obtain new state-of-the-art algorithms for broad classes of problems in convex optimization.
Friday, March 29, 2019 at 11:00am to 12:00pm
St. Mary's Hall, 326
3700 Reservoir Road, N.W., Washington