Student Information: 

    Full Name: Tiancheng Zhao

    GT ID: 904056610

    Degree: Master of Science in Computer Science

    School: School of Computer Science, College of Computing

    Defense Schedule & Location:

        Date: Tuesday, July 14, 2026

        Time: 10.30 am - 12.30 pm

        Location: Coda C1315 Grant Park; https://gatech.zoom.us/j/98984363801?pwd=2Nho0mHrZYgO4Of

   Thesis Details:

        Title: A Fast Parallel Density-Aware Algorithm for Graph Spectral Sparsification

    Committee Members:

•    Prof. Helen Xu (Advisor) - School of Computational Science and Engineering, Georgia Institute of Technology

•    Prof. Richard Vuduc - School of Computational Science and Engineering, Georgia Institute of Technology

•    Prof. Jan van den Brand – School of Computer Science, Georgia Institute of Technology

•    Prof. Elizabeth Cherry – School of Computer Science, Georgia Institute of Technology

•    Prof. Chaojian Li - Department of Computer Science and Engineering, Hong Kong University of Science and Technology

    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.