Arithmetic complexity of calculation of linear transformations / S. B. Gashkov. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2014. № 6. P. 19-31 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 0].

Quadratic and superquadratic estimates are obtained for the complexity of computations of some linear transforms by circuits over the base {x+y} ∪ {ax: |a| ≤ C} consisting of addition and scalar multiplications on bounded constants. Upper bounds O(n log n) of computation complexity are obtained for the linear base {ax+by: a,b ∈ {ℝ}}. Lower bounds Θ(n log n) are obtained for the monotone linear base {ax+by: a,b > 0}.

Key words: binomial transform, Stirling's transforms, Lah's transform, Pascal's triangle, Pascal's triangle modulo p, Stirling's triangles, Serpinsky's matrix, Hadamar-Silvester matrix, Gauss's coefficients, Galois's coefficients, computational complexity, schemata over bases of arithmetical and linear operations.