Algorithm of Polynomial Factorization and Its Implementation in Maple

In the work we propose an algorithm for a Wiener-Hopf factorization of scalar polynomials. The algorithm based on notions of indices and essential polynomials allows to find the factorization factors of the polynomial with the guaranteed accuracy. The method uses computations with finite Toeplitz matrices and permits to obtain coefficients of both factorization factors simultaneously. Computation aspects of the algorithm are considered. An a priory estimate for the condition number of the used Toeplitz matrices is found. Formulas for computation of the Laurent coefficients with the given accuracy for functions that analytical and non-vanishing in an annular neighborhood of the unit circle are obtained. Stability of the factorization factors is studied. Upper bounds for the accuracy of the factorization factors are established. All estimates are effective. The proposed algorithm is implemented in Maple computer system as module 'PolynomialFactorization'. Numerical experiments with the module show a good agreement with the theoretical studies.В работе предложен алгоритм факторизации Винера - Хопфа скалярных многочленов. Алгоритм, основанный на понятиях индексов и существенных многочленов, позволяет найти факторизационные множители многочлена с гарантированной точностью. Метод использует вычисления с конечными теплицевыми матрицами и дает возможность получить коэффициенты обоих факторизационных факторов одновременно. Рассмотрены вычислительные аспекты алгоритма. Найдена априорная оценка числа обусловленности используемой теплицевой матрицы. Получены формулы для вычисления лорановских коэффициентов с заданной точностью для функций аналитических и не обращающихся в нуль в кольцевой окрестности единичной окружности. Изучена устойчивость факторизационных множителей. Установлены верхние границы точности вычисления факторизационных множителей. Все оценки являются эффективными. Предложенный алгоритм был реализован в компьютерной системе Maple в виде модуля 'PolynomialFactorization'. Численные эксперименты с модулем показали хорошее согласие с теоретическим исследованием