Implementing Low-Stretch Spanning Trees for Efficient Graph Approximation and Linear System Solvers

Abstract

We investigate the construction and performance of low- stretch spanning trees as an effective approach for graph optimization and preconditioning techniques in linear system solvers. Inspired by the methods introduced by Spielman et al., our implementation focuses on minimizing stretch to improve computational efficiency in solving symmetric diagonally dominant (SDD) systems. Developed in Julia, the algorithm employs contraction and recursive decomposition strategies to generate spanning trees optimized for reduced stretch. Performance evaluations on diverse graph structures highlight the algorithm’s scalability and suitability for data-intensive applications, including network design and resource allocation problems. This study demonstrates the practical impact of low-stretch spanning trees in advancing graph-based computation and solver technologies.