[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3452143.3465536acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
research-article

Comprehensive Characteristic Decomposition of Parametric Polynomial Systems

Published: 18 July 2021 Publication History

Abstract

This paper presents an algorithm that decomposes an arbitrary set F of multivariate polynomials involving parameters into finitely many sets Γi of (lexicographical) Gröbner bases G ij such that associated with each Γi there is a system Ai of parametric constraints, all the Ai's partition the parameter space, all the Gij's in each Γi remain Gröbner bases under specialization of the parameters satisfying the constraints in Ai, and for each i the Gröbner bases Gij together with their corresponding W-characteristic sets form a normal characteristic decomposition of F. The sets of Gröbner bases computed by the algorithm provide a comprehensive characteristic decomposition of F that is structure-invariant under the associated constraints and possesses many algebraic and geometric properties, including most of the notable properties on comprehensive Gröbner systems and comprehensive triangular decomposition. Some of these properties are highlighted in the paper and advantages of the proposed algorithm are discussed briefly from the aspects of methodological simplicity and computational performance using illustrative examples and preliminary experiments.

References

[1]
P. Aubry. 1999. Ensembles Triangulaires de Polynômes et Résolution de Systemes Algébriques. Implantation en Axiom. Ph.D. Dissertation. Université Pierre et Marie Curie, France.
[2]
P. Aubry, D. Lazard, and M. Moreno Maza. 1999. On the theories of triangular sets. J. Symbolic Comput., Vol. 28, 1--2 (1999), 105--124.
[3]
T. Bächler. 2014. Counting Solutions of Algebraic Systems via Triangular Decomposition. Ph.D. Dissertation. RWTH Aachen University, Germany.
[4]
T. Bächler, V. Gerdt, M. Lange-Hegermann, and D. Robertz. 2012. Algorithmic Thomas decomposition of algebraic and differential systems. J. Symbolic Comput., Vol. 47, 10 (2012), 1233--1266.
[5]
T. Becker, V. Weispfenning, and H. Kredel. 1993. Gröbner Bases: A Computational Approach to Commutative Algebra. Springer, New York.
[6]
B. Buchberger. 1965. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal. Ph.D. Dissertation. Universität Innsbruck, Austria.
[7]
C. Chen, J. Davenport, J. May, M. Moreno Maza, B. Xia, and R. Xiao. 2013. Triangular decomposition of semi-algebraic systems. J. Symbolic Comput., Vol. 49 (2013), 3--26.
[8]
C. Chen, O. Golubitsky, F. Lemaire, M. Moreno Maza, and W. Pan. 2007. Comprehensive triangular decomposition. In Proceedings of CASC 2007. Springer-Verlag, Berlin Heidelberg, 73--101.
[9]
C. Chen and M. Moreno Maza. 2012. Algorithms for computing triangular decompositions of polynomial systems. J. Symbolic Comput., Vol. 47, 6 (2012), 610--642.
[10]
S.-C. Chou and X.-S. Gao. 1990. Ritt-Wu's decomposition algorithm and geometry theorem proving. In Proceedings of CADE-10. Springer-Verlag, Berlin Heidelberg, 207--220.
[11]
D. Cox, J. Little, and D. O'Shea. 1997. Ideals, Varieties, and Algorithms. Springer, New York.
[12]
R. Dong and C. Mou. 2019. On characteristic decomposition and quasi-characteristic decomposition. In Proceedings of CASC 2019. Springer, 122--139.
[13]
R. Dong and D. Wang. 2021. Computing strong regular characteristic pairs with Gröbner bases. J. Symbolic Comput., Vol. 104 (2021), 312--327.
[14]
J.-C. Faugère. 1999. A new efficient algorithm for computing Gröbner bases (F 4). J. Pure Appl. Algebra, Vol. 139, 1--3 (1999), 61--88.
[15]
X.-S. Gao and S.-C. Chou. 1992. Solving parametric algebraic systems. In Proceedings of ISSAC 1992. ACM Press, 335--341.
[16]
P. Gianni, B. Trager, and G. Zacharias. 1988. Gröbner bases and primary decomposition of polynomial ideals. J. Symbolic Comput., Vol. 6, 2 (1988), 149--167.
[17]
E. Hubert. 2003. Notes on triangular sets and triangulation-decomposition algorithms I: Polynomial systems. In Symbolic and Numerical Scientific Computation. Springer-Verlag, Berlin Heidelberg, 143--158.
[18]
D. Kapur. 1995. An approach for solving systems of parametric polynomial equations. In Principles and Practice of Constraint Programming. MIT Press, 217--224.
[19]
D. Kapur, Y. Sun, and D. Wang. 2010. A new algorithm for computing comprehensive Gröbner systems. In Proceedings of ISSAC 2010. ACM Press, 29--36.
[20]
D. Kapur, Y. Sun, and D. Wang. 2013. An efficient algorithm for computing a comprehensive Gröbner system of a parametric polynomial system. J. Symbolic Comput., Vol. 49 (2013), 27--44.
[21]
D. Lazard and F. Rouillier. 2007. Solving parametric polynomial systems. J. Symbolic Comput., Vol. 42, 6 (2007), 636--667.
[22]
M. Manubens and A. Montes. 2009. Minimal canonical comprehensive Gröbner systems. J. Symbolic Comput., Vol. 44, 5 (2009), 463--478.
[23]
A. Montes. 2002. A new algorithm for discussing grobner bases with parameters. J. Symbolic Comput., Vol. 33, 2 (2002), 183--208.
[24]
M. Moreno Maza, B. Xia, and R. Xiao. 2012. On solving parametric polynomial systems. Math. Comput. Sci., Vol. 6, 4 (2012), 457--473.
[25]
C. Mou, D. Wang, and X. Li. 2013. Decomposing polynomial sets into simple sets over finite fields: The positive-dimensional case. Theoret. Comput. Sci., Vol. 468 (2013), 102--113.
[26]
K. Nabeshima. 2007. A speed-up of the algorithm for computing comprehensive Gröbner systems. In Proceedings of ISSAC 2007. ACM Press, 299--306.
[27]
J. F. Ritt. 1932. Differential Equations from the Algebraic Standpoint. American Mathematical Society, New York.
[28]
A. Suzuki and Y. Sato. 2003. An alternative approach to comprehensive Gröbner bases. J. Symbolic Comput., Vol. 36, 3--4 (2003), 649--667.
[29]
A. Suzuki and Y. Sato. 2006. A simple algorithm to compute comprehensive Gröbner bases using Gröbner bases. In Proceedings of ISSAC 2006. ACM Press, 326--331.
[30]
D. Wang. 1998. Decomposing polynomial systems into simple systems. J. Symbolic Comput., Vol. 25, 3 (1998), 295--314.
[31]
D. Wang. 2000. Computing triangular systems and regular systems. J. Symbolic Comput., Vol. 30, 2 (2000), 221--236.
[32]
D. Wang. 2001. Elimination Methods. Springer-Verlag, Wien.
[33]
D. Wang. 2005. The projection property of regular systems and its application to solving parametric polynomial systems. In Proceedings of A3L 2005. Herstellung und Verlag, 269--274.
[34]
D. Wang. 2016. On the connection between Ritt characteristic sets and Buchberger-Gröbner bases. Math. Comput. Sci., Vol. 10, 4 (2016), 479--492.
[35]
D. Wang, R. Dong, and C. Mou. 2020. Decomposition of polynomial sets into characteristic pairs. Math. Comp., Vol. 89, 324 (2020), 1993--2015.
[36]
V. Weispfenning. 1992. Comprehensive Gröbner bases. J. Symbolic Comput., Vol. 14, 1 (1992), 1--29.
[37]
M. Wibmer. 2007. Gröbner bases for families of affine or projective schemes. J. Symbolic Comput., Vol. 42, 8 (2007), 803--834.
[38]
W.-T. Wu. 1986. On zeros of algebraic equations: An application of Ritt principle. Kexue Tongbao, Vol. 31, 1 (1986), 1--5.
[39]
W.-T. Wu. 1994. Mechanical Theorem Proving in Geometries: Basic Principles. Springer-Verlag, Wien. Translated from the Chinese by X. Jin and D. Wang.
[40]
L. Yang, X. Hou, and B. Xia. 1998. Automated discovering and proving for geometric inequalities. In Proceedings of ADG 1998. Springer, 30--46.

Cited By

View all
  • (2023)A Modular Algorithm for Computing the Intersection of a One-Dimensional Quasi-Component and a HypersurfaceComputer Algebra in Scientific Computing10.1007/978-3-031-41724-5_4(69-89)Online publication date: 28-Aug-2023

Index Terms

  1. Comprehensive Characteristic Decomposition of Parametric Polynomial Systems

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ISSAC '21: Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation
    July 2021
    379 pages
    ISBN:9781450383820
    DOI:10.1145/3452143
    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

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 18 July 2021

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. comprehensive characteristic decomposition
    2. gr"{o}bner basis
    3. parametric polynomial system
    4. triangular decomposition

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    ISSAC '21
    Sponsor:
    ISSAC '21: International Symposium on Symbolic and Algebraic Computation
    July 18 - 23, 2021
    Virtual Event, Russian Federation

    Acceptance Rates

    Overall Acceptance Rate 395 of 838 submissions, 47%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)13
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 04 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)A Modular Algorithm for Computing the Intersection of a One-Dimensional Quasi-Component and a HypersurfaceComputer Algebra in Scientific Computing10.1007/978-3-031-41724-5_4(69-89)Online publication date: 28-Aug-2023

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media