Эта публикация цитируется в
1 статье
Математика
Об арифметической сложности вычисления линейных преобразований
С. Б. Гашков Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
Аннотация:
Получены точные по порядку квадратичные и чуть более высокие оценки сложности вычисления некоторых линейных преобразований схемами в базисе
$\{x+y \}\cup \{ax: \vert a \vert \leq C \},$ состоящем из операции сложения и скалярных умножений на ограниченные константы, а также верхние оценки
$O(n\log n)$ для сложности вычисления в базисе, состоящем из всех линейных функций
$\{ax+by: a,b \in {\mathbb R}\}$. Нижние оценки вида
$\Theta(n\log n)$ получены для базиса из всех монотонных линейных функций
$\{ax+by: a, b > 0\}.$
Ключевые слова:
биномиальное преобразование, преобразования Стирлинга, преобразование Лаха, треугольник Паскаля, треугольник Паскаля по простому модулю, матрица Серпинского, матрица Адамара–Сильвестра, треугольники Стирлинга 1-го и 2-го рода, коэффициенты Гаусса, коэффициенты Галуа, сложность вычисления, схемы в базисах из арифметических и линейных операций.
УДК:
519.95
Поступила в редакцию: 10.10.2012
Полный текст:
PDF файл (400 kB)