License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.41
URN: urn:nbn:de:0030-drops-75908
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7590/
Go to the corresponding LIPIcs Volume Portal

Doron, Dean ; Le Gall, François ; Ta-Shma, Amnon

Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers

pdf-format:
LIPIcs-APPROX-RANDOM-2017-41.pdf (0.6 MB)

Abstract

A recent series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system Lx=b, where L is the normalized Laplacian of an undirected graph. In this paper we study the space complexity of the problem. Surprisingly we are able to show a probabilistic, logspace algorithm solving the problem. We further extend the algorithm to other families of graphs like Eulerian graphs (and directed regular graphs) and graphs that mix in polynomial time.

Our approach is to pseudo-invert the Laplacian, by first "peeling-off" the problematic kernel of the operator, and then to approximate the inverse of the remaining part by using a Taylor series. We approximate the Taylor series using a previous work and the special structure of the problem. For directed graphs we exploit in the analysis the Jordan normal form and results from matrix functions.

BibTeX - Entry

@InProceedings{doron_et_al:LIPIcs:2017:7590,
  author =	{Dean Doron and Fran{\c{c}}ois Le Gall and Amnon Ta-Shma},
  title =	{{Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{41:1--41:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7590},
  URN =		{urn:nbn:de:0030-drops-75908},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.41},
  annote =	{Keywords: Laplacian solvers, Randomized logspace, Bounded-space complexity classes, Random walks, Matrix computation}
}

Keywords: Laplacian solvers, Randomized logspace, Bounded-space complexity classes, Random walks, Matrix computation
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 11.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI