Graded Computing

Abstract

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 basis’s 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.