Efficient Computations
Abstract
This article considers a computational method that is more efficient than methods based on the divide-and-conquer principle. Goethe once said that divide and conquer is a good principle, but the principle of unite and guide is better. A more efficient approach, called by the author the graded method of computations, follows this latter principle. It includes, in particular, the method of fast multiplication of large numbers using the Fourier transform. Divide-and-conquer algorithms are designed to reduce a high-dimensional problem to several smaller-dimensional problems. They are described in many algorithm textbooks. The efficiency of this method is justified by the master theorem presented in those textbooks. This approach is usually illustrated by merge sort and Karatsuba multiplication. Earlier, the author demonstrated the advantage of the graded method specifically in sorting problems and large-number multiplication in conference presentations and in [4].
References
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
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
