Градуированные вычисления

  • Rustem Rimovich Aidagulov Московский государственный университет имени М.В. Ломоносова; Институт машиноведения РАН имени А.А. Благонравова http://orcid.org/0000-0002-6579-429X
  • Sergei Timofeevich Glavatsky Московский государственный университет имени М.В. Ломоносова http://orcid.org/0000-0003-1857-6158

Аннотация

Вычисления с большим количеством данных (или данных большой размерности) обычно сводят к наборам вычислений с достаточно малыми их объемами. Одним из способов такого сведения является фильтрация, когда разбиение всего объема данных на мелкие составляющие сводится к рассмотрению ветвлений на графе (дереве). Метод фильтрации вычислений, кратко формулируемый как метод «разделяй и властвуй», часто позиционируется как наиболее эффективный метод сокращения количества операций в сложных вычислениях. Мы рассмотрим здесь более эффективный метод, метод градуированных вычислений, суть которого ранее не была опубликована.
Основное содержание нашего метода заключается в разбиении множества элементов вычисления по их значениям. Это позволяет избежать множества повторов в промежуточных вычислениях. Градуировка линейного пространства предполагает разбиение его на подпространства так же, как при представлении его в виде тензорного произведения компонент малых размерностей. Значениями в этом случае являются линейные функционалы, которые вычисляются как многочлены, сопоставляющие определенные значения базисным элементам компонентов тензорного произведения.
В задачах сортировки выигрыш скорее не так существенен, а в задачах умножения выигрыш метода градуированных вычислений проявляется явно. Даже в случае произведения больших чисел, представление многочлена от одной переменной как многочлена от нескольких переменных, соответствующее тензорному произведению пространств малых размерностей (малых степеней в компонентах), приводит к более эффективным алгоритмам, нежели алгоритм Карацубы, соответствующий вычислению с фильтрацией. Наш алгоритм позволяет выполнить вычисления за Nlog (N) операций при количестве данных  N . Метод фильтрации приводит, вообще говоря, к Nα  операций с экспонентой (умножения) α > 1.

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

Rustem Rimovich Aidagulov, Московский государственный университет имени М.В. Ломоносова; Институт машиноведения РАН имени А.А. Благонравова

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

Sergei Timofeevich Glavatsky, Московский государственный университет имени М.В. Ломоносова

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

Литература

[1] Strassen V. Gaussian elimination is not optimal. Numerische Mathematik. 1969; 13(4):354-356. (In Eng.) DOI: 10.1007/BF02165411
[2] Demmel J., Dumitriu I., Holtz O. Fast linear algebra is stable. Numerische Mathematik. 2007; 108(1):59-91. (In Eng.) DOI: 10.1007/s00211-007-0114-x
[3] Coppersmith D., Winograd S. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation. 1990; 9(3):251-280. (In Eng.) DOI: 10.1016/S0747-7171(08)80013-2
[4] Zhdanovich D.V. The matrix capacity of a tensor. Journal of Mathematical Sciences. 2012; 186(4):599-643. (In Eng.) DOI: 10.1007/s10958-012-1009-7
[5] François Le Gall. Powers of tensors and fast matrix multiplication. In: Katsusuke Nabeshima (eds). Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC '14). ACM, New York, NY, USA. 2014; p. 296-303. (In Eng.) DOI: 10.1145/2608628.2608664
[6] Aidagulov R.R. B and Group Algebras and their Automorphisms. Dnevnik Nauki. 2019; 1(25):25. Available at: https://elibrary.ru/item.asp?id=36901640 (accessed 6.05.2019). (In Russ., abstract in Eng.)
[7] Aidagulov R.R. Group Algebras and Quantum Combinatorics. Dnevnik Nauki. 2019; 1(25):26. Available at: https://elibrary.ru/item.asp?id=36901641 (accessed 6.05.2019). (In Russ., abstract in Eng.)
[8] Harvey D., van der Hoeven J. Integer multiplication in time O(n log n). 2019; hal-02070778. Available at: https://hal.archives-ouvertes.fr/hal-02070778/file/nlogn.pdf (accessed 6.05.2019). (In Eng.)
[9] Harvey D. Faster truncated integer multiplication. CoRR. 2017; abs/1703.00640. Available at: http://arxiv.org/abs/1703.00640 (accessed 6.05.2019). (In Eng.)
[10] Harvey D., van der Hoeven J. Faster integer and polynomial multiplication using cyclotomic coefficient rings. CoRR. 2017; abs/1712.03693. Available at: http://arxiv.org/abs/1712.03693 (accessed 6.05.2019). (In Eng.)
[11] Harvey D., van der Hoeven J. On the complexity of integer matrix multiplication. Journal of Symbolic Computation. 2018; 89:1-8. (In Eng.) DOI: 10.1016/j.jsc.2017.11.001
[12] Harvey D., van der Hoeven J. Faster integer multiplication using plain vanilla FFT primes. Mathematics of Computation. 2019; 88:501-514. (In Eng.) DOI: 10.1090/mcom/3328
[13] Harvey D., van der Hoeven J. Faster integer multiplication using short lattice vectors. In: Scheidler R., Sorenson J. (eds). ANTS XIII. Proceedings of the Thirteenth Algorithmic Number Theory Symposium. Mathematical Sciences Publishers, Berkeley. 2019; 293-310. (In Eng.) DOI: 10.2140/obs.2019.2.293
[14] Harvey D., van der Hoeven J. Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. Journal of Complexity. 2019; 54:101404. (In Eng.) DOI: 10.1016/j.jco.2019.03.004
[15] Harvey D., van der Hoeven J. Polynomial multiplication over finite fields in time O(n log n). 2019; hal-02070816. Available at: https://hal.archives-ouvertes.fr/hal-02070816 (accessed 6.05.2019). (In Eng.)
[16] Harvey D., van der Hoeven J., Lecerf G. Even faster integer multiplication. Journal of Complexity. 2016; 36:1-30. (In Eng.) DOI: 10.1016/j.jco.2016.03.001
[17] Harvey D., van der Hoeven J., Lecerf G. Faster Polynomial Multiplication over Finite Fields. Journal of the ACM. 2017; 63(6):52. 23 p. (In Eng.) DOI: 10.1145/3005344
[18] van der Hoeven J. Faster relaxed multiplication. In: Katsusuke Nabeshima (ed). Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC '14). ACM, New York, NY, USA. 2014; 405-412. (In Eng.) DOI: 10.1145/2608628.2608657
[19] Brent R.P., Zimmermann P. Modern Computer Arithmetic, Cambridge Monographs on Applied and Computational Mathematics. Vol. 18. Cambridge University Press, Cambridge, 2010. 236 p. (In Eng.)
[20] De A., Kurur P., Saha C., Saptharishi R. Fast Integer Multiplication Using Modular Arithmetic. SIAM Journal on Computing. 2013; 42(2):685-699. (In Eng.) DOI: 10.1137/100811167
Опубликована
2019-07-25
Как цитировать
AIDAGULOV, Rustem Rimovich; GLAVATSKY, Sergei Timofeevich. Градуированные вычисления. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 15, n. 2, p. 274-282, july 2019. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/513>. Дата доступа: 21 nov. 2019 doi: https://doi.org/10.25559/SITITO.15.201902.274-282.
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук