### Friday, October 31

## MS15

The Multilevel Method

3:00 PM-5:00 PM

*Room: Ballroom 2*

The multilevel method has emerged as one of the most effective methods for solving numerical and combinatorial problems. It has been used in multigrids, domain decomposition, geometric search structures, as well as optimization algorithms for problems such as partitioning and sparse-matrix ordering. The multilevel method is a class of algorithmic techniques for solving computational and optimization problems. The trademark of these techniques is that in the solution of a problem P, we define a hierarchical set of problems P_0 = P, P_1,...,P_L where P_i is in some sense a coarser approximation of P_{i-1}. The basic strategy is to find the solution for P_L first and then, level by level, construct the solution of P_{i-1} from that of P_i. The research directions of multilevel methods are to find effective methods for coarsening, recognize the class of problems that can be solved efficiently by multilevel methods.

The speakers will discuss algorithms and numerical issues for unstructured meshes, geometric techniques for provably good coarsening and applications in combinatorial optimization

**Organizer: Shang-Hua Teng**

*University of Illinois, Urbana-Champaign and University of Minnesota, Minneapolis*

**3:00 Multilevel Domain Decomposition for Unstructured Meshes**
- Susie Go and
*Tony F. Chan*, University of California, Los Angeles
**3:30 Optimal Good Aspect - Ratio Coarsening for Unstructured Meshes**
- Gary L. Miller, and
*Dafna Talmor*, Carnegie Mellon University; and Shang-Hua Teng, Organizer
**4:00 Multilevel Algorithms for Combinatorial Problems **
*Bruce Hendrickson*, Sandia National Laboratories, Albuquerque; and Erik G. Boman, Stanford University
**4:30 Coarsening, Sampling, and Smoothing: Elements of the Multilevel Method**
- Shang-Hua Teng, Organizer

*MMD, 4/17/97*

*tjf, 6/13/97*

*MMD, 8/6/97*