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.

Keywords

Wiener-Hopf factorization; polynomial factorization; Toeplitz matrices.

References

1. Daniele V.G., Zich R.S. The Wiener-Hopf Method in Electromagnetics. ISMB Series, New Jersey, SciTech Publishing, 2014. DOI: 10.1049/SBEW503E
2. 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
3. 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
4. Clancey K., Gohberg I. Factorization of Matrix Functions and Singular Integral Operators. Basel, Birkauser, 1987.
5. Gohberg I.C., Feldman I.A. Convolution Equations and Projection Methods for Their Solution. Providence, American Mathematical Society, 1974.
6. 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
7. 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
8. Gautschi W. On the Condition of Algebraic Equations. Numerische Mathematik, 1973, vol. 21, no. 5, pp. 405-424. DOI:10.1007/BF01436491
9. 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
10. Bini D.A., B'ottcher A. Polynomial Factorization through Toeplitz Matrix Computations. Linear Algebra Application, 2003, vol. 366, pp. 25-37.
11. 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
12. Adukov V.M. Generalized Inversion of Block Toeplitz Matrices. Linear Algebra Appliction, 1998, vol. 274, pp. 85-124.
13. Adukov V.M. On Wiener-Hopf Factorization of Scalar Polynomials. 2018. Available at: http://arxiv.org/abs/1806.01646.
14. Gakhov F.D. Boundary Value Problems. N.Y., Dover, 1990.