Tianyu Liang

EECS Department, University of California, Berkeley

Technical Report No. UCB/

May 1, 2026

This report is delayed

Modern numerical linear algebra offers algorithms with attractive theoretical complexity, but translating those algorithms into scalable parallel software requires substantial additional work. Irregular dependencies, memory movement, synchronization, communication, and hardware-specific constraints can prevent theoretically efficient methods from achieving high performance in practice. This dissertation studies how graph-based dependency analysis can guide the design of scalable parallel matrix factorizations, from dynamic scheduling on multicore CPUs and GPUs to communication avoidance in distributed-memory systems.

The first case study develops ParAC, a practical parallel framework for randomized approximate Cholesky preconditioning of graph Laplacian systems. Randomized clique sampling causes the active sparse graph—and therefore the available parallel work—to evolve during factorization. ParAC tracks these changes at runtime and uses scheduling and memory-management strategies designed for multicore CPUs and GPUs. Experiments show substantial time-to-solution improvements over deterministic incomplete Cholesky baselines in cases where those baselines converge, while performance relative to algebraic multigrid is problem dependent.

The second case study develops a communication-avoiding distributed-memory hierarchical factorization for dense matrices arising from integral-equation and kernel models. The implementation is evaluated on three-dimensional Laplace and Helmholtz problems and two-dimensional Matérn covariance matrices. For the regular grids studied here, geometry makes it possible to organize work and data exchange in advance. Using a variable-depth halo and repeating selected boundary computations, the communication-avoiding algorithm trades additional arithmetic and storage for fewer communication phases. The hybrid distributed/shared-memory implementation is evaluated across MPI ranks and node-level thread counts, and the experiments quantify the tradeoff between communication reduction and redundant local work.

Together, the two algorithms address the same broad challenge: respecting elimination dependencies while maintaining parallel scalability. ParAC discovers parallelism as the sparse graph changes, whereas the hierarchical factorization uses geometry to organize computation and communication ahead of time. More broadly, the dissertation shows how co-designing numerical algorithms and their parallel implementations can bridge the gap between theoretical efficiency and scalable performance in practice.

Advisors: James Demmel and Aydin Buluç

---

BibTeX citation:

@phdthesis{Liang:32302,
    Author= {Liang, Tianyu},
    Title= {Graph-Based Dependency Analysis for Scalable Matrix Factorizations: Parallelism and Communication Avoidance},
    School= {EECS Department, University of California, Berkeley},
    Year= {2026},
    Month= {Aug},
    Number= {UCB/},
    Abstract= {Modern numerical linear algebra offers algorithms with attractive theoretical complexity, but translating those algorithms into scalable parallel software requires substantial additional work. Irregular dependencies, memory movement, synchronization, communication, and hardware-specific constraints can prevent theoretically efficient methods from achieving high performance in practice. This dissertation studies how graph-based dependency analysis can guide the design of scalable parallel matrix factorizations, from dynamic scheduling on multicore CPUs and GPUs to communication avoidance in distributed-memory systems.

The first case study develops ParAC, a practical parallel framework for randomized approximate Cholesky preconditioning of graph Laplacian systems. Randomized clique sampling causes the active sparse graph—and therefore the available parallel work—to evolve during factorization. ParAC tracks these changes at runtime and uses scheduling and memory-management strategies designed for multicore CPUs and GPUs. Experiments show substantial time-to-solution improvements over deterministic incomplete Cholesky baselines in cases where those baselines converge, while performance relative to algebraic multigrid is problem dependent.

The second case study develops a communication-avoiding distributed-memory hierarchical factorization for dense matrices arising from integral-equation and kernel models. The implementation is evaluated on three-dimensional Laplace and Helmholtz problems and two-dimensional Matérn covariance matrices. For the regular grids studied here, geometry makes it possible to organize work and data exchange in advance. Using a variable-depth halo and repeating selected boundary computations, the communication-avoiding algorithm trades additional arithmetic and storage for fewer communication phases. The hybrid distributed/shared-memory implementation is evaluated across MPI ranks and node-level thread counts, and the experiments quantify the tradeoff between communication reduction and redundant local work.

Together, the two algorithms address the same broad challenge: respecting elimination dependencies while maintaining parallel scalability. ParAC discovers parallelism as the sparse graph changes, whereas the hierarchical factorization uses geometry to organize computation and communication ahead of time. More broadly, the dissertation shows how co-designing numerical algorithms and their parallel implementations can bridge the gap between theoretical efficiency and scalable performance in practice.},
}

EndNote citation:

%0 Thesis
%A Liang, Tianyu 
%T Graph-Based Dependency Analysis for Scalable Matrix Factorizations: Parallelism and Communication Avoidance
%I EECS Department, University of California, Berkeley
%D 2026
%8 May 1
%@ UCB/
%F Liang:32302