×

zbMATH — the first resource for mathematics

Generic regular decompositions for generic zero-dimensional systems. (English) Zbl 1423.68617
Summary: Two new concepts, generic regular decomposition and regular-decomposition-unstable (RDU) variety for generic zero-dimensional systems, are introduced in this paper and an algorithm is proposed for computing a generic regular decomposition and the associated RDU variety of a given generic zero-dimensional system simultaneously. The solutions of the given system can be expressed by finitely many zero-dimensional regular chains if the parameter value is not on the RDU variety. The so called weakly relatively simplicial decomposition plays a crucial role in the algorithm, which is based on the theories of subresultants. Furthermore, the algorithm can be naturally adopted to compute a non-redundant Wu’s decomposition and the decomposition is stable at any parameter value that is not on the RDU variety. The algorithm has been implemented with Maple 16 and experimented with a number of benchmarks from the literature. Empirical results are also presented to show the good performance of the algorithm.
MSC:
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
65H10 Numerical computation of solutions to systems of equations
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chen, C.; Golubitsky, O.; Lemaire, F.; etal., Comprehensive triangular decomposition, 73-101 (2007) · Zbl 1141.68677
[2] Montes, A.; Recio, T., Automatic discovery of geometry theorems using minimal canonical comprehensive Gröbner systems, 113-138 (2007) · Zbl 1195.68093
[3] Weispfenning V. Comprehensive Gröbner bases. J Symb Comput, 1992, 14: 1-29 · Zbl 0784.13013
[4] Kapur, D.; Sun, Y.; Wang, D., A new algorithm for computing comprehensive Gröbner systems, 29-36 (2010) · Zbl 1321.68533
[5] Nabeshima, K., A speed-up of the algorithm for computing comprehensive Gröbner systems, 299-306 (2007) · Zbl 1190.13025
[6] Aubry P, Lazard D, Moreno Maza M. On the theories of triangular sets. J Symb Comput, 1999, 28: 105-124 · Zbl 0943.12003
[7] Gao, X-S; Chou, S-C, Solving parametric algebraic systems, 335-341 (1992) · Zbl 0925.13014
[8] Kalkbrener M. A generalized Euclidean algorithm for computing triangular representationa of algebraic varieties. J Symb Comput, 1993, 15: 143-167 · Zbl 0783.14039
[9] Moreno Maza M. On triangular decompositions of algebraic varieties. Technical Report TR 4/99, NAG Ltd. 1999
[10] Wang, D. K., Zero decomposition algorithms for system of polynomial equations, 67-70 (2000) · Zbl 0981.65063
[11] Wang D M. Computing triangular systems and regular systems. J Symb Comput, 2000, 30: 221-236 · Zbl 1007.65039
[12] Wu W T. Basic principles of mechanical theorem proving in elementary geometries. J Syst Sci Math Sci, 1984, 4: 207-235
[13] Yang L, Hou X, Xia B. A complete algorithm for automated discovering of a class of inequality-type theorems. SCI China Ser F-Inf Sci, 2001, 44: 33-49 · Zbl 1125.68406
[14] Yang L, Xia B. Automated Proving and Discovering Inequalities (in Chinese). Beijing: Science Press, 2008. 11-22
[15] Yang L, Zhang J. Searching dependency between algebraic equations: an algorithm applied to automated reasoning. Technical Report ICTP/91/6. 1991
[16] Yang, L.; Xia, B., Real solution classifications of a class of parameteric semi-algebraic systems, 281-289 (2005)
[17] Suzuki, A.; Sato, Y., An alternative approach to comprehensive Gröbner bases, 255-261 (2002) · Zbl 1072.68699
[18] Suzuki, A.; Sato, Y., A simple algorithm to compute comprehensive Gröbner bases using Gröbner bases, 326-331 (2006) · Zbl 1356.13040
[19] Gao X-S, Hou X, Tang J, et al. Complete solution classification for the perspective-three-point problem. IEEE Trans Pami, 2003, 25: 930-943
[20] Wang D M. Elimination Methods. New York: Springer, 2001. 45-51 · Zbl 0964.13014
[21] Wang D M. Elimination Practice: Software Tools and Applications. London: Imperial College Press, 2004. 82-97
[22] Xia B. DISCOVERER: a tool for solving semi-algebraic systems. ACM Commun Comput Algebra, 2007, 41: 102-103
[23] Cox D, Little J, O’Shea D. Using Algebraic Geometry. New York: Springer, 1998. 1-26 · Zbl 0920.13026
[24] Yang, L.; Zhang, J.; Hou, X., A criterion of dependency between algebraic equations and its applications, 110-134 (1992)
[25] Chen C. Solving polynomial systems via triangular decomposition. Dissertation for the Doctoral Degree. London: Universite of Western Ontario, 2011. 31-94
[26] Yang L, Zhang J, Hou X. Non-linear Algebraic Equalities and Automated Proving (in Chinese). Shanghai: Shanghai Technology Education Press, 1996. 57-68
[27] Mishra B. Algorithmic Algebra. New York: Springer-Verlag, 1993. 250-284 · Zbl 0804.13009
[28] Kahoui M E. An elementary approach to subresultants theory. J Symb Comput, 2003, 35: 281-292 · Zbl 1054.13014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.