| 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-10-05 |
| 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. |
| . |