A Hybrid Procedure for Finding Real Points on a Real Algebraic Set
|
摘要
Motivated by the idea of Shen, et al.'s work, which proposed a hybrid procedure for real root isolation of polynomial equations based on homotopy continuation methods and interval analysis,this paper presents a hybrid procedure to compute sample points on each connected component of a real algebraic set by combining a special homotopy method and interval analysis with a better estimate on initial intervals. For a real algebraic set given by a polynomial system, the new method ?rst constructs a square polynomial system which represents the sample points, and then solve this system by a special homotopy continuation method introduced recently by Wang, et al.(2017). For each root returned by the homotopy continuation method, which is a complex approximation of some(complex/real) root of the polynomial system, interval analysis is used to verify whether it is an approximation of a real root and ?nally get real points on the given real algebraic set. A new estimate on initial intervals is presented which helps compute smaller initial intervals before performing interval iteration and thus saves computation. Experiments show that the new method works pretty well on tested examples.
Motivated by the idea of Shen, et al.'s work, which proposed a hybrid procedure for real root isolation of polynomial equations based on homotopy continuation methods and interval analysis,this paper presents a hybrid procedure to compute sample points on each connected component of a real algebraic set by combining a special homotopy method and interval analysis with a better estimate on initial intervals. For a real algebraic set given by a polynomial system, the new method ?rst constructs a square polynomial system which represents the sample points, and then solve this system by a special homotopy continuation method introduced recently by Wang, et al.(2017). For each root returned by the homotopy continuation method, which is a complex approximation of some(complex/real) root of the polynomial system, interval analysis is used to verify whether it is an approximation of a real root and ?nally get real points on the given real algebraic set. A new estimate on initial intervals is presented which helps compute smaller initial intervals before performing interval iteration and thus saves computation. Experiments show that the new method works pretty well on tested examples.
Motivated by the idea of Shen, et al.'s work, which proposed a hybrid procedure for real root isolation of polynomial equations based on homotopy continuation methods and interval analysis,this paper presents a hybrid procedure to compute sample points on each connected component of a real algebraic set by combining a special homotopy method and interval analysis with a better estimate on initial intervals. For a real algebraic set given by a polynomial system, the new method ?rst constructs a square polynomial system which represents the sample points, and then solve this system by a special homotopy continuation method introduced recently by Wang, et al.(2017). For each root returned by the homotopy continuation method, which is a complex approximation of some(complex/real) root of the polynomial system, interval analysis is used to verify whether it is an approximation of a real root and ?nally get real points on the given real algebraic set. A new estimate on initial intervals is presented which helps compute smaller initial intervals before performing interval iteration and thus saves computation. Experiments show that the new method works pretty well on tested examples.
引文
[1]Collins G,Quantifier elimination for real closed fields by cylindrical algebraic decompostion,Automata Theory and Formal Languages,LNCS 33,Springer,1975,134-183.
[2]Seidenberg A,A new decision method for elementary algebra,Annals of Mathematics,1954,60:365-374.
[3]Safey El Din M and Schost E,Polar varieties and computation of one point in each connected component of a smooth real algebraic set,Proc.ISSAC’03,Philadelphia,2003,224-231.
[4]Safey El Din M and Spaenlehauer P J,Critical point computations on smooth varieties:Degree and complexity bounds,Proc.ISSAC’16,New York,2016,183-190.
[5]Bank B,Giusti M,Heintz J,et al.,Generalized polar varieties and an efficient real elimination,Kybernetika,2004,40:519-550.
[6]Bank B,Giusti M,Heintz J,et al.,Generalized polar varieties:Geometry and algorithms,Journal of Complexity,2005,21:377-412.
[7]Rouillier F,Roy M F,and Safey El Din M,Finding at least one point in each connected component of a real algebraic set defined by a single equation,Journal of Complexity,2000,16:716-750.
[8]Safey El,Din M,and Schost E,Properness defects of projections and computation of at leastone point in each connected component of a real algebraic set,Discrete&Computational Geometry,2004,32:417-430.
[9]Li T Y and Wang X,Solving real polynomial systems with real homotopies,Mathematics of Computation,1993,60:669-680.
[10]Brake D A,Hauenstein J D,and Liddell A C,Numerically validating the completeness of the real solution set of a system of polynomial equations,ar Xiv:1602.00700v1,2016.
[11]Cifuentes D and Parrilo P A,Sampling algebraic varieties for sum of squares programs,SIAMJournal on Optimization,2015,27:2381-2404.
[12]Lu Y,Bates D J,Sommese A J,et al.,Finding all real points of a complex curve,Algebra,Geometry and Their Interactions,2006.
[13]Bates D J and Sottile F,Khovanskii-rolle continuation for real solutions,Found.Comput.Math.,2011,11(5):563-587.
[14]Besana G M,Rocco S,Hauenstein J D,et al.,Cell decomposition of almost smooth real algebraic surfaces,Numer.Algorithms,2013,63:1017-1398.
[15]Hauenstein J D,Numerically computing real points on algebraic sets,Acta Applicandae Mathematicae,2013,125:105-119.
[16]Wu W and Reid G,Finding points on real solution components and applications to differential polynomial systems,Proc.ISSAC’13,Boston,2013,339-346.
[17]Wang Y,Wu W,and Xia B,Early ending in homotopy path-tracking for real roots,Artificial Intelligence and Symbolic Computation,LNCS 11110,Eds.by Fleuriot J,Wang D,and Calmet J,Suzhou,2018,181-194.
[18]Shen F,Wu W,and Xia B,Real root isolation of polynomial equations based on hybrid computation,Computer Mathematics:9th Asian Symposium(ASCM2009),Eds.by Feng R,Lee W S,and Sato Y,Beijing,2014,375-396.
[19]John F,Extremum problems with inequalities as subsidiary conditions,Traces and Emergence of Nonlinear Programming,Eds.by Giorgi G and Kjeldsen T,Springer Basel,2014,197-215.
[20]Sommese A J,Verschelde J,and Wampler C W,Numerical algebraic geometry,The Mathematics of Numerical Analysis,volume 32 of Lectures in Applied Mathematics,AMS,1996,749-763.
[21]Morgan A P and Sommese A J,Coefficient-parameter polynomial continuation,Applied Mathematics and Computation,1989,29:123-160.
[22]Li T Y,Numerical solution of multivariate polynomial systems by homotopy continuation methods,Acta Numerica,1997,6:399-436.
[23]Wang Y,Wu W,and Xia B,A special homotopy continuation method for a class of polynomial systems,Computer Algebra in Scientific Computing,Eds.by Gerdt V P,Koepf W,Seiler W M,et al.,Springer,2017,362-376.
[24]Bernshtein D N,The number of roots of a system of equations,Functional Analysis and Its Applications,1975,9:183-185.
[25]Moore R E,Methods and Application of Interval Analysis,Philadelphia,SIAM,1995.
[26]Krawczyk R,Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken,Computing,1969,4:187-201.
[27]Moore R E and Jones S T,Safe starting regions for iterative methods,SIAM Journal on Numerical Analysis,1977,14:1051-1065.
[28]Kantorovich L V,On Newton’s method for functional equations,Dokl.Akad.Nauk SSSR,1948,59:1237-1240.
[29]Rump S M,INTLAB-INTerval LABoratory,Developments in Reliable Computing,Ed.by Csendes T,Kluwer Academic Publishers,Dordrecht,1999,77-104.
[2]Seidenberg A,A new decision method for elementary algebra,Annals of Mathematics,1954,60:365-374.
[3]Safey El Din M and Schost E,Polar varieties and computation of one point in each connected component of a smooth real algebraic set,Proc.ISSAC’03,Philadelphia,2003,224-231.
[4]Safey El Din M and Spaenlehauer P J,Critical point computations on smooth varieties:Degree and complexity bounds,Proc.ISSAC’16,New York,2016,183-190.
[5]Bank B,Giusti M,Heintz J,et al.,Generalized polar varieties and an efficient real elimination,Kybernetika,2004,40:519-550.
[6]Bank B,Giusti M,Heintz J,et al.,Generalized polar varieties:Geometry and algorithms,Journal of Complexity,2005,21:377-412.
[7]Rouillier F,Roy M F,and Safey El Din M,Finding at least one point in each connected component of a real algebraic set defined by a single equation,Journal of Complexity,2000,16:716-750.
[8]Safey El,Din M,and Schost E,Properness defects of projections and computation of at leastone point in each connected component of a real algebraic set,Discrete&Computational Geometry,2004,32:417-430.
[9]Li T Y and Wang X,Solving real polynomial systems with real homotopies,Mathematics of Computation,1993,60:669-680.
[10]Brake D A,Hauenstein J D,and Liddell A C,Numerically validating the completeness of the real solution set of a system of polynomial equations,ar Xiv:1602.00700v1,2016.
[11]Cifuentes D and Parrilo P A,Sampling algebraic varieties for sum of squares programs,SIAMJournal on Optimization,2015,27:2381-2404.
[12]Lu Y,Bates D J,Sommese A J,et al.,Finding all real points of a complex curve,Algebra,Geometry and Their Interactions,2006.
[13]Bates D J and Sottile F,Khovanskii-rolle continuation for real solutions,Found.Comput.Math.,2011,11(5):563-587.
[14]Besana G M,Rocco S,Hauenstein J D,et al.,Cell decomposition of almost smooth real algebraic surfaces,Numer.Algorithms,2013,63:1017-1398.
[15]Hauenstein J D,Numerically computing real points on algebraic sets,Acta Applicandae Mathematicae,2013,125:105-119.
[16]Wu W and Reid G,Finding points on real solution components and applications to differential polynomial systems,Proc.ISSAC’13,Boston,2013,339-346.
[17]Wang Y,Wu W,and Xia B,Early ending in homotopy path-tracking for real roots,Artificial Intelligence and Symbolic Computation,LNCS 11110,Eds.by Fleuriot J,Wang D,and Calmet J,Suzhou,2018,181-194.
[18]Shen F,Wu W,and Xia B,Real root isolation of polynomial equations based on hybrid computation,Computer Mathematics:9th Asian Symposium(ASCM2009),Eds.by Feng R,Lee W S,and Sato Y,Beijing,2014,375-396.
[19]John F,Extremum problems with inequalities as subsidiary conditions,Traces and Emergence of Nonlinear Programming,Eds.by Giorgi G and Kjeldsen T,Springer Basel,2014,197-215.
[20]Sommese A J,Verschelde J,and Wampler C W,Numerical algebraic geometry,The Mathematics of Numerical Analysis,volume 32 of Lectures in Applied Mathematics,AMS,1996,749-763.
[21]Morgan A P and Sommese A J,Coefficient-parameter polynomial continuation,Applied Mathematics and Computation,1989,29:123-160.
[22]Li T Y,Numerical solution of multivariate polynomial systems by homotopy continuation methods,Acta Numerica,1997,6:399-436.
[23]Wang Y,Wu W,and Xia B,A special homotopy continuation method for a class of polynomial systems,Computer Algebra in Scientific Computing,Eds.by Gerdt V P,Koepf W,Seiler W M,et al.,Springer,2017,362-376.
[24]Bernshtein D N,The number of roots of a system of equations,Functional Analysis and Its Applications,1975,9:183-185.
[25]Moore R E,Methods and Application of Interval Analysis,Philadelphia,SIAM,1995.
[26]Krawczyk R,Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken,Computing,1969,4:187-201.
[27]Moore R E and Jones S T,Safe starting regions for iterative methods,SIAM Journal on Numerical Analysis,1977,14:1051-1065.
[28]Kantorovich L V,On Newton’s method for functional equations,Dokl.Akad.Nauk SSSR,1948,59:1237-1240.
[29]Rump S M,INTLAB-INTerval LABoratory,Developments in Reliable Computing,Ed.by Csendes T,Kluwer Academic Publishers,Dordrecht,1999,77-104.