Arithmetic Complexity of Certain Linear Transformations

S. B. Gashkov

Matematičeskie zametki, Tome 97 (2015) no. 4, pp. 529-555

Résumé

We obtain order-sharp quadratic and slightly higher estimates of the computational complexity of certain linear transformations (binomial, Stirling, Lah, Gauss, Serpiński, Sylvester) in the basis $\{x+y \}\cup \{ax: \vert a \vert \leq C \}$ consisting of the operations of addition and inner multiplication by a bounded constant as well as upper bounds $O(n\log n)$ for the computational complexity in the basis $\{ax+by: a,b \in {\mathbb R}\}$ consisting of all linear functions. Lower bounds of the form $\Omega(n\log n)$ are obtained for the basis consisting of all monotone linear functions $\{ax+by: a, b > 0\}$. For the finite arithmetic basis $B_{+,*,/} = \{x\pm y,xy,1/x,1\}$ and for the bases $\{x\pm y\} \cup \{nx: n \in {\mathbb N}\}\cup \{x/n: n \in {\mathbb N}\}$ and $B_{+,*}=\{x+y,xy,-1\}$, estimates $O(n \log n \log \log n)$ are obtained in certain cases. In the case of a field of characteristic $p$, computations in the basis $\{x+y \operatorname{mod} p\}$ are also considered.

Détail

Mots-clés : linear transformation (binomial, Gauss
Keywords: Stirling, Lah, Serpiński, Sylvester), arithmetic computational complexity of linear transformations, finite arithmetic basis, field of characteristic $p$,.