TIDE-MC: Two-Sided Interpolative Decomposition for Billion-Scale GPU Matrix Completion

Abstract

Matrix completion supports large-scale recommendation and scientific computing, yet existing GPU solvers commonly assume that the observed matrix or its dense factors fit in device memory. On real workloads, this assumption leads to out-of-memory failures or severe PCIe overhead under naive paging. We present TIDE-MC, a bounded-memory GPU framework built on Two-Sided Interpolative Decomposition (TSID). TSID uses a sampled template submatrix as an anchor for reconstructing the full low-rank matrix, allowing computation and storage to scale with the template and active data chunks rather than the complete matrix. TIDE-MC realizes this formulation through two execution stages. First, a conflict-free synchronization engine recovers the template using parallel factorization and hierarchical gradient aggregation. Second, a chunked reconstruction pipeline extends the recovered template to the remaining matrix while overlapping PCIe transfers with GPU computation. An asymmetric gradient-clipping scheme stabilizes mixed-precision Tensor Core execution. Across 15 benchmarks, TIDE-MC completes workloads that cause existing GPU solvers to run out of memory. Compared with the evaluated state-of-the-art baselines, it achieves up to 11,647x speedup, reduces peak memory usage by up to 8.5x, and lowers reconstruction error by up to 99.7%. These results show that template-anchored decomposition and stage-specific GPU execution can scale matrix completion beyond device-memory capacity.