Sparse Linear Algebra Accelerates Genotype Representation Graph Computation at Biobank Scale
Biobank-scale genomic analyses are increasingly constrained by computational costs, as hundreds of thousands to millions of samples and variants must be analyzed together. The genotype representation graph (GRG) compactly encodes population genetic variation to accelerate computation, but the current approach does not exploit modern accelerator architectures. This work introduces Mikado, a new methodology for expressing GRG-based computation using sparse linear algebra primitives. Under a reverse topological ordering of the graph nodes, the GRG adjacency matrix is strictly block-lower-triangular, and the genotype matrix-vector product becomes a sparse triangular solve that can be further decomposed into a pipelined sequence of blocked sparse matrix-vector multiplies. By decoupling computation from graph representation, our approach exposes fine-grained parallelism and enables hardware-optimized sparse primitives on GPUs. Mikado achieves an order-of-magnitude speedup and cost savings for PCA and BOLT-LMM compared with the original GRG traversal approach, including on All of Us cohorts. It provides a scalable, hardware-portable, researcher-friendly tool for population genetics at biobank scale.