Foundations and Trends® in Theoretical Computer Science > Vol 8 > Issue 1–2

Lx = b

By Nisheeth K. Vishnoi, Microsoft Research, India, nisheeth.vishnoi@gmail.com

 
Suggested Citation
Nisheeth K. Vishnoi (2013), "Lx = b", Foundations and Trends® in Theoretical Computer Science: Vol. 8: No. 1–2, pp 1-141. http://dx.doi.org/10.1561/0400000054

Publication Date: 23 May 2013
© 2013 N. K. Vishnoi
 
Subjects
Segmentation and grouping,  Clustering,  Spectral methods,  Computational aspects of combinatorics and graph theory,  Design and analysis of algorithms
 

Free Preview:

Download extract

Share

Download article
In this article:
Preface 
Notation 
I. Basics: 
1. Basic Linear Algebra 
2. The Graph Laplacian 
3. Laplacian Systems and Solvers 
4. Graphs as Electrical Networks 
II. Applications: 
5. Graph Partitioning I The Normalized Laplacian 
6. Graph Partitioning II A Spectral Algorithm for Conductance 
7. Graph Partitioning III Balanced Cuts 
8. Graph Partitioning IV Computing the Second Eigenvector 
9. The Matrix Exponential and Random Walks 
10. Graph Sparsification I Sparsification via Effective Resistances 
11. Graph Sparsification II Computing Electrical Quantities 
12. Cuts and Flows 
III. Tools: 
13. Cholesky Decomposition Based Linear Solvers 
14. Iterative Linear Solvers I The Kaczmarz Method 
15. Iterative Linear Solvers II The Gradient Method 
16. Iterative Linear Solvers III The Conjugate Gradient Method 
17. Preconditioning for Laplacian Systems 
18. Solving a Laplacian System in Õ(m) Time 
19. Beyond Ax = b The Lanczos Method 
References 

Abstract

The ability to solve a system of linear equations lies at the heart of areas such as optimization, scientific computing, and computer science, and has traditionally been a central topic of research in the area of numerical linear algebra. An important class of instances that arise in practice has the form Lx = b, where L is the Laplacian of an undirected graph. After decades of sustained research and combining tools from disparate areas, we now have Laplacian solvers that run in time nearly-linear in the sparsity (that is, the number of edges in the associated graph) of the system, which is a distant goal for general systems. Surprisingly, and perhaps not the original motivation behind this line of research, Laplacian solvers are impacting the theory of fast algorithms for fundamental graph problems. In this monograph, the emerging paradigm of employing Laplacian solvers to design novel fast algorithms for graph problems is illustrated through a small but carefully chosen set of examples. A part of this monograph is also dedicated to developing the ideas that go into the construction of near-linear-time Laplacian solvers. An understanding of these methods, which marry techniques from linear algebra and graph theory, will not only enrich the tool-set of an algorithm designer but will also provide the ability to adapt these methods to design fast algorithms for other fundamental problems.

DOI:10.1561/0400000054
ISBN: 978-1-60198-946-8
154 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-60198-657-3
154 pp. $230.00
Buy E-book (.pdf)
Table of contents:
Preface
Notation
Part I Basics:
1. Basic Linear Algebra
2. The Graph Laplacian
3. Laplacian Systems and Solvers
4. Graphs as Electrical Networks
Part II Applications:
5. Graph Partitioning I The Normalized Laplacian
6. Graph Partitioning II A Spectral Algorithm for Conductance
7. Graph Partitioning III Balanced Cuts
8. Graph Partitioning IV Computing the Second Eigenvector
9. The Matrix Exponential and Random Walks
10. Graph Sparsification I Sparsification via Effective Resistances
11. Graph Sparsification II Computing Electrical Quantities
12. Cuts and Flows
Part III Tools:
13. Cholesky Decomposition Based Linear Solvers
14. Iterative Linear Solvers I The Kaczmarz Method
15. Iterative Linear Solvers II The Gradient Method
16. Iterative Linear Solvers III The Conjugate Gradient Method
17. Preconditioning for Laplacian Systems
18. Solving a Laplacian System in Õ(m) Time
19. Beyond Ax=b The Lanczos Method
References

Lx = b

The ability to solve a system of linear equations lies at the heart of areas like optimization, scientific computing, and computer science and has traditionally been a central topic of research in the area of numerical linear algebra. An important class of instances that arise in practice has the form Lx=b where L is the Laplacian of an undirected graph. After decades of sustained research and combining tools from disparate areas, we now have Laplacian solvers that run in time nearly-linear in the sparsity of the system, which is a distant goal for general systems. Surprisingly, Laplacian solvers are impacting the theory of fast algorithms for fundamental graph problems. In this monograph, the emerging paradigm of employing Laplacian solvers to design novel fast algorithms for graph problems is illustrated through a small but carefully chosen set of examples. A significant part of this monograph is also dedicated to developing the ideas that go into the construction of near-linear time Laplacian solvers. An understanding of these methods, which marry techniques from linear algebra and graph theory, will not only enrich the tool-set of an algorithm designer but will also provide the ability to adapt these methods to design fast algorithms for other fundamental problems. This monograph can be used as the text for a graduate-level course, or act as a supplement to a course on spectral graph theory or algorithms. The writing style, which deliberately emphasizes the presentation of key ideas over rigor, will make it accessible to advanced undergraduates.

 
TCS-054