УДК 519.71
Об одном соотношении двух мер сложности вычисления систем одночленов / В.В. Кочергин // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2009. № 4. С. 8-13.
Для одного класса матриц, задающих показатели степеней переменных в системе одночленов, установлена нетривиальная нижняя оценка сложности - минимального числа умножений, достаточного для вычисления системы по переменным. Также приведен пример последовательности матриц (и соответственно систем одночленов), для которой возможность использования наряду с самими переменными величин, обратных к переменным, приводит к снижению сложности асимптотически в 2 раза.
Ключевые слова: аддитивная цепочка, сложность вычисления систем одночленов.
Библиогр. 17.
