Solving Systems of Polynomial Equations: a Novel End Condition and Root Computation Method

• Autorzy: Maciej Bartoszuk
• Języki publikacji: EN

Abstrakty

EN

In this paper we present an improvement of the algorithm based on recursive de Casteljau subdivision over an n-dimensional bounded domain (simplex or box). The modification consists of a novel end condition and a way of calculation the root in subdomain. Both innovations are based on linear approximation of polynomials in a system. This improvement results in that our approach takes almost half of the time of the standard approach: it can be stopped much earlier than using standard diameter condition and getting midpoint of a subdomain as a root.(original abstract)

Słowa kluczowe

EN

Algorithms; Mathematical analysis; Analytical and computational methods

PL

Algorytmy; Analiza matematyczna; Metody analityczno-obliczeniowe

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 543--552

Twórcy

autor

Maciej Bartoszuk

• Polish Academy of Sciences

Bibliografia

• Bini D., "Numerical computation of polynomial zeros by means of aberth's method," Numerical Algorithms, vol. 13, no. 2, pp. 179-200, 1996. doi: 10.1007/BF02207694. [Online]. Available: http://dx.doi.org/10.1007/BF02207694
• Buse L., Elkadi M., and Mourrain B., "Generalized resultants over unirational algebraic varieties," J. of Symbolic Computation, vol. 29, pp. 515-526, 2000. doi: 10.1006/jsco.1999.0304. [Online]. Available: http://dx.doi.org/10.1006/jsco.1999.0304
• Canny J., "The Complexity of Robot Motion Planning," MIT Press, 1988. doi: 10.1017/S0263574700000151 ACM Doctoral Dissertation Award. [Online]. Available: http://dx.doi.org/10.1017/S0263574700000151
• Chen J., Lazard S., Peñaranda L., Pouget M., Rouillier F., and Tsigaridas E. P., "On the topology of planar algebraic curves," Mathematics for Computer Science. Special issue on Computational Geometry and Computer Aided Geometric Design, vol. 4, no. 1, pp. 113-137, 2010. doi: 10.1145/1542362.1542424. [Online]. Available: http://dx.doi.org/10.1145/1542362.1542424
• Dedieu J. -P. and Yakoubsohn J. -C., "Computing the real roots of a polynomial by the exclusion algorithm," Numerical Algorithms, vol. 4, no. 1, pp. 1-24, 1993. doi: 10.1007/BF02142738. [Online]. Available: http://dx.doi.org/10.1007/BF02142738
• Gao S., IV F. V., and Wang M., "A new algorithm for computing grobner bases," 2010.
• Kearfott R. B., "Interval arithmetic techniques in the computational solution of nonlinear systems of equations: Introduction, examples and comparisons," Lectures in Applied Mathemetics. AMS Press, pp. 337-357, 1990.
• Lavender D., Bowyer A., Davenport J., Wallis A., and Woodwark J., "Voronoi diagrams of set-theoretic solid models," IEEE Computer Graphics and Applications, pp. 69-77, September 1992. doi: 10.1109/38.156016. [Online]. Available: http://dx.doi.org/10.1109/38.156016
• Marciniak K., Pawelec E., and Porter-Sobieraj J., "Method for finding all solutions of systems of polynomial equations," Proc. 7th IEEE Int. Conf. Methods and Models in Automation and Robotics, vol. 1, pp. 155-158, 2001.
• Mourrain B. and Ruatta O., "Relation between roots and coefficients, interpolation and application to system solving," JSC, vol. 33, pp. 679-699, 2002. doi: 10.1006/jsco.2002.0530. [Online]. Available: http://dx.doi.org/10.1006/jsco.2002.0530
• Pan V., "Optimal and nearly optimal algorithms for approximating polynomial zeros," Computers & Mathematics with Applications, vol. 31, no. 12, pp. 97-138, 1996. doi: 10.1016/0898-1221(96)00080-6. [Online]. Available: http://dx.doi.org/10.1016/0898-1221(96)00080-6
• Pitman J., Probability, ser. Springer Texts in Statistics. Springer, 1993. ISBN 9780387979748. [Online]. Available: http://books.google.pl/books?id=L6IWgaCuilwC
• Porter-Sobieraj J. and Klopotek R., "Solving systems of polynomial equations on a GPU," Computer Science and Information Systems (Fed-CSIS), 2012 Federated Conference on, Series IEEE Computer Society Press(2012), pp. 539-544, 2012.
• Porter-Sobieraj J., "Application of simplexes to the solving systems of algebraic equations," Proc. of the IInd International Conference on Advances in Production Engineering 2001, Oficyna Wydawnicza PW, part II, pp. 23-32, 2001.
• Rouillier F. and Zimmermann P., "Efficient isolation of a polynomial real roots," J. Comput. Appl. Math., 2003. doi: 10.1016/j.cam.2003.08.015. [Online]. Available: http://dx.doi.org/10.1016/j.cam.2003.08.015
• Roy M., "Basic algorithms in real algebraic geometry: from Sturm theorem to the existential theory of reals," Exposition in Mathematics, vol. 23, pp. 1-67, 1996.
• Sederberg T., Anderson D., and Goldman R., "Implicit representation of parametric curves and surfaces," Computer Vision, Graphics, and Image Processing, vol. 28, no. 1, 1984. doi: 10.1016/0734-189X(84)90140-3. [Online]. Available: http://dx.doi.org/10.1016/0734-189X(84)90140-3
• Seland J. and Dokken T., "Real-time algebraic surface visualization," Geometrical Modeling, Numerical Simulation, and Optimization, Springer, Heidelberg, pp. 163-183, 2007. doi: 10.1007/978-3-540-68783-2_6. [Online]. Available: http://dx.doi.org/10.1007/978-3-540-68783-2_6
• Su H. -J., McCarthy J., Sosonkina M., and Watson L., "Algorithm 857: POLSYS GLP: A parallel general linear product homotopy code for solving polynomial systems of equations," ACM Trans. Math. Softw, vol. 32, no. 4, pp. 561-579, 2006. doi: 10.1145/1186785.1186789. [Online]. Available: http://dx.doi.org/10.1145/1186785.1186789
• Tomov S., Nath R., Ltaief H., and Dongarra J., "Dense linear algebra solvers for multicore with GPU accelerators," Proceedings of the IEEE International Symposium on Parallel and Distributed Processing Workshops (IPDSW 2010) IEEE Computer Society, pp. 1-8, 2010. doi: 10.1109/IPDPSW.2010.5470941. [Online]. Available: http://dx.doi.org/10.1109/IPDPSW.2010.5470941
• Verschelde J. and Yoffe G., "Evaluating polynomials in several variables and their derivatives on a GPU computing processor," IEEE Computer Society, pp. 1391-1399, 2012. doi: 10.1109/IPDPSW.2012.177. [Online]. Available: http://dx.doi.org/10.1109/IPDPSW.2012.177
• Verschelde J. and Yoffe G., "Polynomial homotopies on multicore workstations," Proceedings of the 4th International Workshop on Parallel Symbolic Computation (PASCO 2010), ACM, pp. 131-140, 2010. doi: 10.1145/1837210.1837230. [Online]. Available: http://dx.doi.org/10.1145/1837210.1837230
• Verschelde J., "Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation," ACM Transactions on Mathematical Software (TOMS), vol. 25, no. 2, pp. 251-276, 1999. doi: 10.1145/317275.317286. [Online]. Available: http://dx.doi.org/10.1145/317275.317286
• Waggenspack W. N. and Anderson D. C., "Converting standard bivariate polynomials to Bernstein form over arbitrary triangular regions," Comput. Aided Des., vol. 18, no. 10, pp. 529-532, Dec. 1986. doi: 10.1016/0010-4485(86)90040-0. [Online]. Available: http://dx.doi.org/10.1016/0010-4485(86)90040-0
• Wilkinson J., "The evaluation of the zeros of ill-conditioned polynomials. parts i and ii," Numer. Math., 1:150-166 and 167-180, 1959. doi: 10.1007/BF01386381. [Online]. Available: http://dx.doi.org/10.1007/BF01386381