Article
Full entry | Fulltext not available
(moving wall
12 months)
Feedback
Summary:
V roce 1969 Strassen ukázal, že součin dvou reálných matic typu $2\times 2$ lze vypočítat pouze pomocí sedmi součinů reálných čísel. Do té doby se všeobecně věřilo, že je zapotřebí osm takových součinů. Výsledný algoritmus je však považován za neintuitivní a chybí také názorné a srozumitelné odvození Strassenovy metody. V tomto článku proto představíme geometrickou interpretaci této metody, podobnou té, která je základem Karatsubova algoritmu pro efektivní násobení celých čísel.
References:
[1] Alman, J., Duan, R., Williams, V. V., Xu, Y., Xu, Z., Zhou, R.: More asymmetry yields faster matrix multiplication. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2024, 2005–2039.
[2] Cariow, A., Paplinski, J. P.: Some algorithms for computing short-length linear convolutions. Electronics 9 (2020), 1–22. DOI 10.3390/electronics9122115
[3] Cooley, J. W., Tukey, J. W.: An algorithm for the machine calculation of complex Fourier series. Math. Comp. 19 (1965), 297–301. Zbl 0127.09002
[4] Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symbolic Comput. 9 (1990), 251–280. DOI 10.1016/S0747-7171(08)80013-2
[5] Dumas, J.-G., Pernet, C., Sedoglavic, A.: Strassen’s algorithm is not optimally accurate. ISSAC ’24: Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation, ACM, 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] Karatsuba, A. A., Ofman, Y. P.: Multiplication of many-digital numbers by automatic computer. (in Russian). Dokl. Akad. Nauk SSSR 145 (1962), 293–294. Engl. transl. Physics-Doklady 7 (1963), 595–596.
[8] Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13 (1969), 354–356. DOI 10.1007/BF02165411 | Zbl 0185.40101
[9] Toom, A. L.: The complexity of a scheme of functional elements simulating the multiplication of integers. (in Russian). Dokl. Akad. Nauk SSSR 150 (1963), 496–498. Engl. transl. Soviet Math. 3 (1963), 714–716.
[10] Winograd, S.: Arithmetic complexity of computations. SIAM, 1980.
Search
Partner of
