Градуированные вычисления
Authors: ГЛАВАЦКИЙ С.Т. , АЙДАГУЛОВ Р.Р. 
Published: January 2025

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

Calculations with a large amount of data (or data of a large dimension) are usually reduced to sets of calculations with fairly small amounts of them. One of the methods of such information is filtering, when splitting the entire volume of data into small components is reduced to the consideration of branching on a graph (tree). The filtering method of computations, briefly formulated as the divide and rule method, is often positioned as the most effective method of reducing the number of operations in complex computations. We consider here a more efficient method, the method of graded calculations, the essence of which has not been previously published. The main content of our method is to split the set of elements of the calculation according to their values. This avoids many repetitions in intermediate calculations. Graduation of a linear space implies splitting it into subspaces in the same way as when representing it as a tensor product of components of small dimensions. In this case, the values are linear functionals, which are calculated as polynomials that associate certain values with the basiss elements of the components of the tensor product. In sorting problems, the gain is probably not so significant, and in multiplication problems, the gain in the method of graded calculations appears explicitly. Even in the case of the multiplication of large numbers, the representation of a polynomial in one variable as a polynomial in several variables, corresponding to the tensor product of spaces of small dimensions (small degrees in the components), leads to more efficient algorithms than the Karatsuba algorithm, corresponding to the calculation with filtering. Our algorithm allows us to perform calculations for Nlog(N) operations with the amount of data N. The filtering method leads, generally speaking, to N exponential operations (multiplication) 1.