A quadratic clipping step with superquadratic convergence for bivariate polynomial systems. (English) Zbl 1254.65062

Jüttler, Bert; Moore, Brian

Math. Comput. Sci. 5, No. 2, 223-235 (2011).

Summary: A new numerical approach to compute all real roots of a system of two bivariate polynomial equations over a given box is described. Using the Bernstein-Bézier representation, we compute the best linear approximant and the best quadratic approximant of the two polynomials with respect to the \(L^2\) norm. Using these approximations and bounds on the approximation errors, we obtain a fat line bounding the zero set first of the first polynomial and a fat conic bounding the zero set of the second polynomial. By intersecting these fat curves, which requires solely the solution of linear and quadratic equations, we derive a reduced subbox enclosing the roots. This algorithm is combined with splitting steps, in order to isolate the roots. It is applied iteratively until a certain accuracy is obtained. Using a suitable preprocessing step, we prove that the convergence rate is 3 for single roots. In addition, experimental results indicate that the convergence rate is superlinear (1.5) for double roots.

MSC:

65H04	Numerical computation of roots of polynomial equations
30C15	Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)

Keywords:

root finding; polynomial; Bézier clipping

Software:

ISOLATE

References:

[1]	Bartoň M., Jüttler B.: Computing roots of polynomials by quadratic clipping. Comput. Aided Geom. Des. 24, 125–141 (2007) · Zbl 1171.65395 · doi:10.1016/j.cagd.2007.01.003
[2]	Bartoň, M. and Jüttler, B.: Computing roots of systems of polynomials by linear clipping. Technical Report 2007-18, SFB F013 Technical Report. http://www.sfb013.uni-linz.ac.at (2007) · Zbl 1171.65395
[3]	Elber, G. and Kim, M.-S.: Geometric constraint solver using multivariate rational spline functions. In: The sixth ACM/IEEE symposium on solid modeling and applications, pp. 1–10. Ann Arbor (2001)
[4]	Elkadi M., Mourrain B.: Symbolic-numeric methods for solving polynomial equations and applications. In: Dickenstein, A., Emiris, I.Z. (eds) Solving Polynomial Equations, Algorithms and Computation in Mathematics, vol. 14, pp. 125–168. Springer, Berlin (2004) · Zbl 1152.68701
[5]	Farouki R.T., Goodman T.N.T.: On the optimal stability of the Bernstein basis. Math. Comput. 65, 1553–1566 (1996) · Zbl 0853.65051 · doi:10.1090/S0025-5718-96-00759-4
[6]	Faugère J.-C.: A new efficient algorithm for computing Gröbner bases (F 4). J. Pure Appl. Algebra 139, 61–88 (1999) · Zbl 0930.68174 · doi:10.1016/S0022-4049(99)00005-5
[7]	Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F 5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pp. 75–83. ACM, New York (2002) · Zbl 1072.68664
[8]	Garloff J., Smith A.P.: Investigation of a subdivision based algorithm for solving systems of polynomial equations. Nonlinear Anal. 47, 167–178 (2001) · Zbl 1042.65526 · doi:10.1016/S0362-546X(01)00166-3
[9]	Giusti M., Lecerf G., Salvy B., Yakoubsohn J.-C.: On location and approximation of clusters of zeros: Case of embedding dimension one. Found. Comput. Math. 7, 1–58 (2007) · Zbl 1124.65047 · doi:10.1007/s10208-004-0159-5
[10]	Hoschek J., Lasser D.: Fundamentals of Computer Aided Geometric Design. AK Peters, Wellesley (1993) · Zbl 0788.68002
[11]	Ko, K.H., Sakkalis, T., Patrikalakis, N.M.: Nonlinear polynomial systems: multiple roots and their multiplicities. In: Proceedings of shape modeling international (SMI), pp. 87–98. IEEE Computer Society (2004)
[12]	Lecerf G.: Quadratic Newton iteration for systems with multiplicity. Found. Comput. Math. 2, 247–293 (2002) · Zbl 1030.65050 · doi:10.1007/s102080010026
[13]	Leykin A., Verschelde J., Zhao A.: Higher-order deflation for polynomial systems with isolated singular solutions. In: Dickenstein, A., Schreyer, F.-O., Sommese, A.J. (eds) Algorithms in Algebraic Geometry, Mathematics and its Applications, vol. 146, pp. 79–97. IMA and Springer, New York (2008) · Zbl 1138.65038
[14]	Lutterkort D., Peters J.: Optimized refinable enclosures of multivariate polynomial pieces. Comput. Aided Geom. Des. 18, 851–863 (2001) · Zbl 0984.68164 · doi:10.1016/S0167-8396(01)00067-X
[15]	Mainar E., Peña J.M.: Evaluation algorithms for multivariate polynomials in Bernstein–Bézier form. J. Approx. Theory 143, 44–61 (2006) · Zbl 1104.41007 · doi:10.1016/j.jat.2006.05.007
[16]	Mantzaflaris, A., Mourrain, B.: Deflation and certified isolation of singular zeros of polynomial systems. In: Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 249–256. ACM, New York (2011) · Zbl 1323.65054
[17]	Mantzaflaris A., Mourrain B., Tsigaridas E.: On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers. Theor. Comput. Sci. 412, 2312–2330 (2011) · Zbl 1243.12005 · doi:10.1016/j.tcs.2011.01.009
[18]	Mourrain B., Pavone J.P.: Subdivision methods for solving polynomial equations. J. Symb. Comput. 44, 292–306 (2009) · Zbl 1158.13010 · doi:10.1016/j.jsc.2008.04.016
[19]	Mourrain, B., Rouillier, F., Roy, M.-F.: The Bernstein basis and real root isolation. In: Combinatorial and Computational Geometry, of Math. Sci. Res. Inst. Publ., vol. 52, pp. 459–478. Cambridge University Press, Cambridge (2005) · Zbl 1094.14051
[20]	Nishita T., Sederberg T., Kakimoto M.: Ray tracing trimmed rational surface patches. Comput. Graph. 24, 337–345 (1990) · doi:10.1145/97880.97916
[21]	Ojika T., Watanabe S., Mitsui T.: Deflation algorithm for the multiple roots of a system of nonlinear equations. J. Math. Anal. Appl. 96, 463–479 (1983) · Zbl 0525.65027 · doi:10.1016/0022-247X(83)90055-0
[22]	Pope S.R., Szanto A.: Nearest multivariate system with given root multiplicities. J. Symb. Comput. 44, 606–625 (2009) · Zbl 1168.65347 · doi:10.1016/j.jsc.2008.03.005
[23]	Prautzsch H., Boehm W., Paluszny M.: Bézier and B-Spline Techniques. Springer, Berlin (2002)
[24]	Rouillier F.: Solving zero-dimensional systems through the rational univariate representation. Appl. Algebra Eng. Commun. Comput. 9, 433–461 (1999) · Zbl 0932.12008 · doi:10.1007/s002000050114
[25]	Rouillier F., Zimmermann P.: Efficient isolation of polynomial’s real roots. J. Comput. Appl. Math. 162, 33–50 (2004) · Zbl 1040.65041 · doi:10.1016/j.cam.2003.08.015
[26]	Rump S., Graillat S.: Verified error bounds for multiple roots of systems of nonlinear equations. Numer. Algorithms 54, 359–377 (2010) · Zbl 1201.65081 · doi:10.1007/s11075-009-9339-3
[27]	Sharma V.: Complexity of real root isolation using continued fractions. Theor. Comput. Sci. 409, 292–310 (2008) · Zbl 1158.68055 · doi:10.1016/j.tcs.2008.09.017
[28]	Sherbrooke E.C., Patrikalakis Nicholas M.: Computation of the solutions of non-linear polynomial systems. Comput. Aided Geom. Des. 10, 379–405 (1993) · Zbl 0817.65035 · doi:10.1016/0167-8396(93)90019-Y
[29]	Tsigaridas E.P., Emiris I.Z.: On the complexity of real root isolation using continued fractions. Theor. Comput. Sci. 392, 158–173 (2008) · Zbl 1134.68067 · doi:10.1016/j.tcs.2007.10.010
[30]	Wu X., Zhi L.: Determining singular solutions of polynomial systems via symbolic-numeric reduction to geometric involutive form. J. Symb. Comput. 27, 104–122 (2008)