"Записки научных семинаров ПОМИ"
Том 373, стр. 157-188
О выборе алгоритма умножения для полиномов и
полиномиальных матриц
Г.И. Малашонок, Ю.Д. Валеев, А.О. Лапаев
Тамбовский государственный
университет им. Г. Р. Державина
ул. Интернациональная 33, 392622 Тамбов, Россия
malaschonok@ya.ru
- Аннотация:
Исследуются алгоритмы умножения для плотных и для
разреженных полиномов и полиномиальных матриц в разных
числовых областях. Получены выражения для сложности
операций умноженния полиномов и полиномиальных матриц как
математического ожидания числа машинных арифметических
операций. Приводится табуляция полученных выражений
сложности для набора параметров, представляющих
практический интерес. Представлены результаты экспериментов
с программами, вычисляющими произведения полиномов и
полиномиальных матриц исследуемыми алгоритмами. Обсуждается
возможность построения процедуры, автоматизирующей выбор
лучшего алгоритма в зависимости от диапазона параметров. Библ. -- 8 назв.
- Ключевые слова: алгоритмы умножения полиномов, алгоритмы
умножения матриц, полиномиальные матрицы, алгоритм
Карацубы, алгоритм Штрассена, модулярные алгоритмы, быстрое
преобразование Фурье
[algorithms of polynomial multiplication,
akgorithms of matrix multiplication, polynomial matrix,
Karatsubs's algorithm. Shtrassen's algorithm, modular
algorithms, fast Fourier transform]
Полный текст(.pdf)