zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Solving parametric piecewise polynomial systems. (English) Zbl 1251.65075

This paper establishes the basic theory on piecewise polynomial functions that are C r with different smoothness degree r over the whole domain, and presents the theory and methods for solving zero-dimensional parametric piecewise polynomial systems. It shows that solving such a system amounts to solving m parametric semi-algebraic systems, which is then reduced to the computation of m discriminant varieties. Here, m is the number of n-dimensional cells in the hereditary partition of the domain. The parametric piecewise polynomial system is ultimately solved utilizing the critical points method and the Collins partial cylindrical algebraic decomposition method.

The paper also proposes a classification method and its algorithm to address whether there exists an open set in the parameter domain such that, for each point in the open set, the corresponding zero-dimensional non-parametric piecewise polynomial system (a realization of the parametric piecewise polynomial system) has exactly the given number of torsion-free real zeros in the m cells respectively.

MSC:
65H10Systems of nonlinear equations (numerical methods)
14Q10Computational aspects of algebraic surfaces and hypersurfaces
65H05Single nonlinear equations (numerical methods)
13P15Solving polynomial systems; resultants
References:
[1]Bochnak, Jacek; Coste, Michel; Roy, Marie-Francoise: Real algebraic geometry, (1998)
[2]S. Basu, R. Pollack, M.F. Roy, Algorithms in Real Algebraic Geometry, Hardcover, 2006.
[3]Cox, D.; Little, J.; O’shea, D.: Using algebraic geometry, (1998)
[4]Lai, Y. S.; Wang, R. H.; Wu, J. M.: Real zeros of the zero-dimensional parametric piecewise algebraic variety, Sci. China ser. A: math. 52, No. 4, 817-832 (2009) · Zbl 1177.14096 · doi:10.1007/s11425-008-0141-9
[5]Wang, R. H.; Lai, Y. S.: Real piecewise algebraic variety, J. comput. Math. 21, No. 4, 473-480 (2003) · Zbl 1080.14547
[6]Wang, R. H.; Shi, X. Q.; Luo, Z. X.; Su, Z. X.: Multivariate spline and its applications, (2001)
[7]Lai, Y. S.; Wang, R. H.: The nöther and Riemann–Roch type theorems for piecewise algebraic curve, Sci. China ser. A: math. 2, 165-182 (2007) · Zbl 1115.14054 · doi:10.1007/s11425-007-0003-x
[8]Wang, R. H.: The structural characterization and interpolation for multivariate spline, Acta math. Sinica 18, 91-106 (1975) · Zbl 0358.41004
[9]Lu, Yang; Xiaorong, Hou; Xia, B. C.: A complete algorithm for automated discovering of a class of inequality-type theorems, Sci. China ser. F 44, No. 1, 33-49 (2001) · Zbl 1125.68406 · doi:10.1007/BF02713938
[10]Xia, B. C.; Lu, Yang: An algorithm for isolating the real solutions of semi-algebraic systems, J. symbolic comput. 34, 461-477 (2002) · Zbl 1027.68150 · doi:10.1006/jsco.2002.0572
[11]Collins, G. E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Lecture notes in computer science 33 (1975) · Zbl 0318.02051
[12]Collins, G. E.; Hong, H.: Partial cylindrical algebraic decomposition for quantifier elimination, J. symbolic comput. 12, 299-328 (1991) · Zbl 0754.68063 · doi:10.1016/S0747-7171(08)80152-6
[13]Brown, C. W.: Simple CAD construction and its applications, J. symbolic comput. 31, 521-547 (2001) · Zbl 0976.65023 · doi:10.1006/jsco.2000.0394
[14]Lazard, D.; Rouillier, F.: Solving parametric polynomial systems, J. symbolic comput. 42, No. 6, 636-667 (2007) · Zbl 1156.14044 · doi:10.1016/j.jsc.2007.01.007
[15]J.-C. Faugere, G. Moroz, F. Rouillier, M.Safey El Din, Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities, in: D. Jeffrey (Eds), ISSAC 2008 Proceedings, Austria, Hagenberg, 2008.
[16]M.Safey EI Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth real algebraic set, in: J.R. Sendra (Ed.), International Symposium on Symbolic and Algebraic Computation 2003, ISSAC’2003, Philadelphia, USA, ACM Press, 2003, pp. 224–231. · Zbl 1072.68693
[17]Din, M. Safey Ei; Schost, E.: Properness defects of projection functions and computation of at least one point in each connected component of a real algebraic set, Discrete comput. Geom. 32, No. 3, 417-430 (2004) · Zbl 1067.14057 · doi:10.1007/s00454-004-1107-5
[18]Corvez, S.; Rouillier, F.: Using computer algebraic tools to classify serial manipulators, Lecture notes in artificial intelligence 2930, 31-43 (2003) · Zbl 1202.68489 · doi:10.1007/b95516
[19]Hartshorne, Robin: Algebraic geometry, (1977)
[20]Wang, D. M.: Computing triangular systems and regular systems, J. symbolic comput. 30, 221-236 (2000) · Zbl 1007.65039 · doi:10.1006/jsco.1999.0355
[21]Wang, D. M.: Elimination methods, (2001)
[22]S. Liang, J. Gerhard, D. Jeffrey, A new maple package for solving parametric polynomial systems, in: MACIS, 2007.
[23]Xia, B. C.: Discoverer: a tool for solving semi-algebraic systems, ACM SIGSAM bull. 41, No. 3, 102-103 (2007)
[24]Xia, B. C.; Hou, X. R.: A complete algorithm for counting real solutions of polynomial systems of equations and inequalities, Comput. math. Appl. 44, 633-642 (2002) · Zbl 1035.65054 · doi:10.1016/S0898-1221(02)00178-5