Article
Full entry | Fulltext not available
(moving wall
12 months)
Feedback
Summary:
V článku detailněji poukážeme na zajímavý a zároveň důležitý aspekt Strassenova násobení matic. Navazujeme tím na nedávno publikovaný článek o jeho geometrické interpretaci. Ukážeme, že konstrukce a efektivita Strassenova algoritmu (resp. každého algoritmu podobného typu) souvisí s rozvojem a hodností jistého tenzoru (resp. jisté třídy tenzorů). V článku se tak na chvíli zastavíme i u tenzorů samotných. Na závěr připomeneme pozoruhodné pokroky v této oblasti z nedávné doby.
References:
[1] Bini, D., Lotti, G.: Stability of fast algorithms for matrix multiplication. Numer. Math. 36 (1980), 63–72. DOI 10.1007/BF01395989
[2] Brandts, J., Křížek, M.: Geometrická interpretace Strassenova násobení matic. Pokroky Mat. Fyz. Astronom. 70 (2025), 141–148.
[3] Brent, R. P.: Algorithms for matrix multiplication. Technical Report. Computer Science Department, Stanford University, STAN-CS-70-157, March 1970. Dostupné z: http://i.stanford.edu/pub/cstr/reports/cs/tr/70/157/CS-TR-70-157.pdf
[4] Demmel, J., Dumitriu, I., Holtz, O., Kleinberg, R.: Fast matrix multiplication is stable. Numer. Math. 106 (2007), 199–224. DOI 10.1007/s00211-007-0061-6
[5] Dumas, J.-G., Pernet, C., Sedoglavic, A.: Strassen’s algorithm is not optimally accurate. ACM, Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation, 2024, 254–263.
[6] Fawzi, A., Balog, M., Huang, A., Hubert, T., Romera-Paredes, B., Barekatain, M., Novikov, A., Ruiz, F. J. R., Schrittwieser, J., Swirszcz, G., Silver, D., Hassabis, D., Kohli, P.: Discovering faster matrix multiplication algorithms with reinforcement learning. Nature 610 (2022), 47–53. DOI 10.1038/s41586-022-05172-4
[7] de Groote, H. F.: On varieties of optimal algorithms for the computation of bilinear mappings I. The isotropy group of a bilinear mapping. Theor. Comput. Sci. 7 (1978), 1–24. DOI 10.1016/0304-3975(78)90038-5
[8] de Groote, H. F.: On varieties of optimal algorithms for the computation of bilinear mappings II. Optimal algorithms for $2\times 2$-matrix multiplication. Theor. Comput. Sci. 7 (1978), 127–148. DOI 10.1016/0304-3975(78)90045-2
[9] Kiers, H. A. L.: Towards a standardized notation and terminology in multiway analysis. J. Chemometrics 14 (2000), 105–122. DOI 10.1002/1099-128X(200005/06)14:3<105::AID-CEM582>3.0.CO;2-I
[10] Kolda, T. G., Bader, B. W.: Tensor decompositions and applications. SIAM Rev. 51 (2009), 455–500. DOI 10.1137/07070111X | Zbl 1173.65029
[11] Novikov, A., Vu, N., Eisenberger, M., Dupont, E., Huang, P.-S., Wagner, A. Z., Shirobokov, S., Kozlovskii, B., Ruiz, F. J. R., Mehrabian, A., Kumar, M. P., See, A., Chaudhuri, S., Holland, G., Davies, A., Nowozin, S., Kohli, R., Balog, M.: AlphaEvolve: A coding agent for scientific and algorithmic discovery. [online], [cit. 26. 3. 2026]. Technical Report. Google DeepMind, 2025. Dostupné z: https://arxiv.org/abs/2506.13131
[12] Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13 (1969), 354–356. DOI 10.1007/BF02165411 | Zbl 0185.40101
Search
Partner of
