Approximate Factorization of Polynomials in Many Variables and Other Problems in Approximate Algebra via Singular Value Decomposition Methods

numerical algebra;computer algebra;polynomial factorization;symbolic-numerics

May, John P ; Erich Kaltofen, Committee Chair,Hoon Hong, Committee Member,Agnes Szanto, Committee Member,Pierre Gramaud, Committee Member,Mark Giesbrecht, Committee Member,May, John P ; Erich Kaltofen ; Committee Chair ; Hoon Hong ; Committee Member ; Agnes Szanto ; Committee Member ; Pierre Gramaud ; Committee Member ; Mark Giesbrecht ; Committee Member

University:North Carolina State University

关键词: numerical algebra;    computer algebra;    polynomial factorization;    symbolic-numerics;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/5379/etd.pdf?sequence=1&isAllowed=y

美国|英语

来源: null

【 摘 要 】

Aspects of the approximate problem of finding the factors of a polynomial in many variables are considered.The idea is that an polynomial may be the result of a computation where a reducible polynomial was expected but due to introduction of floating point coefficients or measurement errors the polynomial is irreducible.Introduction of such errors will nearly always cause polynomials to become irreducible.Thus, it is important to be able to decide whether the computed polynomial is near to a polynomial that factors (and hence should be treated as reducible).If this is the case, one would like to be able to find a closest polynomial that does indeed factor.Though this problem is computable there is no known polynomial time algorithm to find the nearest polynomial that factors. However, there are a number of methods that can be used to find a nearby polynomial that factors if the originalpolynomial was very close to being factorizable. This dissertation gives a method to find a lower bound on the distance to the nearest polynomial that factors.If this lower bound is quite large, one can conclude that the polynomial does not have approximate factors.As part of finding this bound, a linear condition for irreducibility of polynomials from bivariate polynomials is generalized to polynomials with many variables, and a general theory of low rank approximation to extend bounds results to many different polynomial norms is given.The singular value decomposition methods used to find the above lower bound can be used to create another method to find a nearby polynomial that factors.This method is studied, and is shown to be practical.Similar methods are also shown to work for approximate division and approximate greatest common divisor computation.The results on bounding the distance to the nearest polynomial that factors can be applied to functional decomposition of univariate polynomials.Results on functional decomposition from the 1970's together with approximate factorization results allow for a method to compute a lower bound on the distance to the nearest polynomial that has a non-trivial functional decomposition and a new algorithm to compute approximate decompositions.