Where n is dimensions of the matrix representing the linear system of equations, m the number of non-zero entries in the matrix.

This is from a new paper by Koutis, Miller and Peng all from Carnegie Mellon: http://arxiv.org/pdf/1003.2958

I'm used to O(n^3) methods I learned in undergrad linear algebra. This kind of blows my mind. The only trouble is that I have no idea how it works. If I could get some pointers that would explain the groundwork (terms like graph sparsifiers and combinatorial preconditioner are bandied about just in the abstract), I'd be immensely appreciative.

asked Oct 27 '10 at 19:31

Jacob%20Jensen's gravatar image

Jacob Jensen
1914315663


2 Answers:

Some links to background and relevant papers appear on this webpage from Dan Spielman.

answered Oct 27 '10 at 22:01

Vicente%20Malave's gravatar image

Vicente Malave
355137

Also his talk in the FOCS website http://techtalks.tv/focs/2010/ clarifies almost all the basic concepts.

(Nov 08 '10 at 09:18) Alexandre Passos ♦

I'm not familiar with these techniques either, but it seems there are a few steps to understand the significance of this.

  1. An important class of linear systems is the symmetric diagonal dominant systems, where the A matrix (the system is Ax = b) is symmetric and has A_ii >= sum(j != i, A_ij) (that is, the diagonal is larger than the sum of the off-diagonal elements).
  2. A weighted undirected graph can be caracterized by its laplacian matrix L, which is, given an arbitrary indexing of its vertices, L_(i,j) = -w_ij (where w_ij is the weight of the edge between vertices i and j) and L_(i,i) = sum(i != j, w_ij).
  3. Since a graph (and an enumeration) uniquely specifies its laplacian (and vice versa, as you can easily check), you can actually talk of any laplacian-like matrix as a graph.
  4. You can talk of something called a graph preconditioner, which is a graph G' that approximates a given graph G but is easier to solve (i.e., invert the laplacian).
  5. There is this concept called stretch of a tree approximation to a given graph G. The stretch of an edge e connecting vertices i and j is the ratio between the sum of the inverted weights of the edges the (only) path in the tree connecting i and j and the inverted weight of the ij edge in the graph. sum(w'_ab for ab in the path)/w'_ij
  6. You can then talk about an alpha-sparsifier, which is a graph G' that has a nearly linear number of edges and alpha-approximates a given graph G in terms of something related to stretch.

This paper, then, develops what they call an incremental sparsifier, which is a graph that approximates another given graph as you add edges in a specific way. With this guaranteed approximation they can build a solver that runs in the alloted time.

I've just summarized their main claims here, and I have in no way verified or undersood their results.

answered Oct 27 '10 at 20:42

Alexandre%20Passos's gravatar image

Alexandre Passos ♦
2554154278421

Your answer
toggle preview

powered by OSQA

User submitted content is under Creative Commons: Attribution - Share Alike; Other things copyright (C) 2010, MetaOptimize LLC.