First Order Perturbation and Local Stability of Parametrized Systems

详细信息    查看全文

• 作者：Daniel Lichtblau
• 关键词：Constraint geometry ; Parametric polynomial system solving ; Sensitivity to perturbations
• 刊名：Mathematics in Computer Science
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：10
• 期：1
• 页码：143-163
• 全文大小：593 KB
• 参考文献：1.Becker T., Kredel H., Weispfenning V.: Gröbner bases: a computational approach to commutative algebra. Springer-Verlag, London (1993)CrossRef MATH
  2.Bottema O., Veldkamp G.: On the lines in space with equal distances to n given points. Geometriae Dedicata 6, 121–129 (1977)MathSciNet CrossRef MATH
  3.Chaperon, T., Goulette, F.: A note on the construction of right circular cylinders through five 3d points. Technical report, Centre de Robotique, Ecole des Mines de Paris (2003)
  4.Chen, C. Golubitsky, O., Lemaire, F., Maza, M.M., Pan, W.: Comprehensive triangular decomposition. In: Proceedings of CASC 2007, Lecture Notes in Computer Science, vol. 4770, pp. 73–101. Springer-Verlag, London (2007)
  5.Chen Z., Tang X., Xia B.: Generic regular decompositions for parametric polynomial systems. J. Syst. Sci. Complex. 28, 1194–1211 (2015)MathSciNet CrossRef MATH
  6.Corless R.: Editor’s corner: Gröbner bases and matrix eigenproblems. ACM Sigsam Bull. Commun. Comput. Algebra 30, 26–32 (1996)CrossRef
  7.Cox, D.A., Little, J., O’Shea, D.: Using algebraic geometry, Graduate Texts in Mathematics. Springer-Verlag New York, Inc. (1998)
  8.Devillers O., Mourrain B., Preparata F., Trebuchet P.: On circular cylinders by four or five points in space. Discrete Comput. Geom. 28, 83–104 (2003)MathSciNet MATH
  9.Fukuda K., Jensen A.N., Lauritzen N., Thomas R.: The generic gröbner walk. J. Symb. Comput. 42, 298–312 (2007)MathSciNet CrossRef MATH
  10.Gräbe H.-G.: Algorithms in local algebra. J. Symb. Comput. 19, 545–557 (1995)MathSciNet CrossRef MATH
  11.Hoffmann, C.M., Yuan, B.: On spatial constraint solving approaches. In: Revised papers from the third international workshop on automated deduction in geometry (ADG 2000), Lecture Notes in Computer Science, vol. 2061, pp. 1–15. Springer-Verlag, London (2001)
  12.Kondratyev, A.: Numerical computation of Gröbner bases. PhD thesis, Johannes Kepler Universität Linz (2003)
  13.Kondratyev, A., Stetter, H., Winkler, F.: Numerical computation of Gröbner bases. In: Proceedings of the 7th workshop on computer algebra in scientific computation (CASC 2004), pp. 295–306 (2004)
  14.Lazard, D.: Gröbner bases, gaussian elimination, and resolution of systems of algebraic equations. In: Proceedings of the European computer algebra conference (EUROCAL 1983), Lecture Notes in Computer Science, vol. 162, pp. 146–156 (1983)
  15.Lazard D., Rouillier F.: Solving parametric polynomial systems. J. Symb. Comput. 42, 632–667 (2007)MathSciNet CrossRef MATH
  16.Lichtblau, D.: Cylinders through five points: complex and real enumerative geometry. In: Proceedings of the sixth international workshop on automated deduction in geometry (ADG 2006), Lecture Notes in Artificial Intelligence, vol. 4869, pp. 80–97[13]. Springer-Verlag (2007)
  17.Lichtblau D.: Cylinders through five points: computational algebra and geometry. J. Math. Res. 4, 65–82 (2012)MathSciNet CrossRef
  18.Macdonald I.G., Pach J., Theobald T.: Common tangents to four unit balls in \({\mathbb{R}^3}\) . Discrete Comput. Geom. 26(1), 1–17 (2001)MathSciNet CrossRef MATH
  19.Manubens, M., Montes, A.: Minimal canonical comprehensive Gröbner systems. J. Symb. Comput. 44, 463–478 (2009)
  20.Megyesi G.: Lines tangent to four unit spheres with coplanar centres. Discrete Comput. Geom. 26, 493–497 (2001)MathSciNet CrossRef MATH
  21.Montes A.: A new algorithm for discussing gröbner bases with parameters. J. Symb. Comput. 33, 183–208 (2002)MathSciNet CrossRef MATH
  22.Montes A., Wibner M.: Gröbner bases for polynomial systems with parameters. J. Symb. Comput. 45, 1391–1425 (2010)CrossRef MATH
  23.Schömer E., Sellen J., Teichmann M., Yap C.: Smallest enclosing cylinders. Algorithmica 27, 170–186 (2000)MathSciNet CrossRef MATH
  24.Stetter, H.: Stabilization of polynomial systems solving with groebner bases. In: Proceedings of the 1997 international symposium on symbolic and algebraic computation (ISSAC 1997), pp. 117–124. ACM, New York (1997)
  25.Suzuki, A., Sato, Y.: A simple algorithm to compute comprehensive gröbner bases using gröbner bases. In: Proceedings of the 2006 international symposium on symbolic and algebraic computation (ISSAC 2006), pp. 326–331. ACM, New York (2006)
  26.Teller S., Hohmeyer M.: Determining the lines through four lines. J. Graph. Tools 4, 11–22 (1999)CrossRef
  27.Theobald T.: An enumerative geometry framework for algorithmic line problems in \({\mathbb{R}^3}\) . SIAM J. Comput. 31, 1212–1228 (2002)MathSciNet CrossRef MATH
  28.Traverso, C., Zanoni, A.: Numerical stability and stabilization of Groebner basis computation. In: Proceedings of the 2002 international symposium on symbolic and algebraic computation (ISSAC 2002), pp. 262–269. ACM, New York (2002)
  29.Wallner J., Schröcker H.-P., Hu S.-M.: Tolerances in geometric constraint problems. Reliab. Comput. 11, 235–251 (2005)MathSciNet CrossRef MATH
  30.Wang, D.: The projection property of regular systems and its application to solving parametric polynomial systems. In: Algorithmic algebra and logic: proceedings of the A3L 2005, pp. 269–274 (2005)
  31.Weispfenning V.: Comprehensive gröbner bases. J. Symb. Comput. 14, 1–29 (1992)MathSciNet CrossRef MATH
  32.Wolfram Research. Mathematica 10 (2015). http://​www.​wolfram.​com
  
• 作者单位：Daniel Lichtblau (1)
  
  1. Wolfram Research, 100 Trade Center Dr., Champaign, IL, 61820, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Mathematics
  Computer Science, general
  
• 出版者：Springer Basel
• ISSN：1661-8289

文摘

A problem frequently encountered in geometric constraint solving and related settings is to ascertain sensitivity of solutions arising from a well constrained input configuration. This is important for tolerancing and motion planning, for example. An example would be determining lines simultaneously tangent to four given spheres (which originates as a line-of-sight problem); how much does a perturbation of the input affect the positioning of these lines. Once translated to an algebraic setting one has a system of polynomial equations with some coefficients parametrized, and wants to determine the solutions and a good approximation of their sensitivity to changes in the parameters. We will compute this sensitivity from first order changes in an appropriate Gröbner basis. We demonstrate the applicability on several examples. We also discuss a more global form of stability, wherein one wants to know about perturbations that might change the character of the solution space e.g. by having fewer than the generic number of solutions.