Cholesky-like Preconditioner for Hodge Laplacians via Heavy Collapsible Subcomplex

Anton Savostianov, Francesco Tudisco, Nicola Guglielmi

This paper introduces a novel, topologically-aware preconditioning strategy for solving linear systems involving Hodge Laplacians. By identifying a "heavy" collapsible subcomplex within a larger simplicial complex, the authors construct a sparse, Cholesky-like preconditioner that significantly accelerates iterative solvers and outperforms standard incomplete Cholesky methods for sparse higher-order networks.

Introduction

In modern network science, the focus is shifting from simple graphs (nodes and edges) to simplicial complexes. These structures model multi-agent interactions, such as triangles or higher-order tetrahedra, providing a richer framework for studying complex systems. The Hodge Laplacian ($L_k$) serves as the mathematical engine for analyzing the topology and dynamics—such as diffusion or synchronization—within these higher-order networks.

The Computational Bottleneck

Solving linear systems of the form $L_k x = f$ is a critical but computationally demanding task. For standard graphs ($k=0$), efficient solvers exist. However, for higher-order Laplacians ($k \ge 1$), standard direct methods like Cholesky factorization suffer from massive "fill-in." This phenomenon occurs when a sparse matrix becomes dense during calculation, leading to an explosion in memory and time requirements.

Simplicial complex and its boundary operator representation.

This paper addresses this challenge by developing an efficient, sparse preconditioner that exploits the underlying topological structure of the complex to accelerate iterative calculations.

Methods: The HeCS Algorithm

The authors propose HeCS (Heavy Collapsible Subcomplex preconditioning), a strategy built on the following pillars:

  1. Problem Reduction: The authors prove that solving the full Hodge Laplacian can be reduced to solving a sequence of "up-Laplacian" ($L_k^\uparrow$) problems, with a primary focus on the $k=1$ (edge-flow) case.
  2. Topological Sparsity and Collapsibility: The "fill-in" problem is fundamentally linked to cycles within the complex. The authors leverage collapsibility—a topological property where a complex can be reduced to a single point by iteratively removing "free" faces. Collapsible complexes have the unique property that their Cholesky factors remain perfectly sparse.
  3. HeCS Implementation: Since most real-world complexes are not fully collapsible, the authors developed a greedy algorithm to identify a heavy collapsible subcomplex. This algorithm iteratively adds the "heaviest" triangles (those with the highest weights) to a subcomplex, ensuring it remains "weakly collapsible."
  4. Preconditioning: The exact Cholesky factor of this heavy subcomplex is used as a preconditioner for the original system within a Conjugate Gradient Least Squares (CGLS) solver.

Key Insights

  • The Cyclic Term Bottleneck: The failure of standard Cholesky for Hodge Laplacians is caused by the elimination of edges shared by multiple triangles, which creates "cyclic terms" that densifies the matrix.
  • Collapsibility as a Sparsity Guarantee: Restricting the preconditioner to a collapsible subcomplex prevents these cyclic terms from appearing, guaranteeing a sparse factor.
  • Weight-Based Selection: By prioritizing "heavy" triangles, the preconditioner captures the most significant numerical components of the Laplacian, resulting in better conditioning than purely structural selection methods.

Evaluation and Results

The method was evaluated using synthetic enriched triangulations with various sparsity patterns and weight distributions (e.g., Cauchy, bi-modal Gaussian, and topological rules). Key findings include:

  • Condition Number Reduction: HeCS significantly reduces the condition number ($\kappa_+$) of the system, particularly in sparse regimes.
  • Convergence Speed: Preconditioned CGLS converged much faster than unpreconditioned versions in numerical tests.
  • Performance vs. Incomplete Cholesky: HeCS consistently outperformed standard ichol methods, which often struggle with the singular nature of Hodge Laplacians or fail to maintain sparsity as the number of vertices increases.
  • Efficiency: The greedy algorithm for finding the subcomplex has a complexity of $O(m_1 m_2)$, making it suitable for the sparse complexes typical in network science.

Limitations and Future Work

While promising, the current implementation focuses on $k=1$ (triangles and edges). Future work includes extending the algorithm to $k > 2$ (tetrahedra and beyond). Additionally, the performance gains of HeCS diminish as simplicial complexes become very dense, as fewer triangles can be included in a collapsible subcomplex. Finally, validating the method on real-world datasets, such as co-authorship or protein interaction networks, remains a key next step.

Summary updated

BibTeX
@article{savostianov2024cholesky,
  author = {Anton Savostianov and Francesco Tudisco and Nicola Guglielmi},
  title = {{Cholesky-like Preconditioner for Hodge Laplacians via Heavy Collapsible Subcomplex}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2024},
  doi = {10.1137/23m1626396},
}
Figure