Ho Yee Cheung
Skip Abstract Section
Abstract
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.
- Ahlswede, R. F., Cai, N., Li, S.-Y. R., and Yeung, R. W. 2000. Network information flow. IEEE Trans. Info. Theory 46, 4, 1204--1216. Google Scholar
Digital Library
- Ailon, N. and Chazelle, B. 2006. Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing. 557--563. Google ScholarDigital Library
- Ailon, N. and Liberty, E. 2011. An almost optimal unrestricted fast Johnson-Lindenstrauss transform. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. 185--191. Google ScholarDigital Library
- Alon, N. and Yuster, R. 2007. Fast algorithms for maximum subset matching and all-pairs shortest paths in graphs with a (not so) small vertex cover. In Proceedings of the 15th Annual European Symposium on Algorithms. 175--186. Google ScholarDigital Library
- Bhalgat, A., Hariharan, R., Kavitha, T., and Panigrahi, D. 2007. An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 605--614. Google ScholarDigital Library
- Buergisser, P., Clausen, M., and Shokrollahi, A. 1997. Algebraic Complexity Theory. Springer Verlag. Google ScholarDigital Library
- Bunch, J. R. and Hopcroft, J. E. 1974. Triangular Factorization and Inversion by Fast Matrix Multiplication. Math. Comp. 28, 125, 231--236.Google Scholar
- Charles, D., Chickering, M., Devanur, N. R., Jain, K., and Sanghi, M. 2010. Fast algorithms for finding matchings in lopsided bipartite graphs with applications to display ads. In Proceedings of the 11th ACM Conference on Electronic Commerce. 121--128. Google ScholarDigital Library
- Chen, L., Eberly, W., Kaltofen, E., Saunders, B. D., Turner, W. J., and Villard, G. 2002. Efficient matrix preconditioners for black box linear algebra. Linear Algebra Appl. 343--344, 119--146.Google Scholar
- Cheriyan, J. 1997. Randomized Õ(M(|V|)) algorithms for problems in matching theory. SIAM J. Comput. 26, 6, 1635--1655. Google ScholarDigital Library
- Cheung, H. Y., Lau, L. C., and Leung, K. M. 2011a. Algebraic algorithms for linear matroid parity problems. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithm. 1366--1382. Google ScholarDigital Library
- Cheung, H. Y., Lau, L. C., and Leung, K. M. 2011b. Graph connectivities, network coding, and expander graphs. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science. Google ScholarDigital Library
- Coppersmith, D. and Winograd, S. 1990. Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 3, 251--280. Google ScholarDigital Library
- Cunningham, W. H. 1986. Improved bounds for matroid partition and intersection algorithms. SIAM J. Comput. 15, 4, 948--957. Google ScholarDigital Library
- Frandsen, G. S. and Frandsen, P. F. 2009. Dynamic matrix rank. Theoreti. Comput. Sci. 410, 41, 4085--4093. Google ScholarDigital Library
- Gabow, H. N. and Stallmann, M. 1986. An augmenting path algorithm for linear matroid parity. Combinatorica 6, 2, 123--150. Google ScholarDigital Library
- Gabow, H. N. and Xu, Y. 1996. Efficient theoretic and practical algorithms for linear matroid intersection problems. J. Comput. System Sci. 53, 129--147. Google ScholarDigital Library
- Goldberg, A. V. and Karzanov, A. V. 2004. Maximum skew-symmetric flows and matchings. Math. prog. 100, 3, 537--568. Google ScholarDigital Library
- Harvey, N. J. A. 2009. Algebraic algorithms for matching and matroid problems. SIAM J. Comput. 39, 2, 679--702. Google ScholarDigital Library
- Ho, T., Médard, M., Koetter, R., Karger, D. R., Effros, M., Shi, J., and Leong, B. 2006. A random linear network coding approach to multicast. IEEE Trans. Inf. Theory 52, 10, 4413--4430. Google ScholarDigital Library
- Holm, J., de Lichtenberg, K., and Thorup, M. 2001. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48, 4, 723--760. Google ScholarDigital Library
- Hoory, S., Linial, N., and Wigderson, A. 2006. Expander graphs and their applications. Bull. (New series) Amer. Math. Soc. 43, 4, 439--561.Google ScholarCross Ref
- Huang, X. and Pan, V. Y. 1998. Fast rectangular matrix multiplication and applications. J. Complex. 14, 2, 257--299. Google ScholarDigital Library
- Ibarra, O. H., Moran, S., and Hui, R. 1982. A generalization of the fast LUP matrix decomposition algorithm and applications. J. Algor. 3, 1, 45--56.Google ScholarCross Ref
- Kaltofen, E. and Saunders, B. D. 1991. On Wiedemann's method of solving sparse linear systems. In Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. 29--38. Google ScholarDigital Library
- Lovász, L. 1979. On determinants, matchings and random algorithms. In Fundamentals of Computation Theory, vol. 79, 565--574.Google Scholar
- Micali, S. and Vazirani, V. V. 1980. An O(√|V||E|) algorithm for finding maximum matching in general graphs. In Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. 17--27. Google ScholarDigital Library
- Mucha, M. and Sankowski, P. 2004. Maximum Matchings via Gaussian elimination. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. 248--255. Google ScholarDigital Library
- Pan, V. 1972. On schemes for the evaluation of products and inverses of matrices. Uspekhi Matematicheskikh Nauk 27, 5, 249--250.Google Scholar
- Sankowski, P. 2004. Dynamic Transitive Closure via Dynamic Matrix Inverse. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. 509--517. Google ScholarDigital Library
- Sankowski, P. 2007. Faster dynamic matchings and vertex connectivity. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 118--126. Google ScholarDigital Library
- Sarlós, T. 2006. Improved approximation algorithms for large matrices via random projections. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science. 143--152. Google ScholarDigital Library
- Saunders, B. D., Storjohann, A., and Villard, G. 2004. Matrix rank certification. Electro. J. Lin. Algebra 11, 16--23.Google ScholarCross Ref
- Schrijver, A. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer Verlag.Google Scholar
- Schwartz, J. T. 1980. Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27, 4 (Oct.), 701--717. Google ScholarDigital Library
- Storjohann, A. 2009. Integer matrix rank certification. In Proceedings of the International Symposium on Symbolic and Algebraic Computation. 333--340. Google ScholarDigital Library
- Trefethen, L. N. and Bau, D. 1997. Numerical Linear Algebra. SIAM.Google Scholar
- Tutte, W. T. 1947. The factorization of linear graphs. J. London Math. Soc. 22, 2, 107--111.Google ScholarCross Ref
- Vazirani, V. V. 1990. A theory of alternating paths and blossoms for proving correctness of the O(√|V||E|) general graph matching algorithm. In Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference. 509--530. Google ScholarDigital Library
- von zur Gathen, J. and Gerhard, J. 2003. Modern Computer Algebra. Google ScholarDigital Library
- Wiedemann, D. H. 1986. Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory 32, 1, 54--62. Google ScholarDigital Library
- Williams, V. V. 2012. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing. 887--898. Google ScholarDigital Library
- Woodbury, M. A. 1950. Inverting Modified Matrices. Princeton University. 4 pages.Google Scholar
- Yuster, R. 2010. Generating a d-dimensional linear subspace efficiently. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms. 467--470. Google ScholarDigital Library
Index Terms
- Fast matrix rank algorithms and applications
Recommendations
Fast matrix rank algorithms and applications
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computingWe consider the problem of computing the rank of an mxn matrix A over a field. We present a randomized algorithm to find a set of r = rank(A) linearly independent columns in O(|A| + rw) field operations, where |A| denotes the number of nonzero entries ...
Reliable Krylov-based algorithms for matrix null space and rank
ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computationKrylov-based algorithms have recently been used, in combination with other methods, to solve systems of linear equations and to perform related matrix computations over finite fields. For example, large and sparse systems of linear equations ;2; are ...
Computing the rank and a small nullspace basis of a polynomial matrix
ISSAC '05: Proceedings of the 2005 international symposium on Symbolic and algebraic computationWe reduce the problem of computing the rank and a null-space basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree, d over a field K we give a rank and nullspace algorithm using about the same ...
Comments