### Fast matrix rank algorithms and applicationsFast matrix rank algorithms and applications

Access Restriction
Subscribed

 Author Cheung, Ho Yee ♦ Kwok, Tsz Chiu ♦ Lau, Lap Chi Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Combinatorial optimization ♦ Exact linear algebra ♦ Matrix rank ♦ Randomized algorithm Abstract We consider the problem of computing the rank of an $\textit{m}$ × $\textit{n}$ matrix $\textit{A}$ over a field. We present a randomized algorithm to find a set of $\textit{r}$ = $rank(\textit{A})$ linearly independent columns in $\textit{Õ}(|\textit{A}|$ + $r^{ω})$ field operations, where $|\textit{A}|$ denotes the number of nonzero entries in $\textit{A}$ and ω < 2.38 is the matrix multiplication exponent. Previously the best known algorithm to find a set of $\textit{r}$ linearly independent columns is by Gaussian elimination, with deterministic running time $O(mnr^{ω-2}).$ Our algorithm is faster when $\textit{r}$ < $max{\textit{m},\textit{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 $\textit{Õ}(\textit{mn})$ field operations. We show that these algorithms can be used to obtain faster algorithms for various problems in exact linear algebra, combinatorial optimization and dynamic data structure. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2013-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 60 Issue Number 5 Page Count 25 Starting Page 1 Ending Page 25

#### Open content in new tab

Source: ACM Digital Library