research-article

Fast matrix rank algorithms and applications

Authors:

Lap Chi LauAuthors Info & Claims

Journal of the ACM (JACM), Volume 60, Issue 5

Article No.: 31, Pages 1 - 25

https://doi.org/10.1145/2528404

Published: 28 October 2013 Publication History

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.

References

[1]

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.

Digital Library

[2]

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.

Digital Library

[3]

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.

Digital Library

[4]

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.

Digital Library

[5]

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.

Digital Library

[6]

Buergisser, P., Clausen, M., and Shokrollahi, A. 1997. Algebraic Complexity Theory. Springer Verlag.

Digital Library

[7]

Bunch, J. R. and Hopcroft, J. E. 1974. Triangular Factorization and Inversion by Fast Matrix Multiplication. Math. Comp. 28, 125, 231--236.

[8]

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.

Digital Library

[9]

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.

[10]

Cheriyan, J. 1997. Randomized Õ(M(|V|)) algorithms for problems in matching theory. SIAM J. Comput. 26, 6, 1635--1655.

Digital Library

[11]

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.

Digital Library

[12]

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.

Digital Library

[13]

Coppersmith, D. and Winograd, S. 1990. Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 3, 251--280.

Digital Library

[14]

Cunningham, W. H. 1986. Improved bounds for matroid partition and intersection algorithms. SIAM J. Comput. 15, 4, 948--957.

Digital Library

[15]

Frandsen, G. S. and Frandsen, P. F. 2009. Dynamic matrix rank. Theoreti. Comput. Sci. 410, 41, 4085--4093.

Digital Library

[16]

Gabow, H. N. and Stallmann, M. 1986. An augmenting path algorithm for linear matroid parity. Combinatorica 6, 2, 123--150.

Digital Library

[17]

Gabow, H. N. and Xu, Y. 1996. Efficient theoretic and practical algorithms for linear matroid intersection problems. J. Comput. System Sci. 53, 129--147.

Digital Library

[18]

Goldberg, A. V. and Karzanov, A. V. 2004. Maximum skew-symmetric flows and matchings. Math. prog. 100, 3, 537--568.

Digital Library

[19]

Harvey, N. J. A. 2009. Algebraic algorithms for matching and matroid problems. SIAM J. Comput. 39, 2, 679--702.

Digital Library

[20]

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.

Digital Library

[21]

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.

Digital Library

[22]

Hoory, S., Linial, N., and Wigderson, A. 2006. Expander graphs and their applications. Bull. (New series) Amer. Math. Soc. 43, 4, 439--561.

[23]

Huang, X. and Pan, V. Y. 1998. Fast rectangular matrix multiplication and applications. J. Complex. 14, 2, 257--299.

Digital Library

[24]

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.

[25]

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.

Digital Library

[26]

Lovász, L. 1979. On determinants, matchings and random algorithms. In Fundamentals of Computation Theory, vol. 79, 565--574.

[27]

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.

Digital Library

[28]

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.

Digital Library

[29]

Pan, V. 1972. On schemes for the evaluation of products and inverses of matrices. Uspekhi Matematicheskikh Nauk 27, 5, 249--250.

[30]

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.

Digital Library

[31]

Sankowski, P. 2007. Faster dynamic matchings and vertex connectivity. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 118--126.

Digital Library

[32]

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.

Digital Library

[33]

Saunders, B. D., Storjohann, A., and Villard, G. 2004. Matrix rank certification. Electro. J. Lin. Algebra 11, 16--23.

[34]

Schrijver, A. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer Verlag.

[35]

Schwartz, J. T. 1980. Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27, 4 (Oct.), 701--717.

Digital Library

[36]

Storjohann, A. 2009. Integer matrix rank certification. In Proceedings of the International Symposium on Symbolic and Algebraic Computation. 333--340.

Digital Library

[37]

Trefethen, L. N. and Bau, D. 1997. Numerical Linear Algebra. SIAM.

[38]

Tutte, W. T. 1947. The factorization of linear graphs. J. London Math. Soc. 22, 2, 107--111.

[39]

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.

Digital Library

[40]

von zur Gathen, J. and Gerhard, J. 2003. Modern Computer Algebra.

Digital Library

[41]

Wiedemann, D. H. 1986. Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory 32, 1, 54--62.

Digital Library

[42]

Williams, V. V. 2012. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing. 887--898.

Digital Library

[43]

Woodbury, M. A. 1950. Inverting Modified Matrices. Princeton University. 4 pages.

[44]

Yuster, R. 2010. Generating a d-dimensional linear subspace efficiently. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms. 467--470.

Digital Library

Cited By

Seliverstov AZverkov O(2024)Lower bounds for the rank of a matrix with zeros and ones outside the leading diagonalПрограммирование10.31857/S0132347424020133(100-107)Online publication date: 15-Apr-2024
https://doi.org/10.31857/S0132347424020133
Seliverstov AZverkov O(2024)Lower Bounds for the Rank of a Matrix with Zeros and Ones outside the Leading DiagonalProgramming and Computing Software10.1134/S036176882402014250:2(202-207)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1134/S0361768824020142
Lin JHuang YLee MChen P(2024)Coded Distributed Multiplication for Matrices of Different Sparsity LevelsIEEE Transactions on Communications10.1109/TCOMM.2023.332619372:2(633-647)Online publication date: Feb-2024
https://doi.org/10.1109/TCOMM.2023.3326193
Show More Cited By

Index Terms

Fast matrix rank algorithms and applications
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations in finite fields

Recommendations

Fast matrix rank algorithms and applications
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

We 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| + r^w) 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 computation

Krylov-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 computation

We 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 60, Issue 5

October 2013

245 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2528384

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 October 2013

Accepted: 01 March 2013

Revised: 01 February 2013

Received: 01 June 2012

Published in JACM Volume 60, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Research Grants Council, University Grants Committee, Hong Kong

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
950
Total Downloads

Downloads (Last 12 months)76
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Seliverstov AZverkov O(2024)Lower bounds for the rank of a matrix with zeros and ones outside the leading diagonalПрограммирование10.31857/S0132347424020133(100-107)Online publication date: 15-Apr-2024
https://doi.org/10.31857/S0132347424020133
Seliverstov AZverkov O(2024)Lower Bounds for the Rank of a Matrix with Zeros and Ones outside the Leading DiagonalProgramming and Computing Software10.1134/S036176882402014250:2(202-207)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1134/S0361768824020142
Lin JHuang YLee MChen P(2024)Coded Distributed Multiplication for Matrices of Different Sparsity LevelsIEEE Transactions on Communications10.1109/TCOMM.2023.332619372:2(633-647)Online publication date: Feb-2024
https://doi.org/10.1109/TCOMM.2023.3326193
Meier MNakatsukasa Y(2024)Fast randomized numerical rank estimation for numerically low-rank matricesLinear Algebra and its Applications10.1016/j.laa.2024.01.001686(1-32)Online publication date: Apr-2024
https://doi.org/10.1016/j.laa.2024.01.001
Grasegger GLegerský J(2024)Flexibility and rigidity of frameworks consisting of triangles and parallelogramsComputational Geometry: Theory and Applications10.1016/j.comgeo.2023.102055120:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.comgeo.2023.102055
Dhar ANatarajan VRathod A(2024)Fast Algorithms for Minimum Homology BasisDiscrete & Computational Geometry10.1007/s00454-024-00680-8Online publication date: 24-Jul-2024
https://doi.org/10.1007/s00454-024-00680-8
Akmal SJin C(2024)An Efficient Algorithm for All-Pairs Bounded Edge ConnectivityAlgorithmica10.1007/s00453-023-01203-286:5(1623-1656)Online publication date: 22-Jan-2024
https://doi.org/10.1007/s00453-023-01203-2
Feng YWoodruff DKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Improved algorithms for white-box adversarial streamsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618807(9962-9975)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618807
Zverkov OSeliverstov A(2023)Effective Lower Bounds on the Matrix Rank and Their ApplicationsПрограммирование10.31857/S0132347423020176(79-86)Online publication date: 1-Sep-2023
https://doi.org/10.31857/S0132347423020176
Seliverstov A(2023)Generalization of the Subset Sum Problem and Cubic FormsЖурнал вычислительной математики и математической физики10.31857/S004446692301011863:1(51-60)Online publication date: 1-Jan-2023
https://doi.org/10.31857/S0044466923010118
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents