Article

A geometric-numeric algorithm for absolute factorization of multivariate polynomials

Authors:

Robert M. Corless,

André Galligo,

Ilias S. Kotsireas,

Stephen M. WattAuthors Info & Claims

ISSAC '02: Proceedings of the 2002 international symposium on Symbolic and algebraic computation

Pages 37 - 45

https://doi.org/10.1145/780506.780512

Published: 10 July 2002 Publication History

Abstract

In this paper, we propose a new semi-numerical algorithmic method for factoring multivariate polynomials absolutely. It is based on algebraic and geometric properties after reduction to the bivariate case in a generic system of coordinates. The method combines 4 tools: zero-sum relations at triplets of points, partial information on monodromy action, Newton interpolation on a structured grid, and a homotopy method. The algorithm relies on a probabilistic approach and uses numerical computations to propose a candidate factorization (with probability almost one) which is later validated.

References

[1]

Bajaj C. Canny J. Garrity R. Warren J. Factoring rational polynomials over the complexes, ISSAC'89 Proceedings, (1989), pp 81-90.

Digital Library

[2]

Chistov, A. L. and Gregoriev D. Y. Subexponential-time solving systems of algebraic equations preprint (1983).

[3]

Corless R. M. Giesbrecht M. W. Hoeij v. M. Kotsireas I. S. Watt S. M Towards Factoring Bivariate Approximate Polynomials, ISSAC'2001 Proceedings, London, Canada, July 2001, pp. 85-92.

Digital Library

[4]

Duval D. Absolute factorization of polynomials: a geometric approach, SIAM J. Comput. 20 (1991), no. 1, pp. 1-21.

Digital Library

[5]

Galligo, A. and Watt, S. An absolute primality test for bivariate polynomials Proc. Intern. Symp. on Symbolic and Algebraic Computation, 217-224, ACM Press (1997).

Digital Library

[6]

Galligo, A. and Ruppecht, D. Semi-Numerical Determination of Irreducible Branches of a Reduced Space Curve Proc. Intern. Symp. on Symbolic and Algebraic Computation, 137-142, ACM Press (2001).

Digital Library

[7]

Galligo, A. and Ruppecht, D. Absolute irreducible decomposition of Curves To appear in J. Symb. Comp.

Digital Library

[8]

Heintz, J. and Sieveking, M. Absolute primality of polynomials is decidable in random polynomial time in the number of variables Proc. ICALP (1981), LNCS 115, pp. 16-28.

Digital Library

[9]

Kaltofen E. Fast parallel absolute irreducibility testing, JSC vol 1, 1985, pp. 57-67.

Digital Library

[10]

Kaltofen E. Polynomial factorization 1987-1991. LATIN'92 Proceedings, Sao Paulo, Brazil, 1992, pp. 294-313, Lecture Notes in Comput. Sci., 583, Springer, Berlin, 1992.

Digital Library

[11]

Kaltofen E., Effective Hilbert Irreducibility Information and Control, 66, 123-137 (1985).

[12]

Mumford D. Introduction to Algebraic Geometry, Cambridge Mass., Harvard University, 1955.

[13]

PARI-GP http://www.parigp-home.de/

[14]

Ostrowski A. M. Solution of equations and systems of equations, New York, Academic Press, 1960.

[15]

Ragot, J. F. Sur la factorisation absolue des polynomes, PhD Thesis, Univ. Limoges, (1997).

[16]

Ruppecht, D. Semi-numerical absolute factorization of polynomials with integer coefficients To appear in Journal of Symb. Comp. (2001).

[17]

Ruppecht, D. Elements pour un calcul approche et certifie : etude du PGCD et de la factorisation PhD thesis, University of Nice, France, (2000), http://www-math.unice.fr/~rupprech

[18]

Sasaki T. Suzuki M. Kolar M. Sasaki M. Approximate factorization of multivariate polynomials and absolute irreducibility testing. Japan J. Indust. Appl. Math. 8 (1991), no. 3, pp. 357-375.

[19]

Sasaki T. Approximate Multivariate Polynomial Factorization Based on Zero-Sum Relations Proc. Intern. Symp. on Symbolic and Algebraic Computation, 284-291, ACM Press (2001).

Digital Library

[20]

Shampine L. F. Corless R. M. Initial Value Problems for ODEs in Problem Solving Environments J. Comp. & App. Math. (2000) 125, pp. 31-40

Digital Library

[21]

Sommese A. J. Verschelde J. and Wampler C. W. Using Monodromy to Decompose Solution Sets of Polynomial Systems into Irreducible Components Proc. of a NATO Conference in Eilat Israel, "Application of Algebraic Geometry to Coding Theory, Physics and Computation", pp. 297-315, Kluwer Academic Publishers, (2001).

[22]

Sommese A. J. Verschelde J. and Wampler C. W. Symmetric functions applied to decomposing solution sets of polynomial systems preprint, november 2001.

[23]

Sommese A. J., Verschelde J. and Wampler C. W. Functions Applied to Decomposing Solution Sets of Polynomial Systems, (2001), preprint available from http://www.math.uic.edu/~jan.

[24]

Sommese A. J., Verschelde J. and Wampler C. W. Numerical decomposition of the solution sets of polynomial systems into irreducible components, SIAM Journal on Numerical Analysis, 38 (2001), 2022-2046.

Digital Library

[25]

J. von zur Gathen and J. Gerhard Modern Computer Algebra Cambridge University Press, (1999).

Digital Library

[26]

Walker R. J. Algebraic curves, Princeton University Press, 1950. Princeton mathematical series ; vol 13.

[27]

Zippel, R. E. Effective polynomial computation Boston, Kluwer Academic Publishers, Kluwer international series in engineering and computer science vol 241 (1993)

Cited By

严杰(2020)The Verification of Approximate Polynomial FactorizationAdvances in Applied Mathematics10.12677/AAM.2020.9814409:08(1230-1238)Online publication date: 2020
https://doi.org/10.12677/AAM.2020.98144
Alcazar JGoldman R(2016)Finding the Axis of Revolution of an Algebraic Surface of RevolutionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2015.249860222:9(2082-2093)Online publication date: 1-Sep-2016
https://doi.org/10.1109/TVCG.2015.2498602
Alcázar JHermoso CMuntingh G(2015)Symmetry detection of rational space curves from their curvature and torsionComputer Aided Geometric Design10.1016/j.cagd.2015.01.00333:C(51-65)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.cagd.2015.01.003
Show More Cited By

Index Terms

A geometric-numeric algorithm for absolute factorization of multivariate polynomials

Recommendations

Factorization of multivariate positive Laurent polynomials

Recently Dritschel proved that any positive multivariate Laurent polynomial can be factorized into a sum of square magnitudes of polynomials. We first give another proof of the Dritschel theorem. Our proof is based on the univariate matrix Fejer-Riesz ...
Factorization formulas for Macdonald polynomials

The aim of this note is to give some factorization formulas for different versions of the Macdonald polynomials when the parameter t is specialized at roots of unity, generalizing those given in [A. Lascoux, B. Leclerc, J.-Y. Thibon, Green polynomials ...
Properties of Multivariate Homogeneous Orthogonal Polynomials

It is well-known that the denominators of Pade approximants can be considered as orthogonal polynomials with respect to a linear functional. This is usually shown by defining Pade-type approximants from so-called generating polynomials and then ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '02: Proceedings of the 2002 international symposium on Symbolic and algebraic computation

July 2002

296 pages

ISBN:1581134843

DOI:10.1145/780506

Conference Chair:
Marc Giusti
CNRS-Ecole Polytechnique, France

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 July 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC02

Sponsor:

SIGSAM

ISSAC02: International Symposium on Symbolic and Algebraic Computation

July 7 - 10, 2002

Lille, France

Acceptance Rates

ISSAC '02 Paper Acceptance Rate 35 of 86 submissions, 41%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
151
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

严杰(2020)The Verification of Approximate Polynomial FactorizationAdvances in Applied Mathematics10.12677/AAM.2020.9814409:08(1230-1238)Online publication date: 2020
https://doi.org/10.12677/AAM.2020.98144
Alcazar JGoldman R(2016)Finding the Axis of Revolution of an Algebraic Surface of RevolutionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2015.249860222:9(2082-2093)Online publication date: 1-Sep-2016
https://doi.org/10.1109/TVCG.2015.2498602
Alcázar JHermoso CMuntingh G(2015)Symmetry detection of rational space curves from their curvature and torsionComputer Aided Geometric Design10.1016/j.cagd.2015.01.00333:C(51-65)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.cagd.2015.01.003
Wu WZeng Z(2015)The Numerical Factorization of PolynomialsFoundations of Computational Mathematics10.1007/s10208-015-9289-117:1(259-286)Online publication date: 19-Nov-2015
https://doi.org/10.1007/s10208-015-9289-1
Luo GPei G(2015)A Novel Multivariate Polynomial Approximation Factorization of Big DataIntelligent Computation in Big Data Era10.1007/978-3-662-46248-5_61(484-496)Online publication date: 2015
https://doi.org/10.1007/978-3-662-46248-5_61
Adrovic DVerschelde J(2011)Tropical algebraic geometry in MapleJournal of Symbolic Computation10.1016/j.jsc.2010.08.01146:7(755-772)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1016/j.jsc.2010.08.011
Verschelde JYoffe G(2010)Polynomial homotopies on multicore workstationsProceedings of the 4th International Workshop on Parallel and Symbolic Computation10.1145/1837210.1837230(131-140)Online publication date: 21-Jul-2010
https://dl.acm.org/doi/10.1145/1837210.1837230
Lichtblau D(2010)Polynomial GCD and Factorization via Approximate Gröbner BasesProceedings of the 2010 12th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing10.1109/SYNASC.2010.76(29-36)Online publication date: 23-Sep-2010
https://dl.acm.org/doi/10.1109/SYNASC.2010.76
Leykin AVerschelde J(2009)Decomposing solution sets of polynomial systems: a new parallel monodromy breakup algorithmInternational Journal of Computational Science and Engineering10.1504/IJCSE.2009.0270014:2(94-101)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1504/IJCSE.2009.027001
Qin XFeng YChen JZhang JSasaki TShirayanagi KKotsireas I(2009)Finding exact minimal polynomial by approximationsProceedings of the 2009 conference on Symbolic numeric computation10.1145/1577190.1577211(125-132)Online publication date: 3-Aug-2009
https://dl.acm.org/doi/10.1145/1577190.1577211
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten