Abstract:
Quadratic and superquadratic estimates are obtained for the complexity of computations of some linear transforms by circuits over the base $\{x+y \}\cup \{ax: \vert a \vert \leq 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 \in {\mathbb R}\}$. Lower bounds $\Theta(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.
Fulltext:
PDF file (400 kB)