The Laplacian Matrices of Graphs: Algorithms and Applications
Monday,
November 13, 2017
11:30 AM - 12:30 PM
Dan Spielman, Yale
The Laplacian matrices of graphs arise in many fields, including Machine Learning, Computer Vision, Optimization, Computational Science, and of course Network Analysis. We will explain what these matrices are and why they appear in so many applications. We then survey recent ideas that allow us to solve systems of linear equations in Laplacian matrices in nearly linear time, emphasizing the utility of graph sparsification---the approximation of a graph by a sparser one---and a recent algorithm of Kyng and Sachdeva that uses random sampling to accelerate Gaussian Elimination.
The Laplacian matrices of graphs arise in many fields, including Machine Learning, Computer Vision, Optimization, Computational Science, and of course Network Analysis. We will explain what these matrices are and why they appear in so many applications. We then survey recent ideas that allow us to solve systems of linear equations in Laplacian matrices in nearly linear time, emphasizing the utility of graph sparsification---the approximation of a graph by a sparser one---and a recent algorithm of Kyng and Sachdeva that uses random sampling to accelerate Gaussian Elimination.
LOCATION:
← BACK TO EVENTS
- Morningside
- Lecture
- Computer Science
- Engineering
- Staff
- Faculty
- Students
Date Navigation Widget
Getting to Columbia
Other Calendars
- Alumni Events
- Barnard College
- Columbia Business School
- Columbia College
- Committee on Global Thought
- Heyman Center
- Jewish Theological Seminary
- Miller Theatre
- School of Engineering & Applied Science
- School of Social Work
- Teachers College
Guests With Disabilities
- Columbia University makes every effort to accommodate individuals with disabilities. Please notify us if you need any assistance by contacting the event’s point person. Alternatively, the Office of Disability Services can be reached at 212.854.2388 and [email protected]. Thank you.