УДК 519.95
Об арифметической сложности вычисления линейных преобразований / С. Б. Гашков. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2014. № 6. С. 19-31.
Получены точные по порядку квадратичные и чуть более высокие оценки сложности вычисления некоторых линейных преобразований схемами в базисе {x+y} ∪ {ax: |a| ≤ C}, состоящем из операции сложения и скалярных умножений на ограниченные константы, а также верхние оценки O(n log n) для сложности вычисления в базисе, состоящем из всех линейных функций {ax+by: a,b ∈ {ℝ}}. Нижние оценки вида Θ(n log n) получены для базиса из всех монотонных линейных функций {ax+by: a,b > 0}.
Ключевые слова: биномиальное преобразование, преобразования Стирлинга, преобразование Лаха, треугольник Паскаля, треугольник Паскаля по простому модулю, матрица Серпинского, матрица Адамара-Сильвестра, треугольники Стирлинга 1-го и 2-го рода, коэффициенты Гаусса, коэффициенты Галуа, сложность вычисления, схемы в базисах из арифметических и линейных операций.
Библиогр. 17.
