Georgia Institute of Technology
A Fast Parallel Density-aware Algorithm for Graph Spectral Sparsification
Abstract
dc:description.abstractGraph Spectral Sparsification (GSS) identifies an ultra-sparse subgraph, or sparsifier, whose Laplacian matrix closely approximates the spectral properties of the original graph, enabling substantial reductions in computational complexity for computationally intensive problems in scientific computing. The state-of-the-art method for efficient GSS is feGRASS, consisting of two steps: 1) spanning tree generation and 2) off-tree edge recovery. However, feGRASS suffers from two main issues: 1) difficulties in parallelizing the recovery step for strict data dependencies, and 2) performance degradation on skewed inputs, often requiring multiple passes to recover sufficient edges. To address these challenges, we propose parallel density-aware Graph Spectral Sparsification (pdGRASS), a parallel algorithm that organizes edges into disjoint subtasks without data dependencies between them, enabling efficient parallelization and sufficient edge recovery in a single pass. We empirically evaluate feGRASS and pdGRASS based on 1) off-tree edge-recovery runtime and 2) sparsifier quality, measured by the iteration count required for convergence in a preconditioned conjugate gradient (PCG) application. The evaluation demonstrates that pdGRASS achieves average speedups ranging from 3.9× to 8.8× depending on the number of edges recovered, and mitigates worst-case runtimes of feGRASS with over 1000× speedup on skewed inputs.
Degree
thesis:*- Name thesis:degree_name
- Computer Science, MS
- Department thesis:degree_department
- Computer Science
- Grantor
- Georgia Institute of Technology
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Zhao, Tiancheng
- Advisor dc:contributor.advisor
-
- Xu, Helen
- Committee members dc:contributor.committeemember
-
- Van Den Brand, Jan
- Cherry, Elizabeth
- Vuduc, Richard
- Li, Chaojian
- ORCID person:identifier.orcid
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/82133