Fast sparse matrix multiplication

Abstract

Let A and B two n×n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using O(m^0.7n^1.2+n^2+o(1)) algebraic operations (i.e., multiplications, additions and subtractions) over R. The naïve matrix multiplication algorithm, on the other hand, may need to perform Ω(mn) operations to accomplish the same task. For m≤n^1.14, the new algorithm performs an almost optimal number of only n^2+o(1) operations. For m≤n^1.68, the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O(n^2.38) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value.

References

1. Alon, N., Yuster, R., and Zwick, U. 1995. Color-coding. J. ACM 42, 844--856.
2. Alon, N., Yuster, R., and Zwick, U. 1997. Finding and counting given length cycles. Algorithmica 17, 209--223.
3. Bürgisser, P., Clausen, M., and Shokrollahi, M. 1997. Algebraic complexity theory. Springer-Verlag, New York.
4. Chan, T. 2002. Dynamic subgraph connectivity with geometric applications. In Proceedings of 34th Symposium on the Theory of Computing. ACM, New York, 7--13.
5. Cheriyan, J. 1997. Randomized Õ(M(|V|)) algorithms for problems in matching theory. SIAM J. Comput. 26, 1635--1655.
6. Chin, F. 1978. An O(n) algorithm for determining a near-optimal computation order of matrix chain products. Commun. ACM 21, 7, 544--549.
7. Cohen, E. 1997. Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sciences 55, 3, 441--453.
8. Cohn, H., and Umans, C. 2003. A group-theoretic approach to fast matrix multiplication. In Proceedings of 44th Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 438--449.
9. Coppersmith, D. 1997. Rectangular matrix multiplication revisited. J. Complex. 13, 42--49.
10. Coppersmith, D., and Winograd, S. 1990. Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251--280.
11. Cormen, T., Leiserson, C., Rivest, R., and Stein, C. 2001. Introduction to Algorithms, Second ed. The MIT Press, Cambridge, Mass.
12. Demetrescu, C., and Italiano, G. 2000. Fully dynamic transitive closure: Breaking through the O(n2) barrier. In Proceedings of 41st Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 381--389.
13. Eisenbrand, F., and Grandoni, F. 2003. Detecting directed 4-cycles still faster. Inf. Proc. Lett. 87, 1, 13--15.
14. Gustavson, F. 1978. Two fast algorithms for sparse matrices: Multiplication and permuted transposition. ACM Trans. Math. Softw. 4, 3, 250--269.
15. Hu, T., and Shing, M. 1982. Computation of matrix chain products I. SIAM J. Comput. 11, 2, 362--373.
16. Hu, T., and Shing, M. 1984. Computation of matrix chain products II. SIAM J. Comput. 13, 2, 228--251.
17. Huang, X., and Pan, V. 1998. Fast rectangular matrix multiplications and applications. J. Complex. 14, 257--299.
18. Kratsch, D., and Spinrad, J. 2003. Between O(nm) and O(nα). In Proceedings of 14th Symposium on Discrete Algorithms. ACM, New York, 709--716.
19. Mucha, M., and Sankowski, P. 2004a. Maximum matchings in planar graphs via gaussian elimination. In Proceedings of 12th ESA, 532--543.
20. Mucha, M., and Sankowski, P. 2004b. Maximum matchings via gaussian elimination. In Proceedings of 45th Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 248--255.
21. Mulmuley, K., Vazirani, U. V., and Vazirani, V. V. 1987. Matching is as easy as matrix inversion. Combinatorica 7, 105--113.
22. Nešetřil, J., and Poljak, S. 1985. On the complexity of the subgraph problem. Comment. Math. Univ. Carol. 26, 2, 415--419.
23. Pan, V. 1985. How to multiply matrices faster. In Lecture Notes in Computer Science, vol. 179. Springer-Verlag, New York.
24. Rabin, M., and Vazirani, V. 1989. Maximum matchings in general graphs through randomization. J. Alg. 10, 557--567.
25. Raz, R. 2003. On the complexity of matrix product. SIAM J. Comput. 32, 1356--1369.
26. Roditty, L., and Zwick, U. 2002. Improved dynamic reachability algorithms for directed graphs. In Proceedings of 43rd Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 679--688.
27. Seidel, R. 1995. On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51, 400--403.
28. Shoshan, A., and Zwick, U. 1999. All pairs shortest paths in undirected graphs with integer weights. In Proceedings of 40th Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 605--614.
29. Shpilka, A. 2003. Lower bounds for matrix product. SIAM J. Comput. 32, 1185--1200.
30. Strassen, V. 1969. Gaussian elimination is not optimal. Numer. Math. 13, 354--356.
31. Yuster, R., and Zwick, U. 2004. Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. In Proceedings of 15th Symposium on Discrete Algorithms. ACM, New York, 247--253.
32. Zwick, U. 2002. All-pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49, 289--317.

Index Terms

• Computing methodologies

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

      • Algebraic algorithms

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Computations on matrices

• Theory of computation

  • Randomness, geometry and discrete structures