Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleSolving parametric polynomial systems
Author(s) Daniel Lazard, Fabrice Rouillier
TypeArticle in Journal
AbstractWe present a new algorithm for solving basic parametric constructible or semi-algebraic systems of the form C = x ∈ C n , p 1 ( x ) = 0 , … , p s ( x ) = 0 , f 1 ( x ) ≠ 0 , … , f l ( x ) ≠ 0 or S = x ∈ R n , p 1 ( x ) = 0 , … , p s ( x ) = 0 , f 1 ( x ) > 0 , … , f l ( x ) > 0 , where p i , f i ∈ Q [ U , X ] , U = [ U 1 , … , U d ] is the set of parameters and X = [ X d + 1 , … , X n ] the set of unknowns. If Π U denotes the canonical projection onto the parameter’s space, solving C or S is reduced to the computation of submanifolds U ⊂ C d or U ⊂ R d such that ( Π U − 1 ( U ) ∩ C , Π U ) is an analytic covering of U (we say that U has the ( Π U , C ) -covering property). This guarantees that the cardinality of Π U − 1 ( u ) ∩ C is constant on a neighborhood of u , that Π U − 1 ( U ) ∩ C is a finite collection of sheets and that Π U is a local diffeomorphism from each of these sheets onto U . We show that the complement in Π U ( C ) ¯ (the closure of Π U ( C ) for the usual topology of C n ) of the union of all the open subsets of Π U ( C ) ¯ which have the ( Π U , C )-covering property is a Zariski closed set which is called the minimal discriminant variety of C w.r.t. Π U , denoted as W D . We propose an algorithm to compute W D efficiently. The variety W D can then be used to solve the parametric system C (resp. S ) as long as one can describe Π U ( C ) ¯ ∖ W D (resp. R d ∩ ( Π U ( C ) ¯ ∖ W D ) ). This can be done by using the critical points method or an “open” cylindrical algebraic decomposition.
KeywordsComputer algebra, Parametric polynomial system, Polynomial system, Solving, Discriminant variety, Algorithms, Semi-algebraic set, Constructible set
ISSN0747-7171
URL http://www.sciencedirect.com/science/article/pii/S0747717107000132
LanguageEnglish
JournalJournal of Symbolic Computation
Volume42
Number6
Pages636 - 667
Year2007
Edition0
Translation No
Refereed No
Webmaster