Back to search

Georgia Institute of Technology

A Fast Parallel Density-aware Algorithm for Graph Spectral Sparsification

Abstract

dc:description.abstract

Graph 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

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Zhao, Tiancheng. A Fast Parallel Density-aware Algorithm for Graph Spectral Sparsification. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/82133