Machine Learning Summer School on Theory and Practice of Computational Learning

Spectral Graph Theory, Linear Solvers and Applications

author: Gary L Miller, School of Computer Science, Carnegie Mellon University

Description

We discuss the development of combinatorial methods for solving symmetric diagonally dominate linear systems. Over the last fifteen years the computer science community has made substantial progress in fast solvers for SDD systems. For general SDD systems the upper bound is $0(m \log^k n)$ for some constant $k$, where $m$ is the number of non-zero entries, due to Spielman and Teng. Newer methods, combinatorial multigrid, have linear time guarantee for the planar case and work very well in practice. Critical to the use of these new solvers has been the reduction of problems to the solution of SDD systems. We present some of these reductions, including several from image processing.

You might be experiencing some problems with Your Video player.

*Slides*
0:00	Spectral Graph Theory, Linear Solvers, and Applications
0:44	Linear Systems
1:15	Matrix Form
1:33	Solving the General Case (1)
1:53	Solving the General Case (2)
2:01	An Easy Case (1)
2:11	An Easy Case (2)
2:18	An Easy Case (3)
2:26	Symmetric Matrices (1)
2:43	Symmetric Matrices (2)
3:02	Direct Methods Gaussian Elimination Matrices (1)
3:39	Direct Methods Gaussian Elimination Matrices (2)
3:56	Pivoting (1)
4:08	Pivoting (2)
4:21	Pivoting (2)
4:24	Pivoting (3)
4:42	Good Pivot Strategies (1)
5:11	Good Pivot Strategies (2)
5:32	Good Pivot Strategies (3)
5:45	Pure Iterative Methods (1)
6:13	Pure Iterative Methods (2)
6:24	Pure Iterative Methods (3)
6:40	Pure Iterative Methods (4)
6:51	Preconditioned Iterative Methods (1)
7:32	Preconditioned Iterative Methods (2)
8:24	Preconditioned Iterative Methods (3)
8:52	Classic Preconditioners (1)
9:06	Classic Preconditioners (2)
9:35	Classic Preconditioners (3)
9:54	Classic Preconditioners (4)
11:10	Graph Laplacian (1)
11:43	Graph Laplacian (2)
11:52	Graph Laplacian (3)
12:00	Graph Laplacian (4)
12:04	Graph Laplacian (5)
12:15	Classic Applications of the Laplacian (1)
12:58	Classic Applications of the Laplacian (2)
13:07	Classic Applications of the Laplacian (3)
13:49	Graph Laplacian’s and the Heat Equations
13:57	Graph Laplacian’s and Random Walks
15:17	Laplacian’s and Spring Mass Systems (1)
15:40	Laplacian’s and Spring Mass Systems (2)
15:46	Laplacian’s and Spring Mass Systems (3)
16:24	Spring Mass Systems
18:53	Spanning Tree Preconditioners (1)
21:53	Spanning Tree Preconditioners (2)
22:18	Spanning Tree Preconditioners (3)
22:29	Low Stretch Spanning Trees (1)
22:51	Low Stretch Spanning Trees (2)
22:57	Low Stretch Spanning Trees (3)
23:02	Low Stretch Spanning Trees (4)
23:21	Steiner Tree Preconditioners (1)
23:52	Steiner Tree Preconditioners (2)
24:00	Steiner Tree Preconditioners (3)
24:06	Steiner Tree Preconditioners (4)
24:20	Steiner Forest Preconditioners (1)
25:03	Steiner Forest Preconditioners (2)
25:08	Steiner Forest Preconditioners (3)
25:12	Steiner Forest Preconditioners (4)
25:21	Recursive Methods (1)
26:11	Recursive Methods (2)
26:34	The Error (1)
26:56	The Error (2)
27:03	The Error (3)
27:11	The Error (4)
27:19	Condition Number (1)
27:22	Condition Number (2)
27:39	Condition Number (3)
27:53	Condition Number (4)
28:02	Convergence Rates (1)
28:11	Convergence Rates (2)
28:17	Convergence Rates (3)
28:43	Generalized Condition Number (1)
28:55	Generalized Condition Number (2)
29:05	Generalized Condition Number (3)
29:17	Generalized Condition Number (4)
29:24	The Support (1)
29:46	The Support (2)
30:23	The Support (3)
30:46	Estimating Support
31:15	Estimating Support Example
35:03	History of Planar Solvers (1)
35:37	History of Planar Solvers (2)
35:49	History of Planar Solvers (3)
35:57	History of Planar Solvers (4)
36:04	History of Planar Solvers (6)
36:39	General Laplacian Solver (1)
37:31	General Laplacian Solver (2)
38:31	General Laplacian Solver (3)
39:01	Symmetric Diagonally Dominate Systems (1)
40:05	Symmetric Diagonally Dominate Systems (2)
40:32	Symmetric Diagonally Dominate Systems (3)
40:42	Symmetric Diagonally Dominate Systems (4)
40:51	Symmetric Diagonally Dominate Systems (4)
41:27	Symmetric Diagonally Dominate Systems (5)
41:34	Basic Properties: Generalized Laplacian (1)
42:42	Basic Properties: Generalized Laplacian (2)
43:16	Basic Properties: Generalized Laplacian (3)
43:25	Solving Generalized Laplacian by Change of Variables (1)
43:43	Solving Generalized Laplacian by Change of Variables (2)
44:10	Solving Generalized Laplacian by Change of Variables (3)
44:39	Generalized Laplacians Example
45:29	Change of Variables for Laplacians
46:33	Orientable Generalized Laplacians (1)
47:59	Orientable Generalized Laplacians (2)
48:08	Orientable Generalized Laplacians (3)
48:48	Orientable Generalized Laplacians (4)
49:04	Orientable Generalized Laplacians (5)
49:18	Orientable Generalized Laplacians (6)
49:29	Orientable Generalized Laplacians (7)
49:59	Two-Fold Covers (1)
50:23	Two-Fold Covers (2)
50:39	Two-Fold Covers (3)
50:59	Two-Fold Covers (4)
51:22	Example: Two-Fold Cover
53:56	Two-Fold Covers and Solving Generalized Laplacians (1)
54:16	Two-Fold Covers and Solving Generalized Laplacians (2)
54:23	Two-Fold Covers and Solving Generalized Laplacians (3)
55:21	Two-Fold Covers and Solving Generalized Laplacians (4)
56:40	SDD systems (1)
56:43	SDD systems (2)
56:55	SDD systems (3)
57:03	Spectral Graph Partitioning
57:15	Open Questions

Lecture rating

People found this lecture:
Worth seeing
because it is:
Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.