Arithmetic Complexity of Certain Linear Transformations Mathematical Notes

Gashkov, S.B.

Информация о цитировании статьи получена из Web of Science, Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 28 мая 2015 г.

Автор: Gashkov S.B.
Журнал: Mathematical Notes
Том: 97
Номер: 4
Год издания: 2015
Издательство: Pleiades Publishing, Ltd
Местоположение издательства: Road Town, United Kingdom
Первая страница: 531
Последняя страница: 555
DOI: 10.1134/S0001434615030256
Аннотация: 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.
Добавил в систему: Гашков Сергей Борисович

	ИСТИНА	Войти в систему Регистрация
	ФНКЦ РР
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ФНКЦ РР

Arithmetic Complexity of Certain Linear Transformations Mathematical Notesстатья

Прикрепленные файлы