NDLI: Exact polynomial factorization by approximate high degree algebraic numbers

Please wait, while we are loading the content...

Pseudospectra for exponential polynomial matrices

Rigorous global search using taylor models

Parametrization of ε-rational curves: extended abstract

Error free transformations of floating point numbers and its applications to constructing efficient error free numerical algorithms

Exact polynomial factorization by approximate high degree algebraic numbers

Preconditioning, randomization, solving linear systems, eigen-solving, and root-finding

Computing nearest Gcd with certification

Symbolic-numeric problems in the automatic analysis and verification of cyber-physical systems

Extracting numerical factors of multivariate polynomials from taylor expansions

De-Sinc numerical methods

Experimental evaluation and cross-benchmarking of univariate real solvers

An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination

A proof of the monotone column permanent (MCP) conjecture for dimension 4 via sums-of-squares of rational functions

Curve/surface intersection problem by means of matrix representations

Rigorous integration of flows and ODEs using taylor models

Continued fraction expansion of real roots of polynomial systems

Application of filter diagonalization method to numerical solution of algebraic equations

Nearly optimal symbolic-numerical algorithms for structured integer matrices and polynomials

Continuations and monodromy on random riemann surfaces

Finding exact minimal polynomial by approximations

Optimization and NP_R-completeness of certain fewnomials

A method for finding zeros of polynomial equations using a contour integral based eigensolver

Computing multivariate approximate GCD based on Barnett's theorem

Convergence and many-valuedness of hensel seriesnear the expansion point

Approximate factorization of polynomials over Z

Computing clustered close-roots of univariate polynomials

Finding positively invariant sets of a class of nonlinear loops via curve fitting

Reducing exact computations to obtain exact results based on stabilization techniques

Exact polynomial factorization by approximate high degree algebraic numbers

Content Provider	ACM Digital Library
Author	Feng, Yong Qin, Xiao-lin Zhang, Jing-zhong Chen, Jing-wei
Abstract	For factoring polynomials in two variables with rational coefficients, an algorithm using transcendental evaluation was presented by Hulst and Lenstra. In their algorithm, transcendence measure was computed. However, a constant c is necessary to compute the transcendence measure. The size of c involved the transcendence measure can influence the efficiency of the algorithm greatly. In this paper, we overcome the problem arising in Hulst and Lenstra's algorithm and propose a new polynomial time algorithm for factoring bivariate polynomials with rational coefficients. Using an approximate algebraic number of high degree instead of a variable of a bivariate polynomial, we can get a univariate one. A factor of the resulting univariate polynomial can then be obtained by a numerical root finder and the purely numerical LLL algorithm. The high degree of the algebraic number guarantees that this factor corresponds to a factor of the original bivariate polynomial. We prove that our algorithm saves a $(log^{2}(mn))^{2+ε}$ factor in bit-complexity comparing with the algorithm presented by Hulst and Lenstra, where (n, m) represents the bi-degree of the polynomial to be factored. We also demonstrate on many significant experiments that our algorithm is practical. Moreover our algorithm can be generalized to polynomials with variables more than two.
Starting Page	21
Ending Page	28
Page Count	8
File Format	PDF
ISBN	9781605586649
DOI	10.1145/1577190.1577199
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-08-03
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Polynomial Approximation Algebraic number Factorization
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

From an approximate to an exact absolute polynomial factorization

Approximation to real numbers by cubic algebraic numbers

Chinese academy of sciences (902).

Approximation of complex algebraic numbers by algebraic numbers of bounded degree

Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields

Approximation of complex algebraic numbers by algebraic numbers of bounded degree (2007).

Unconstrained parametric minimization of a polynomial: approximate and exact.

Finding exact minimal polynomial by approximations

Kronecker's theorem and rational approximation of algebraic numbers (1982).

Exact polynomial factorization by approximate high degree algebraic numbers

Similar Documents

From an approximate to an exact absolute polynomial factorization

Approximation to real numbers by cubic algebraic numbers

Chinese academy of sciences (902).

Approximation of complex algebraic numbers by algebraic numbers of bounded degree

Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields

Approximation of complex algebraic numbers by algebraic numbers of bounded degree (2007).

Unconstrained parametric minimization of a polynomial: approximate and exact.

Finding exact minimal polynomial by approximations

Kronecker's theorem and rational approximation of algebraic numbers (1982).

Exact polynomial factorization by approximate high degree algebraic numbers