Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
复制标题
DOI：
10.1145/1989493.1989496
复制
发表时间：
2011-06
期刊：
影响因子：
--
通讯作者：
G. Blelloch;Anupam Gupta;I. Koutis;G. Miller;Richard Peng;Kanat Tangwongsan
中科院分区：
文献类型：
--
作者：
G. Blelloch;Anupam Gupta;I. Koutis;G. Miller;Richard Peng;Kanat Tangwongsan
提出了求解对称对角占优（SDD）线性方程组的一种近似线性功并行算法。对于一个具有m个非零元素的SDD n × n矩阵A和一个向量B，我们的算法计算一个向量x，使得Ax-A +B ≤ ε · A+B的工作时间为O（mlogO（1）nlog 1/ε），深度为O（m1/3+θ log 1/ε），对于任何固定的θ > 0.该算法依赖于一个并行算法生成低拉伸生成树或生成子图。为此，我们首先开发了一个并行分解算法，在多对数深度和O（|E|）工作，将图划分为具有多对数直径的组件，使得只有一小部分原始边位于组件之间。这可以用来生成低拉伸生成树，其平均拉伸时间为O（nα），工作时间为O（n1+α），深度为O（nα）。或者，它可以用来生成具有多对数平均拉伸的生成子图，|E|）工作和多对数深度。我们应用这个子图构造来导出我们的求解器。通过在已知应用中使用线性系统求解器，我们的结果意味着针对多个问题的改进并行随机算法，包括单源最短路径、最大流、最小成本流和近似最大流。
This paper presents the design and analysis of a near linear-work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input an SDD n-by-n matrix A with m non-zero entries and a vector b, our algorithm computes a vector x such that Ax - A+b ≤ ε • A+b in O(m logO(1) n log 1/ε) work and O(m1/3+θ log 1/ε) depth for any fixed θ > 0. The algorithm relies on a parallel algorithm for generating low-stretch spanning trees or spanning subgraphs. To this end, we first develop a parallel decomposition algorithm that in polylogarithmic depth and O(|E|) work, partitions a graph into components with polylogarithmic diameter such that only a small fraction of the original edges are between the components. This can be used to generate low-stretch spanning trees with average stretch O(nα) in O(n1+α) work and O(nα) depth. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in O(|E|) work and polylogarithmic depth. We apply this subgraph construction to derive our solver. By using the linear system solver in known applications, our results imply improved parallel randomized algorithms for several problems, including single-source shortest paths, maximum flow, min-cost flow, and approximate max-flow.