Fast Matrix Rank Algorithms and Applications

Details Fast Matrix Rank Algorithms and Applications Fast Matrix Rank Algorithms and Applications

2012-03-30

arxiv.org/abs/1203.6705v2

Computer Science

Data Structures and Algorithms

Scientific paper

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 \~O(|A| + r^\omega) field operations, where |A| denotes the number of nonzero entries in A and \omega < 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^{\omega-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 \~O(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.

Affiliated with

Also associated with

No associations

Rating

Fast Matrix Rank Algorithms and Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Matrix Rank Algorithms and Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Matrix Rank Algorithms and Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-63840