Fast Matrix Rank Algorithms and Applications
| Autor: | Lap Chi Lau, Ho Yee Cheung, Tsz Chiu Kwok |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
FOS: Computer and information sciences
Rank (linear algebra) Field (mathematics) Low-rank approximation G.1.3 computer.software_genre Combinatorics Matrix (mathematics) symbols.namesake Gaussian elimination Artificial Intelligence Computer Science - Data Structures and Algorithms FOS: Mathematics Data Structures and Algorithms (cs.DS) Mathematics - Numerical Analysis Mathematics Discrete mathematics Numerical linear algebra F.2.1 Computer Science - Numerical Analysis Numerical Analysis (math.NA) Augmented matrix Randomized algorithm Hardware and Architecture Control and Systems Engineering symbols Linear independence Algorithm computer Software Information Systems |
| Zdroj: | STOC |
| DOI: | 10.48550/arxiv.1203.6705 |
| Popis: | We consider the problem of computing the rank of an m × 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 deterministic 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 exact linear algebra, combinatorial optimization and dynamic data structure. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|