О выборе алгоритма умножения для полиномов и полиномиальных матриц

Исследуются алгоритмы умножения для плотных и для разреженных полиномов и полиномиальных матриц в разных числовых областях. Получены выражения для сложности операций умножения полиномов и полиномиальных матриц как математического ожидания числа арифметических операций. Приводится табуляция полученных выражений сложности для набора параметров, представляющих практический интерес. Представлены результаты экспериментов с программами, вычисляющими произведения полиномов и полиномиальных матриц исследуемыми алгоритмами. Обсуждается возможность построения процедуры, автоматизирующей выбор лучшего алгоритма в зависимости от диапазона параметров. Библ. – 8 назв.