Algorithm of Polynomial Factorization and Its Implementation in Maple

V. M. Adukov

doi:10.14529/mmp180408

Authors

V. M. Adukov South Ural State University

DOI:

https://doi.org/10.14529/mmp180408

Keywords:

Wiener-Hopf factorization, polynomial factorization, Toeplitz matrices.

Abstract

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.

Author Biography

V. M. Adukov, South Ural State University

Doctor of Physico-Mathematical Sciences, Professor

References

Daniele V.G., Zich R.S. The Wiener-Hopf Method in Electromagnetics. ISMB Series, New Jersey, SciTech Publishing, 2014. DOI: 10.1049/SBEW503E

Abrahams I.D. On the Application of the Wiener-Hopf Technique to Problems in Dynamic Elasticity. Wave Motion, 2002, vol. 36, pp. 311-333. DOI: 10.1016/S0165-2125(02)00027-6

Lawrie J.B., Abrahams I.D. A Brief Historical Perspective of the Wiener-Hopf Technique. Journal of Engineering Mathematics, 2007, vol. 59, pp. 351-358. DOI: 10.1007/s10665-007-9195-x

Clancey K., Gohberg I. Factorization of Matrix Functions and Singular Integral Operators. Basel, Birkauser, 1987.

Gohberg I.C., Feldman I.A. Convolution Equations and Projection Methods for Their Solution. Providence, American Mathematical Society, 1974.

Rogosin S., Mishuris G. Constructive Methods for Factorization of Matrix-Functions. IMA Journal of Applied Mathematics, 2016, vol. 81, no. 2, pp. 365-391. DOI: 10.1093/imamat/hxv038

Kisil A.V. A Constructive Method for an Approximate Solution to Scalar Wiener-Hopf Equations. Proceedings of The Royal Society A Mathematical Physical and Engineering Sciences, 2013, vol. 469, no. 2154, article ID: 20120721. DOI: 10.1098/rspa.2012.0721

Gautschi W. On the Condition of Algebraic Equations. Numerische Mathematik, 1973, vol. 21, no. 5, pp. 405-424. DOI:10.1007/BF01436491

Uhlig F. Are the Coefficients of a Polynomial Well-Condition Function of Its Roots? Numerische Mathematik, 1992, vol. 61, no. 1, pp. 383-393. DOI: 10.1007/BF01385516

Bini D.A., B'ottcher A. Polynomial Factorization through Toeplitz Matrix Computations. Linear Algebra Application, 2003, vol. 366, pp. 25-37.

Boyd D.W. Two Sharp Inequalities for the Norm of a Factor of a Polynomials. Mathematika, 1992, vol. 39, no. 2, pp. 341-349. DOI: 10.1112/S0025579300015072

Adukov V.M. Generalized Inversion of Block Toeplitz Matrices. Linear Algebra Appliction, 1998, vol. 274, pp. 85-124.

Adukov V.M. On Wiener-Hopf Factorization of Scalar Polynomials. 2018. Available at: http://arxiv.org/abs/1806.01646.

Gakhov F.D. Boundary Value Problems. N.Y., Dover, 1990.