{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:44:03Z","timestamp":1783035843891,"version":"3.54.6"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T00:00:00Z","timestamp":1120176000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2005,7]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            two\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            matrices over a ring\n            <jats:italic>R<\/jats:italic>\n            (e.g., the reals or the integers) each containing at most\n            <jats:italic>m<\/jats:italic>\n            nonzero elements. We present a new algorithm that multiplies\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>0.7<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1.2<\/jats:sup>\n            +\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              2+\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            ) algebraic operations (i.e., multiplications, additions and subtractions) over\n            <jats:italic>R<\/jats:italic>\n            . The na\u00efve matrix multiplication algorithm, on the other hand, may need to perform \u2126(\n            <jats:italic>mn<\/jats:italic>\n            ) operations to accomplish the same task. For\n            <jats:italic>m<\/jats:italic>\n            \u2264\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1.14<\/jats:sup>\n            , the new algorithm performs an almost optimal number of only\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              2+\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            operations. For\n            <jats:italic>m<\/jats:italic>\n            \u2264\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1.68<\/jats:sup>\n            , the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2.38<\/jats:sup>\n            ) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast\n            <jats:italic>rectangular<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/1077464.1077466","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"2-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":172,"title":["Fast sparse matrix multiplication"],"prefix":"10.1145","volume":"1","author":[{"given":"Raphael","family":"Yuster","sequence":"first","affiliation":[{"name":"University of Haifa, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2005,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser P. Clausen M. and Shokrollahi M. 1997. Algebraic complexity theory. Springer-Verlag New York.   B\u00fcrgisser P. Clausen M. and Shokrollahi M. 1997. Algebraic complexity theory. Springer-Verlag New York.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509911"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793256223"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359556"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of 44th Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 438--449","author":"Cohn H.","unstructured":"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 . 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."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0438"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_2_1_11_1","unstructured":"Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms Second ed. The MIT Press Cambridge Mass.   Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms Second ed. The MIT Press Cambridge Mass."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of 41st Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 381--389","author":"Demetrescu C.","unstructured":"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 . 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."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00252-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/355791.355796"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211028"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213017"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1998.0476"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of 14th Symposium on Discrete Algorithms. ACM","author":"Kratsch D.","unstructured":"Kratsch , D. , and Spinrad , J . 2003. Between O(nm) and O(n&alpha;) . In Proceedings of 14th Symposium on Discrete Algorithms. ACM , New York, 709--716. Kratsch, D., and Spinrad, J. 2003. Between O(nm) and O(n&alpha;). In Proceedings of 14th Symposium on Discrete Algorithms. ACM, New York, 709--716."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of 12th ESA, 532--543","author":"Mucha M.","unstructured":"Mucha , M. , and Sankowski , P . 2004a. Maximum matchings in planar graphs via gaussian elimination . In Proceedings of 12th ESA, 532--543 . Mucha, M., and Sankowski, P. 2004a. Maximum matchings in planar graphs via gaussian elimination. In Proceedings of 12th ESA, 532--543."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.40"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_22_1","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Ne\u0161et\u0159il J.","year":"1985","unstructured":"Ne\u0161et\u0159il , J. , and Poljak , S. 1985 . On the complexity of the subgraph problem . Comment. Math. Univ. Carol. 26 , 2, 415 -- 419 . Ne\u0161et\u0159il, J., and Poljak, S. 1985. On the complexity of the subgraph problem. Comment. Math. Univ. Carol. 26, 2, 415--419.","journal-title":"Comment. Math. Univ. Carol."},{"key":"e_1_2_1_23_1","series-title":"Lecture Notes in Computer Science","volume-title":"How to multiply matrices faster","author":"Pan V.","unstructured":"Pan , V. 1985. How to multiply matrices faster . In Lecture Notes in Computer Science , vol. 179 . Springer-Verlag , New York . Pan, V. 1985. How to multiply matrices faster. In Lecture Notes in Computer Science, vol. 179. Springer-Verlag, New York."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90005-9"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402147"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of 43rd Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 679--688","author":"Roditty L.","unstructured":"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 . 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."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1078"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of 40th Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 605--614","author":"Shoshan A.","unstructured":"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 . 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."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405954"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of 15th Symposium on Discrete Algorithms. ACM","author":"Yuster R.","unstructured":"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. 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."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567114"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1077464.1077466","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1077464.1077466","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:23:51Z","timestamp":1750267431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1077464.1077466"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["10.1145\/1077464.1077466"],"URL":"https:\/\/doi.org\/10.1145\/1077464.1077466","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,7]]},"assertion":[{"value":"2005-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}