Seminars & Events

Department of Computer Science
"Linear-time finite element approximation of coercive operators"

DATE: March 1, 2007
TIME: 3:00 pm to 4:00 pm
SPEAKER: Robert Kirby, Texas Tech University
LOCATION: Research Institutes Bldg., Room 405, University of Chicago
HOST: Ridgway Scott

Description:
Multigrid algorithms are powerful tools for numerically solving certain partial differential equations in O(n) time. However, they are difficult to formulate and analyze for nonsymmetric and nonlinear operators. I will present a new theory for the iterative solution of finite element equations for coercive linear (and strongly monotone nonlinear) operators based on a constructive proof of on the fundamental existence/uniqueness result, the Lax-Milgram Theorem. This iterative technique requires a number of iterations that depends only on the coercivity and continuity constants of the operator and not on the particular subspace chosen. In particular, it is mesh-independent. Each iteration requires the computation of a Riesz map, which for many problems in H_0^1 can be done in linear time by multigrid algorithms. These iterations also turn out to be related at an operator-theoretic level to classic splitting-based stationary iterations analyzed by David Young. This work shows that if one works in the most natural topology for the problem setting rather than the Euclidean structure used by most iterative methods, linear-time algorithms are not hard to come by. The bad news is that the constants in these linear-time algorithms can be bad. I will discuss what condition numbers and preconditioning mean in this context.

More Information:
People in need of assistance should call 773-834-8977 in advance.

For information on future CS talks: http://www.cs.uchicago.edu/events
more info >>

Save the event to your calendar [schedule.ics]