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