Нижние оценки аддитивной сложности линейных операторов и
билинейных алгоритмов умножения матриц и многочленов над $GF(2)$
И. С. Сергеевa a Научно-исследовательский институт "Квант", г. Москва
Аннотация:
Для линейного оператора с явно заданной булевой матрицей размера
$n \times n$ установлена нижняя оценка сложности
$5n-o(n)$
при реализации аддитивными схемами над
$GF(2)$. Нижние оценки
$3n-o(n)$ доказаны для конструктивно заданных циклических матриц
и матриц Серпинского размера
$n \times n$. Попутно установлены
нижние оценки аддитивной сложности билинейных алгоритмов:
$(4-o(1))n^2$ – для умножения матриц размера
$n \times n$,
а также
$5n-o(n)$ – для умножения многочленов степени
$n-1$ и
$4n-o(n)$ – для циклической свертки порядка
$n$ над
$GF(2)$.
Библиография: 27 названий.
Ключевые слова:
аддитивные схемы, билинейные алгоритмы, булевы линейные операторы,
матрицы Серпинского, множества Сидона, нижние оценки сложности,
прямые суммы матриц, умножение матриц, умножение многочленов,
циклическая свертка, циклические матрицы, циклы в графах.
УДК:
519.71 Поступило: 14.10.2024
Исправленный вариант: 31.12.2024
DOI:
10.4213/mzm14541
Полный текст:
PDF файл (773 kB)
Первая страница:
PDF файл
