Access Restriction

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

   Open content in new tab
Source: ACM Digital Library