Solving Algebraic Constraints

The problem of finding (all)
solutions of a set of non-linear equations/constraints is highly important in a
whole variety of fields in science and engineering. In this seminar, we will
explore algorithms and methods to solve sets of algebraic constraints,
primarily using *subdivision based solvers*. Subdivision based solvers
exploit properties of special (piecewise) polynomial bases, the Bezier and
B-spline basis functions, to allow the computation of the solution with the
following properties:

1. The solvers focus on real solutions only.

2. All solutions are guaranteed to be globally isolated up to a provided tolerance and machine precision.

3. The solvers can manage zero dimensional solution spaces, one dimensional solution spaces (univariate curves), and even two-dimensional solution spaces (bivariate surfaces).

The seminar will include a few introductory classes that will be delivered by the lecturer only to be followed by lectures given by the students, selected from the list of papers below. Students are also invited to propose other (academic) papers for presentation.

1. 104011 Hedva 2m, or equivalent.

2. 234107 Numeric Analysis 1, or equivalent.

- Personal Info: Yossi Graph, Student ID 1234567, Hasmacha, Semester 6. I am registered for the course.
·
Preferred
dates (order of preference): April 21 · Preferred topics: o First choice: . o Second Choice: o Third Choice: · Comments: I am highly qualified for the first topic as I also took the CAGD 236716 course. |

75%: Class presentation;

5%: Readiness of material a week prior to talk;

20%: Attendance of the course.

** **

1. M. Barton. Solving polynomial systems using no-root elimination blending schemes. Computer-Aided Design, 43(12):18701878, 2011.

2. M. Barton, G. Elber, and I. Hanniel. Topologically guaranteed univariate solutions of underconstrained polynomial systems via no-loop and single component tests. Computer-Aided Design, 43(8):10351044, 2011.

3. M. Barton and B. Juttler. Computing roots of polynomials by quadratic clipping. Computer Aided Geometric Design, 24(3):125141, 2007.

4. X. D. Chen and W. Ma. Rational cubic clipping with linear complexity for computing roots of polynomials. Applied Mathematics and Computation Vol 273, 15, January 2016, Pages 1051-1058.

5. E. Cohen, R. F. Riesenfeld, and G. Elber. Geometric Modeling with Splines, an Introduction. A K Peters, 2001.

6. Eigenwillig, V. Sharma, and C. Yap. Almost tight recursion tree bounds for the Descartes method. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, 2006:7178, 2006.

7. G. Elber and T. Grandine. An efficient solution to systems of multivariate polynomial using expression trees. Visualization and Computer Graphics, IEEE Transactions on, 15(4):596604, 2009.

8. G. Elber and M.-S. Kim. Geometric constraint solver using multivariate rational spline functions. ACM symposium on Solid modeling and applications, pages 110, 2001.

9. C. Funfzig, D. Michelucci, S. Foufou. Polytope based computation of polynomial ranges. Computer Aided Geometric Design, vol 29, pp 18-29, 2012.

10. R. T. Farouki and V. T. Rajan. On the numerical condition of polynomials in Bernstein form. Computer Aided Geometric Design, 4(3):191216, 1987.

11. T. A. Grandine. Computing zeroes of spline functions. Computer Aided Geometric Design, 6(2):129136, 1989.

12. I. Hanniel. Solving multivariate polynomial systems using hyperplane arithmetic and linear programming. Computer-Aided Design 46: 101-109 (2014).

13. I. Hanniel and G. Elber. Subdivision termination criteria in subdivision multivariate solvers using dual hyperplanes representations. Computer-Aided Design, 39(5):369378, 2007.

14. W. Krandick and K. Mehlhorn. New bounds for the Descartes method. Journal of Symbolic Computation, 41(1):4966, 2006.

15. J. M. Lane and R. F. Riesenfeld. Bounds on a polynomial. BIT Numerical Mathematics, 21(1):112117, 1981.

16. J. M. McNamee. A bibliography on roots of polynomials. Journal of Computational and Applied Mathematics, 47(3):391394, 1990.

17. J. Mizrahi and G. Elber. Topologically guaranteed bivariate solutions of under-constrained multivariate piecewise polynomial systems. Computer Aided Design, 58:210219, 2015.

18. J. Mizrahi and Gershon Elber. Detection of critical points of multivariate piecewise polynomial systems. Computer Aided Geometric Design, Vol 40, December 2015, pp 76-87.

19. K. M. Morken and M. Reimers. An unconditionally convergent method for computing zeros of splines and polynomials. Mathematics of Computation, 76(258):845865, 2007.

20. B. Mourrain and J.-P. Pavone. Subdivision methods for solving polynomial equations. Journal of Symbolic Computation, 44(3):292306, 2009.

21. Mourrain, M. N. Vrahatis, and J.-C. Yakoubsohn. On the complexity of isolating real roots and computing with certainty the topological degree. Journal of Complexity, 18(2):612640, 2002.

22. C. Park, G. Elber, K. Kim, G. Kim, and J. Seong. A hybrid parallel solver for systems of multivariate polynomials using cpus and gpus. Computer Aided Design, 43(11):13601369, 2011.

23. F. Rouillier and P. Zimmermann. Efficient isolation of polynomials real roots. Journal of Computational and Applied Mathematics, 162(1):3350, 2004.

24. S. Ray, P. S. V. Nataraj. An efficient algorithm for range computation of polynomials using the Bernstein form. Journal of Global Optimization, Nov 2009, Vol 45, Issue 3, pp 403-426.

25. T. W. Sederberg and R. J. Meyers. Loop detection in surface patch intersections. Computer Aided Geometric Design, 5(2):161171, 1988.

26. T. W. Sederberg and T. Nishita. Curve intersection using Bezier clipping. Computer-Aided Design, 22(9):538549, 1990.

27. E. C. Sherbrooke and N. M. Patrikalakis. Computation of the solutions of nonlinear polynomial systems. Computer Aided Geometric Design, 10(5):379405, 1993.

28. F. Wei, J. Feng, and H. Lin. Gpu-based parallel solver via the Kantorovich theorem for the nonlinear Bernstein polynomial systems. Computers & Mathematics with Applications, 62(6):25062517, 2011.