2 Search Results for "Levin, Alex"

Document
DOI: 10.4230/LIPIcs.STACS.2012.266
Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices

Authors: Ioannis Koutis, Alex Levin, and Richard Peng

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We present three spectral sparsification algorithms that, on input a graph G with n vertices and m edges, return a graph H with n vertices and O(n log n/epsilon^2) edges that provides a strong approximation of G. Namely, for all vectors x and any epsilon>0, we have (1-epsilon) x^T L_G x <= x^T L_H x <= (1+epsilon) x^T L_G x, where L_G and L_H are the Laplacians of the two graphs. The first algorithm is a simple modification of the fastest known algorithm and runs in tilde{O}(m log^2 n) time, an O(log n) factor faster than before. The second algorithm runs in tilde{O}(m log n) time and generates a sparsifier with tilde{O}(n log^3 n) edges. The third algorithm applies to graphs where m>n log^5 n and runs in tilde{O}(m log_{m/ n log^5 n} n time. In the range where m>n^{1+r} for some constant r this becomes softO(m). The improved sparsification algorithms are employed to accelerate linear system solvers and algorithms for computing fundamental eigenvectors of dense SDD matrices.
Cite as

Ioannis Koutis, Alex Levin, and Richard Peng. Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 266-277, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{koutis_et_al:LIPIcs.STACS.2012.266,
  author =	{Koutis, Ioannis and Levin, Alex and Peng, Richard},
  title =	{{Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{266--277},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.266},
  URN =		{urn:nbn:de:0030-drops-34348},
  doi =		{10.4230/LIPIcs.STACS.2012.266},
  annote =	{Keywords: Spectral sparsification, linear system solving}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.440
Spectral Sparsification in the Semi-Streaming Setting

Authors: Jonathan A. Kelner and Alex Levin

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
Let G be a graph with n vertices and m edges. A sparsifier of G is a sparse graph on the same vertex set approximating $G$ in some natural way. It allows us to say useful things about $G$ while considering much fewer than m edges. The strongest commonly-used notion of sparsification is spectral sparsification; H is a spectral sparsifier of G if the quadratic forms induced by the Laplacians of G and H approximate one another well. This notion is strictly stronger than the earlier concept of combinatorial sparsification. In this paper, we consider a semi-streaming setting, where we have only ~O(n) storage space, and we thus cannot keep all of G. In this case, maintaining a sparsifier instead gives us a useful approximation to G, allowing us to answer certain questions about the original graph without storing all of it. In this paper, we introduce an algorithm for constructing a spectral sparsifier of G with O(n log n/epsilon^2) edges (where epsilon is a parameter measuring the quality of the sparsifier), taking ~O(m) time and requiring only one pass over G. In addition, our algorithm has the property that it maintains at all times a valid sparsifier for the subgraph of G that we have received. Our algorithm is natural and conceptually simple. As we read edges of $G,$ we add them to the sparsifier $H$. Whenever $H$ gets too big, we resparsify it in $tilde O(n)$ time. Adding edges to a graph changes the structure of its sparsifier's restriction to the already existing edges. It would thus seem that the above procedure would cause errors to compound each time that we resparsify, and that we should need to either retain significantly more information or reexamine previously discarded edges in order to construct the new sparsifier. However, we show how to use the information contained in $H$ to perform this resparsification using only the edges retained by earlier steps in nearly linear time.
Cite as

Jonathan A. Kelner and Alex Levin. Spectral Sparsification in the Semi-Streaming Setting. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 440-451, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kelner_et_al:LIPIcs.STACS.2011.440,
  author =	{Kelner, Jonathan A. and Levin, Alex},
  title =	{{Spectral Sparsification in the Semi-Streaming Setting}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{440--451},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.440},
  URN =		{urn:nbn:de:0030-drops-30332},
  doi =		{10.4230/LIPIcs.STACS.2011.440},
  annote =	{Keywords: algorithms and data structures, graph algorithms, spectral graph theory, sub-linear space algorithms, spectral sparsification}
}
  • Refine by Author
  • 2 Levin, Alex
  • 1 Kelner, Jonathan A.
  • 1 Koutis, Ioannis
  • 1 Peng, Richard

  • Refine by Classification

  • Refine by Keyword
  • 1 Spectral sparsification
  • 1 algorithms and data structures
  • 1 graph algorithms
  • 1 linear system solving
  • 1 spectral graph theory
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2011
  • 1 2012

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact