Arithmetic Complexity of Certain Linear Transformations Mathematical Notesстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 28 мая 2015 г.
Аннотация:We obtain order-sharp quadratic and slightly higher estimates of the computational
complexity of certain linear transformations (binomial, Stirling, Lah, Gauss, Serpin´ ski,
Sylvester) in the basis {x + y} ∪ {ax : |a| ≤ 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 ∈ R} consisting of all linear functions. Lower
bounds of the form Ω(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 ± y, xy, 1/x, 1} and
for the bases {x ± y} ∪ {nx : n ∈ N} ∪ {x/n : n ∈ 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 mod p} are also considered.
Keywords: linear transformation (binomial, Stirling, Lah, Gauss, Serpin´ ski, Sylvester), arithmetic
computational complexity of linear transformations, finite arithmetic basis, field of
characteristic p.