Search our Site
ON THIS PAGE:
Course Objectives
Prerequisites
Approach
Typical Text
Course Outline
 
COMP 205: Scientific and Geometric Computation
(3 hours)
Official Syllabus approved April 1984
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 Equationrelating position and
orientation with velocity and angular velocity, inertia
tensor and mass. Setting up the partial differential
equation system.
 Solving Differential Equations. Dealing with illconditioned
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.
To solve the driving problem we need to know
 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 IllConditioned 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
Assignments
There is no course project.
Students should implement the driving problem as a series of assignments.
For example, start with easy dynamic simulation, such as airhockey 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
Course Outline
 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 ErrorFree Geometric Operations. Problems of
inconsistency in geometric computations by using lineintersection
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 912: 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
illconditioned 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.
