Sparse bivariate polynomial factorization  

作　　者：WU WenYuan CHEN JingWei FENG Yong 

机构地区：[1]Chongqing Key Laboratory of Automated Reasoning and Cognition,Chongqing Institute of Green and Intelligent Technology,Chinese Academy of Sciences

出　　处：《Science China Mathematics》2014年第10期2123-2142,共20页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China(GrantNos.91118001 and 11170153);National Key Basic Research Project of China(Grant No.2011CB302400);Chongqing Science and Technology Commission Project(Grant No.cstc2013jjys40001)

摘　　要：Motivated by Sasaki＇s work on the extended Hensel construction for solving multivariate algebraic equations, we present a generalized Hensel lifting, which takes advantage of sparsity, for factoring bivariate polynomial over the rational number field. Another feature of the factorization algorithm presented in this article is a new recombination method, which can solve the extraneous factor problem before lifting based on numerical linear algebra. Both theoretical analysis and experimental data show that the algorithm is etIicient, especially for sparse bivariate polynomials.Motivated by Sasaki's work on the extended Hensel construction for solving multivariate algebraic equations,we present a generalized Hensel lifting,which takes advantage of sparsity,for factoring bivariate polynomial over the rational number field.Another feature of the factorization algorithm presented in this article is a new recombination method,which can solve the extraneous factor problem before lifting based on numerical linear algebra.Both theoretical analysis and experimental data show that the algorithm is efficient,especially for sparse bivariate polynomials.

关 键 词：polynomial factorization sparse polynomial generalized Hensel lifting 

分 类 号：O151.1[理学—数学]