2012/03/30 by Ho Yee Cheung, Cheung, Ho Yee, Tsz Chiu Kwok +3
Computer Science · #Advanced Graph Theory Research #Coding theory and cryptography #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #G.1.3 #Numerical Analysis (math.NA)
paper · pdf · doi:10.48550/arxiv.1203.6705
openalex publication_date 2012/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of computing the rank of an m x n matrix A over a field. We present a randomized algorithm to find a set of r = rank(A) linearly independent columns in Õ(|A| + rω) field operations, where |A| denotes the number of nonzero entries in A and ω< 2.38 is the matrix multiplication exponent. Previously the best known algorithm to find a set of r linearly independent columns is by Gaussian elimination, with running time O(mnrω-2). Our algorithm is faster when r < max(m,n), for instance when the matrix is rectangular. We also consider the problem of computing the rank of a matrix dynamically, supporting the operations of rank one updates and additions and deletions of rows and columns. We present an algorithm that updates the rank in Õ(mn) field operations. We show that these algorithms can be used to obtain faster algorithms for various problems in numerical linear algebra, combinatorial optimization and dynamic data structure.