Эффективные вычисления

DOI: https://doi.org/10.25559/SITITO.021.202502.158-165

Аннотация

В статье рассматривается более эффективный метод вычисления, чем вычисления, основанные по принципу "разделяй и властвуй". Ещё Гёте сказал: разделяй и властвуй хороший принцип, однако принцип объединяй и направляй лучше. Более эффективный метод, названный автором градуированным методом вычислений, соответствует этому принципу. Сюда в частности, относится метод быстрого умножения больших чисел используя преобразование Фурье. Алгоритмы, работающие по принципу "разделяй и властвуй", разработаны для сведения задачи с большой размерности к нескольким задачам меньшей размерности. Они описаны во многих учебниках по алгоритмам. Эффективность этого метода обосновывается описанный в этих учебниках мастер теореме. Этот метод обычно демонстрируется на алгоритме сортировки слиянием и на методе умножения Карацубы. Ранее автор на докладах в конференции и своих работах демонстрировал преимущество градуированного метода именно в задачах сортировки и умножении больших чисел.

Сведения об авторах

Rustem Rimovich Aidagulov, Московский государственный университет имени М.В. Ломоносова

старший научный сотрудник кафедры теоретической информатики отделения математики механико-математического факультета, кандидат физико-математических наук

Valery Alexandrovich Vasenin, Московский государственный университет имени М.В. Ломоносова

заведующий кафедрой математического моделирования и компьютерных исследований механико-математического факультета; заведующий лабораторией автоматизации экспериментальных исследований НИИ механики МГУ, доктор физико-математических наук, профессор

Литература

1. Karatsuba A., Ofman Yu. Multiplication of many-digital numbers by automatic computers. Dokl. Akad. Nauk SSSR. 1962;145(2):293-294. (In Russ.)
2. Karatsuba A.A. Comments to my works, written by myself. Proceedings of the Steklov Institute of Mathematics. 2013;282(Suppl 1):1-23. https://doi.org/10.1134/S0081543813070018
3. Karatsuba A.A. The Complexity of Computations. Trudy Matematicheskogo Instituta imeni V.A. Steklova = Proceedings of the Steklov Institute of Mathematics. 1995;211:169-183.
4. Aidagulov R.R., Glavatsky S.T. Graded Computing. Modern Information Technologies and IT-Education. 2019;15(2):274-282. (In Russ., abstract in Eng.) https://doi.org/10.25559/SITITO.15.201902.274-282
5. Gashkov S.B., Sergeev I.S. Multiplication. Chebyshevskii Sbornik. 2020;21(1):101-134. (In Russ., abstract in Eng.) https://doi.org/10.22405/2226-8383-2020-21-1-101-134
6. Strassen V. Gaussian elimination is not optimal. Numerische Mathematik. 1969;13:354-356.
7. Demmel J., Dumitriu I., Holtz O., Kleinberg R. Fast matrix multiplication is stable. arXiv:math/0603207. 2006. https://doi.org/10.48550/arXiv.math/0603207
8. Cohn H., Kleinberg R., Szegedy B., Umans C. Group-theoretic algorithms for matrix multiplication. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). Pittsburgh, PA, USA: IEEE Press; 2005. p. 379-388. https://doi.org/10.1109/SFCS.2005.39
9. Cohn H., Umans C. Fast matrix multiplication using coherent configurations. In: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms (SODA '13). New Orleans, Louisiana: Society for Industrial and Applied Mathematics, USA; 2013. p. 1074-1086.
10. Coppersmith D., Winograd S. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation. 1990;9(3):251-280. https://doi.org/10.1016/S0747-7171(08)80013-2
11. Le Gall F. Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC '14). New York, NY, USA: Association for Computing Machinery; 2014. p. 296-303. https://doi.org/10.1145/2608628.2608664
12. Zhdanovich D.V. The matrix capacity of a tensor. Journal of Mathematical Sciences. 2012;186(4):599-643. https://doi.org/10.1007/s10958-012-1009-7
13. Smirnov A.V. The bilinear complexity and practical algorithms for matrix multiplication. Computational Mathematics and Mathematical Physics. 2013;53:1781-1795. https://doi.org/10.1134/S0965542513120129
14. Moosbauer J., Poole M. Flip Graphs with Symmetry and New Matrix Multiplication Schemes. In: Proceedings of the 2025 International Symposium on Symbolic and Algebraic Computation (ISSAC '25). New York, NY, USA: Association for Computing Machinery; 2025. p. 233-239. https://doi.org/10.1145/3747199.3747566
15. Aidagulov R.R., Shamolin M.V. Groups of colors. Journal of Mathematical Sciences. 2009;161(5):615-627. https://doi.org/10.1007/s10958-009-9592-y
16. Aidagulov R.R. Fast multiplication algorithms. Intellektual'nye Sistemy. Teoriya i Prilozheniya = Intelligent Systems. Theory and Applications. 2022;26(1):134-139. (In Russ., abstract in Eng.) EDN: DVKLFX
17. Aidagulov R.R., Glavatsky S.T., Mikhalev A.V. Clustering Models. Journal of Mathematical Sciences. 2022;262(5):603-616. https://doi.org/10.1007/s10958-022-05841-9
18. Aidagulov R.R. Bigroup Algebras and Potter’s Theorem. Intellektual'nye Sistemy. Teoriya i Prilozheniya = Intelligent Systems. Theory and Applications. 2022;26(1):140-145. (In Russ., abstract in Eng.) EDN: VBJJXI
19. Alexeev N., Aidagulov R., Alekseyev M.A. A Computational Method for the Rate Estimation of Evolutionary Transpositions. In: Ortuño F., Rojas I. (eds.) Bioinformatics and Biomedical Engineering. IWBBIO 2015. Lecture Notes in Computer Science. Vol. 9043. Cham: Springer; 2015. p. 471-480. https://doi.org/10.1007/978-3-319-16483-0_46
20. Aidagulov R.R., Shamolin M.V. Fast Matrix Multiplication by Using Color Algebras. Journal of Mathematical Sciences. 2017;227(4):402-406. https://doi.org/10.1007/s10958-017-3593-z
Опубликована
2025-07-21
Как цитировать
AIDAGULOV, Rustem Rimovich; VASENIN, Valery Alexandrovich. Эффективные вычисления. Современные информационные технологии и ИТ-образование, [S.l.], v. 21, n. 2, p. 158-165, july 2025. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/1212>. Дата доступа: 28 may 2026 doi: https://doi.org/10.25559/SITITO.021.202502.158-165.
Форматы библиографических ссылок
Выпуск
Том 21 № 2 (2025): Современные информационные технологии и ИТ-образование
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук
Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.