Last edited 27jul98 by gfrancis@uiuc.edu
Find this document at http://new.math.uiuc.edu/seminar/

Summer 1998 Computational Mathematics Seminar


Room 102 Altgeld ( grafiXlab)

Watch for our Vosaic transmission, later this summer, once we get our license renewed. You may also view the videotapes of lectures given last summer in the grafiXlab. Put this page into your bookmarks for current seminar announcements.

11 AM Tuesday 28 July 1998

Continued from 11 AM Tuesday 23 June 1998

Foams in Three-Manifolds

by

John M. Sullivan


We will examine the geometry of foams, especially the class known as TCP foams. We will describe how these foams can be used to tile many three-manifolds.

11 AM Tuesday 16 June 1998

Ochiai's iterative method for embedding a triangulated Pair-of-Pants in 3-space.

by

Noriko Imafuji


visiting from

Nara Women's University, Japan

In 1994 M. Ochiai proposed a canonical matrix derived from the incidence matrix of a 3-connected (simple) planar graph with the following remarkable property. For any embedding of the graph the boundary of the infinite complementary component consists of a closed, polygonal subgraph. Consider a particular placement of this subgraph as a convex polygon about the origin. Place all other vertices initially at the origin and apply Ochiai's matrix recursively to this data. The iteration quickly converges to a canonical embedding of the graph in the plane and keeping the initial data fixed.

This same method applies to a triangulation of a Pair-of-Pants surface (genus 0 with 3 punctures), given the initial placement of the three border loops in 3-space. Ochiai's iteration quickly converges to a pleasing embedding of the surface, which is parametrized by the position of the borders.

The plan for my seminar is as follows:

0. Planar Graphs
   a. How to obtain the matrix.
   b. Demonstration of the embedding. 
1. The Transformation Matrix
   a. How to obtain the matrix.
   b. A theorem concerning the matrix.
2. Embedding the Pair-of-Pants
   a. The original graph of the triangulation. 
   b. Demonstration of the embedding.

I will explain this method and illustrate by real-time interactive computer animations.

11 AM Tuesday 9 June 1998

Leapfrog methods for Einstein's geodesic equation
u''+u=k u^2 for gravitational lenses.

by Ulises Cervantes-Pimentel

The numerical solution of ordinary (ODE) and partial differential equations (PDE) is carried out by finite differences approximations of the total and partial derivatives of the function u. The accuracy of the derivatives approximation depends basically on two factors:

When only two points are considered, we talk of an Euler method or a trapezoidal method if we include more points. If we can compute the values of the current state based only on the previous state, we call it an explicit method, if we need points from the current or next state, we call it an implicit method. Based on the way we take such points we can have the following schemes (among other): 

*-*-*
  |  Backward Euler (Implicit)
  *

  *
  |
*-*-*  Forward Euler (Explicit)

  *
  |  Friedrichs (Explicit)
*---*

*-*-*
  |  Crank-Nicolson (explicit)
*-*-*

  *
  |
*---*  Leap-Frog (implicit)
  |
  *

When the differential equation is written down using any of these schemes, we can always rewrite it using matricial notation. For all the explicit methods, we end up with a system of the form u_(n+1)=A u_(n) which reflect the fact that we only need the values at step n to determine the values for step n+1. On the other hand, for implicit methods we get a system of the form A u_(n+1)= B u_(n)+C u_(n-1)+...

If the matrix A has a special form (upper/lower triangular, symmetric positive,etc) we can use special algorithms to solve the system (backward substitution, Gauss, gradient method and iterative methods) and in some cases paralellize the computation.

The step size and scheme selected, determine the local truncation error (LTE) of the differential equation when it is rewritten by finite differences. There is also another important factor to consider, the stability of the system. We need to be sure that the numerical solution obtained is related to the real solution of the differential equation in such way that it approaches the real solution as we let the step size go to zero. Hence we need to make an stability analysis of the system.

The selection of the discretization scheme depends on the nature of the differential equation (parabolic, elliptic, hyperbolic PDE, etc) and the stability analysis. We are interested in those schemes which can be scaled to 2D and 3D.

Considering the geodesic equation u''+u=k u^2, I will write down the corresponding finite difference equation and the LTE and stability analysis for the Leap frog scheme. It was reported that this scheme was the most convenient for this problem, but we can of course compare agains other schemes.

Once MATLAB becomes available in the Department, I will have a MATLAB implementation of the solution.