Чебышевский сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Чебышевский сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Чебышевский сб., 2020, том 21, выпуск 1, страницы 101–134 (Mi cheb863)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Умножение

С. Б. Гашковa, И. С. Сергеевb

a Московский государственный университет им. М. В. Ломоносова (г. Москва)
b Научно-исследовательский институт «Квант» (г. Москва)

Аннотация: В работе предпринимается обзор современного состояния теории быстрых алгоритмов умножения чисел и многочленов. Рассматривается процесс эволюции методов умножения от первых блочных алгоритмов Карацубы и Тоома 1960-х гг. к методам 1970-х гг., опирающимся на дискретное преобразование Фурье (ДПФ), и далее к новейшим методам, разработанным в 2007–2019 гг. Современные методы умножения сочетают использование специальных алгебраических структур, переход к приближенным вычислениям, особые формы преобразований Фурье: многомерное ДПФ, аддитивный аналог ДПФ. Эти и другие существенные для быстрых методов умножения концепции подробно рассматриваются в настоящем обзоре. Отдельно предусмотрено введение в теорию ДПФ с извлечением необходимых для изложения материала фактов. В заключительной части обзора приводятся краткие сведения о результатах в области параллельных алгоритмов умножения, аккуратных оценок сложности базовых методов умножения, алгоритмов умножения в реальном времени, мультипликативной сложности умножения многочленов над конечными полями. Отмечены модели вычислений, в которых умножение имеет линейную или квадратичную сложность.

Ключевые слова: быстрые вычисления, умножение, сложность, дискретное преобразование Фурье, аддитивное ДПФ.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 19-01-00294_а
Исследование выполнено при поддержке гранта РФФИ (проект 19-01-00294а).


DOI: https://doi.org/10.22405/2226-8383-2018-21-1-101-134

Полный текст: PDF файл (810 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.7

Образец цитирования: С. Б. Гашков, И. С. Сергеев, “Умножение”, Чебышевский сб., 21:1 (2020), 101–134

Цитирование в формате AMSBIB
\RBibitem{GasSer20}
\by С.~Б.~Гашков, И.~С.~Сергеев
\paper Умножение
\jour Чебышевский сб.
\yr 2020
\vol 21
\issue 1
\pages 101--134
\mathnet{http://mi.mathnet.ru/cheb863}
\crossref{https://doi.org/10.22405/2226-8383-2018-21-1-101-134}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/cheb863
  • http://mi.mathnet.ru/rus/cheb/v21/i1/p101

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. А. Алексашкина, А. Н. Костромин, Ю. В. Нестеренко, “О быстром алгоритме вычисления преобразования Фурье”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2021, № 3, 36–41  mathnet
  • Просмотров:
    Эта страница:100
    Полный текст:84
    Литература:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021