Article
| Title: | Geometrická interpretace Strassenova násobení matic (Czech) |
| Title: | Geometric Interpretation of Strassen's Matrix Multiplication (English) |
| Author: | Brandts, Jan |
| Author: | Křížek, Michal |
| Language: | Czech |
| Journal: | Pokroky matematiky, fyziky a astronomie |
| ISSN: | 0032-2423 |
| Volume: | 70 |
| Issue: | 3 |
| Year: | 2025 |
| Pages: | 141-148 |
| Summary lang: | Czech |
| . | |
| Category: | math |
| . | |
| 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. (Czech) |
| MSC: | 65-01 |
| MSC: | 65F99 |
| MSC: | 65Y20 |
| . | |
| Date available: | 2026-03-04T03:29:14Z |
| Last updated: | 2026-03-12 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/153540 |
| . | |
| Reference: | [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. |
| Reference: | [2] Cariow, A., Paplinski, J. P.: Some algorithms for computing short-length linear convolutions.. Electronics 9 (2020), 1–22. 10.3390/electronics9122115 |
| Reference: | [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 |
| Reference: | [4] Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions.. J. Symbolic Comput. 9 (1990), 251–280. 10.1016/S0747-7171(08)80013-2 |
| Reference: | [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. |
| Reference: | [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. 10.1038/s41586-022-05172-4 |
| Reference: | [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. |
| Reference: | [8] Strassen, V.: Gaussian elimination is not optimal.. Numer. Math. 13 (1969), 354–356. Zbl 0185.40101, 10.1007/BF02165411 |
| Reference: | [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. |
| Reference: | [10] Winograd, S.: Arithmetic complexity of computations.. SIAM, 1980. |
| . |
Fulltext not available (moving wall 12 months)
Search
Partner of
