ON THIS PAGE:

Course Objectives

Prerequisites

Approach

Typical Text

Course Outline

Course Objectives
Teach error analysis and efficiency analysis via a driving problem that requires geometric algorithms.

Prerequisites
COMP 122, MATH 166.

Approach
Teach error analysis and efficiency analysis via a driving problem that requires geometric algorithms. Bring up error analysis approaches when they are relevant to the driving problem. Thus lectures should mix the motivating problem, the algorithms, and the methods of analysis. In addition, it is desirable that the course give an experience in scientific computation. Thus it should involve solving a real scientific problem, should require the solution of a range of numerical problems, and should involve the student in programming solutions to real parts of the problem, experiencing the speeds and accuracies that result from the choice of methods.

Driving Problem
In the syllabus below, the geometric algorithms, error analysis subjects, and efficiency analysis subjects are prescriptive. The particular driving problem is not. Here we give a particular driving problem to illustrate the feasibility of the approach, but the instructor is free to change the driving problem.

Rigid body simulation using the laws of Newtonian dynamics.

It consists of

• Collision Detection
• Contact Determination (Assume only point contacts)
• Expressing Motion Constraints of the Bodies at each Contact Point as a system of constraint equations. Main emphasis on how to formulate and solve this constraint system.
• Use of First Order Differential Equation--relating position and orientation with velocity and angular velocity, inertia tensor and mass. Setting up the partial differential equation system.
• Solving Differential Equations. Dealing with ill-conditioned Jacobians, whenever an impulse is to be applied.
• Use of Quadratic Programming to solve linear complementary problem and use of Mathematical Programming methods (an optimization problem). Use of Matrix Inversion. Dealing with Singular Systems.

• Convex Hulls. Issues in computing convex hull in three dimensions. Problems of numerical stability. Eventually boils down to computing sign of a 4 * 4 determinant. Use of perturbation in floating point arithmetic. Use of exact arithmetic.
• Voronoi Regions Computations. Issues of Numeric Stability. How to circumvent problems caused by floating point computation.
• Contact Determination with imprecise information. Because of our representations, we have error in the model and error accumulated in computations. For example, due to floating point arithmetic we cannot exactly represent rotations for almost all angles (as the sines and cosines used in the matrix correspond to approximate representations). Problems with degenerate configurations.
• Some knowledge of Newtonian Dynamics.
• Solving first and second order differential equations. Integrating the equations by taking finite steps.
• Dealing with Ill-Conditioned Jacobians.
• Solving Optimization Problems, in particular a quadratic programming problems. Needs knowledge of different methods of solving linear systems and their comparisons in terms of efficiency and accuracy

Students should implement the driving problem as a series of assignments. For example, start with easy dynamic simulation, such as air-hockey pucks (2D and circularly symmetric). Then add complexities week by week, so there is always a visualized dynamic simulation.

Typical Text
There is no single textbook that will cover this course. Text materials might include selected chapters from

• Pizer with Wallace, To Compute Numerically
  
• Preparata and Shamos, Computational Geometry
  
• Hoffman, Geometric and Solid Modeling

• Convex Sets, Convex Hull in 2D and 3D, Voronoi Regions, Proximity Problems, Applications to Collision Detection between Polyhedral Objects, Contact Determination.
• Robust and Error Free Geometric Computations, Problem of Consistency in Geometric Computation due to floating point errors. Line intersection conditioning.
• Application to Dynamic Simulation.
• Error analysis: generation: arithmetic and representation, approximation, propagation, stability and convergence.
• Algorithm analysis: O() analysis
• Solution of linear systems, ordinary and partial differential equations, function evaluation, nonlinear equations.

Syllabus (in 75 minute lectures)
This syllabus does not adequately intermix driving problem issues and subjects of algorithms and their analysis within lectures. Materials from adjacent lectures will need to be intermixed to accomplish this goal.

• Lecture 1: Driving problem overview. Absolute and relative error
• Lecture 2: Generated error, propagated error, and their interaction.
• Lecture 3: Robust and Error-Free Geometric Operations. Problems of inconsistency in geometric computations by using line-intersection problems. Different sources of error (in the model, in the floating point computations)
• Lectures 4, 5: Arithmetic and representation error, floating point computing
• Lectures 6, 7: Convex sets and computing convex hull of points in 2D and 3D. Algorithm analysis.
• Lecture 8: Problems in computing convex hull in 3D due to finite precision arithmetic and degenerate data. Use of perturbation methods and exact arithmetic.
• Lectures 9-12: Error propagation, partial derivatives, calculation graphs, sensitivity, condition number, analysis of Gaussian elimination with pivoting. QR method and singular value decomposition.
• Lecture 13: Voronoi Regions and Proximity Problems. Algorithm analysis
• Lecture 14: Collision Detection between Polyhedral Models. Emphasis on convex polytopes only.
• Lecture 15: Closest Features computation and use of Voronoi regions. Application to collision detection and contact determination.
• Lecture 16, 17: Approximation error and function evaluation, Taylor series error analysis (If the course needs to be shortened, these are lectures that might be cut to one or omitted, replacing it with a short statement of the existence of error in the approximation of functions and the existence of methods to bound that error.)
• Lecture 18: Rigid Body Simulation. Formulation of Constraint Equations.
• Lecture 19: How to solve the differential equations and taking care of ill-conditioned Jacobians.
• Lectures 20, 21: Stability analysis for recurrent methods
• Lecture 22: Contact force computation as problem with solution of nonlinear equations.
• Lectures 23, 24: Convergence and error analysis for iterative methods, one method for solving partial differential equations, applications of error analysis to partial differential equations.
• Lecture 25: Contact force computation as optimization problem. How to solve the Quadratic programming problem (which are convex programming problems)?
• Lecture 26: Summary of error analysis. With application to problem of contact force optimization, overall error analysis and designing algorithms taking efficiency as well as numerical accuracy into account.
• Lecture 27: Putting driving problem together, system implementation.