EUVIMEDEUVIMED entdecken
Crossref

Lx = b Laplacian Solvers and Their Algorithmic Applications

Nisheeth K. Vishnoi

Foundations and Trends® in Theoretical Computer Science · 2013

DOI: 10.1561/0400000054 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Foundations and Trends® in Theoretical Computer Science, 2013. Verfasst von Nisheeth K. Vishnoi. Die Arbeit wurde bisher 63-mal zitiert (Crossref) und nennt 89 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 nearlylinear 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.

Zitieren

APA

Vishnoi, N. K. (2013). Lx = b Laplacian Solvers and Their Algorithmic Applications. Foundations and Trends® in Theoretical Computer Science. https://doi.org/10.1561/0400000054

Vancouver

Vishnoi NK. Lx = b Laplacian Solvers and Their Algorithmic Applications. Foundations and Trends® in Theoretical Computer Science. 2013. doi:10.1561/0400000054

BibTeX
@article{Vishnoi2013,
  author = {Vishnoi, Nisheeth K.},
  title = {Lx = b Laplacian Solvers and Their Algorithmic Applications},
  journal = {Foundations and Trends® in Theoretical Computer Science},
  year = {2013},
  doi = {10.1561/0400000054}
}
Kostenlos starten →