Solving Algebraic Constraints

Seminar in Computer Graphics 236816

Lecturer:  Gershon Elber

Time:  Wednesday 9:30-11:30,   Place: Taub (CS) 401

http://www.cs.technion.ac.il/~gershon/seminar16

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.

Prerequisites:

 

1.      104011 Hedva 2m, or equivalent.

2.      234107 Numeric Analysis 1, or equivalent.

Course Policy:

·            All students are required to submit their preferences by 31st of March (End of 2nd week of semester). You are invited to start and send us your requests as early as you can.

·            We cannot guarantee registration to the seminar unless you have an assigned presentation slot. Hence, coordinate your presentation topic as soon as you can. You cannot consider yourself 'registered' before you receive an acknowledgement and a presentation-date assignment from us (see below).

·            The topics are not limited to the provided list of papers and a student who likes to present other topic(s) is invited to contact the lecturer.

·            Provide your preferences via email to Prof. Elber in a message titled "Seminar preference" and in the format shown in the example below. It is your responsibility to make sure we receive your preferences.  A sample preference request:

  • Personal Info: Yossi Graph, Student ID 1234567, Hasmacha, Semester 6. I am registered for the course.

·         Preferred dates (order of preference): April 21st , May 7th, May 12th  

·         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.

·            You are to prepare a presentation, approx. one (academic) hour long, on your assigned topic out of our list, or a topic that you convinced us is worth presenting.

·            You are expected to dig and find additional material relevant to your talk, as much as possible. The WEB is a wonderful resource with which to start.

·            You have to be ready to deliver your talk A WEEK PRIOR TO THE SCHEDULED DATE. You may be called to deliver your talk earlier/later than scheduled.

·            You must email us with (a pointer to) your talk at least 7 days prior to the talk so we can include it here so other students can come prepared to your talk. Failing to make your presentation available on the WEB a week prior to your presentation and informing us, will automatically reduce your grade by 5%.

·            While we require you to attend all seminars, you can miss a single seminar with no penalty. Missing any additional seminar you will cost you 2%, up to 20% in total, of the final grade.

Grading policy:

 

75%: Class presentation;

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

20%: Attendance of the course.


 

Schedule

 

 

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/B-spline 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. Gpu-based parallel solver via the Kantorovich theorem for the nonlinear Bernstein polynomial systems

 

 

Literature

 

1.      M. Barton. Solving polynomial systems using no-root elimination blending schemes. Computer-Aided Design, 43(12):1870–1878, 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):1035–1044, 2011.

3.      M. Barton and B. Juttler. Computing roots of polynomials by quadratic clipping. Computer Aided Geometric Design, 24(3):125–141, 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:71–78, 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):596–604, 2009.

8.      G. Elber and M.-S. Kim. Geometric constraint solver using multivariate rational spline functions. ACM symposium on Solid modeling and applications, pages 1–10, 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):191–216, 1987.

11.  T. A. Grandine. Computing zeroes of spline functions. Computer Aided Geometric Design, 6(2):129–136, 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):369–378, 2007.

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

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

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

17.  J. Mizrahi and G. Elber. Topologically guaranteed bivariate solutions of under-constrained multivariate piecewise polynomial systems. Computer Aided Design, 58:210–219, 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):845–865, 2007.

20.  B. Mourrain and J.-P. Pavone. Subdivision methods for solving polynomial equations. Journal of Symbolic Computation, 44(3):292–306, 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):612–640, 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):1360–1369, 2011.

23.  F. Rouillier and P. Zimmermann. Efficient isolation of polynomial’s real roots. Journal of Computational and Applied Mathematics, 162(1):33–50, 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):161–171, 1988.

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

27.  E. C. Sherbrooke and N. M. Patrikalakis. Computation of the solutions of nonlinear polynomial systems. Computer Aided Geometric Design, 10(5):379–405, 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):2506–2517, 2011.