Регулярные оценки сложности умножения многочленов и усеченного ДПФ

Сергеев, И.С.

Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 29 мая 2019 г.

Автор: Сергеев И.С.
Журнал: Прикладная дискретная математика
Номер: 4
Год издания: 2011
Издательство: Изд-во ТГУ
Местоположение издательства: Томск
Первая страница: 72
Последняя страница: 88
Аннотация: В работе строятся схемы для умножения многочленов и усеченного ДПФ, эффективные с точки зрения сложности и глубины или сложности и объема памяти. Как следствие, например, умножение многочленов суммарной степени n=2^{n_1}+...+2^{n_s}, где n_1>...>n_s, над кольцом, в котором обратима двойка, можно выполнить со сложностью M(n_1)+...+M(n_s)+O(n) арифметических операций в этом кольце и глубиной max_i{D(n_i)}+O(log n), где M(k) и D(k) - соответственно сложность и глубина схемы умножения по модулю x^{2^k}+1. Или, например, усеченное ДПФ порядка n (т.е. ДПФ порядка 2^{┌log_2 n┐}, приведенное к векторам длины n) можно реализовать схемой сложности 1,5nlog_2 n+O(n) и объема памяти n+1.
Добавил в систему: Сергеев Игорь Сергеевич

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

ИСТИНА

ИСТИНА ИНХС РАН

Регулярные оценки сложности умножения многочленов и усеченного ДПФстатья

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