Solving Algebraic Constraints
The problem of finding (all) solutions of a set of nonlinear 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 Bspline 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 twodimensional 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.
· Preferred dates (order of preference): April 21^{st} , May 7^{th}, May 12^{th} · 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.

Date 
Name 
Topic 
1 
Mar 22nd 
Gershon Elber 
Introduction to the Constraints and Bezier basis functions and representation 
2 
Mar 29th 
Gershon Elber 
Introduction to the Bezier/Bspline basis functions and representation 
3 
Apr 5th 
Gershon Elber 
Introduction to Algebraic Constraint Solving 
4 
Apr 19th(No Class) 





5 
Apr 26th 
John Noonan 
J. M. Lane and R. F. Riesenfeld. Bounds on a polynomial 
Fady Massarwi 
T. A. Grandine. Computing zeroes of spline functions. 

6 
May 3rd 





7 
May 10th 
Lior Ben Zvi 
B. Mourrain and J.P. Pavone. Subdivision methods for solving polynomial equations. 



8 
May 17th 





9 
May 24th 





10 
June 7th 





11 
June 14th 





12 
June 21st(No Class) 





13 
June 28th 
Lotem Fridman 
F. Wei, J. Feng, and H. Lin. Gpubased parallel solver via the Kantorovich theorem for the nonlinear Bernstein polynomial systems 


1. M. Barton. Solving polynomial systems using noroot elimination blending schemes. ComputerAided Design, 43(12):18701878, 2011.
2. M. Barton, G. Elber, and I. Hanniel. Topologically guaranteed univariate solutions of underconstrained polynomial systems via noloop and single component tests. ComputerAided 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 10511058.
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 1829, 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. ComputerAided Design 46: 101109 (2014).
13. I. Hanniel and G. Elber. Subdivision termination criteria in subdivision multivariate solvers using dual hyperplanes representations. ComputerAided 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 underconstrained 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 7687.
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 403426.
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. ComputerAided 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. Gpubased parallel solver via the Kantorovich theorem for the nonlinear Bernstein polynomial systems. Computers & Mathematics with Applications, 62(6):25062517, 2011.