Dynamic Rank, Basis, and Matching
2026-05-11 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors studied ways to quickly update important properties of matrices, like rank and basis, when the matrix changes over time. Previous methods were slower because their speed depended on the entire matrix size. The authors created new algorithms whose speed depends mainly on the matrix's rank, making updates faster especially for low-rank matrices. These improvements also apply to finding maximum matchings in changing graphs, which is useful in computer science problems.
dynamic algorithmsmatrix rankbasisfull-rank submatrixmaximum matchingentry-updatecolumn-updategraph algorithmssubquadratic time
Authors
Jan van den Brand, Vishal Kumar, Daniel J. Zhang
Abstract
We study dynamic algorithms for maintaining fundamental algebraic properties of matrices, specifically, rank, basis, and full-rank submatrices, with applications to maximum matching on dynamic graphs. Prior dynamic algorithms for rank achieve subquadratic update times but scale with the matrix dimension $n$, and could not always maintain the corresponding objects such as a basis or maximum full-rank submatrix. We present the first dynamic rank algorithms whose update time scales with the matrix rank $r$, achieving $\tilde O(r^{1.405})$ time per entry-update and $\tilde O(r^{1.528}+ z)$ per column-update, where $z$ is the number of changed entries. This extends to $\tilde O(|M|^{1.405})$ edge-update time to maintain the size $|M|$ of a maximum matching. We also give dynamic algorithms for maintaining a column-basis subject to column-updates and a maximum full-rank submatrix subject to entry-updates.