Distinguished Guest Lecturer
Meshing in Fixed Dimension in near Optimal Work and Time
Gary Miller
School of Computer Science
Carnegie Mellon University
Nov 15 2007 3:30PM
480 Dreese Labs
All interested parties are invited to attend.
Refreshments will served in the lecture room immed
Abstract:
A finite element mesh or simply a mesh has has amazingly broad applicability. In its simplest form, the goal is to decompose a region into triangles/tetrahedra with good aspect ratio. The main use of a mesh is to represent succinctly functions in space and time. Thus meshes arise in areas such as scientific simulations, manufacturing, and graphics to mention only a few areas.
On the other hand, robust and fast code has be elusive for what is a seemingly simple problem. One of the issues that has hampered quality code has been the lack of algorithms that works over a large class of problems. The lack of available code is so bad that many, if not most researchers doing complicated simulations have given up the hope of having available good meshes and have developed possibly suboptimal methods that do not rely on meshing. Good code seems to need algorithms with provable guarantees.
Algorithms with quality, size, and run time guarantees have been much harder to find than expected. The case of 2D meshing has been a little easier. Over the last 17 years computer scientists have been in the forefront in designing algorithms with guarantees for the meshing problem. The work began with the quadtree meshing in 1990 and Ruppert's 1993 2D Delaunay Refinement algorithm.
3D versions of the 2D algorithms have been progressing much more slowly. In fact, some of the best progress has been done here a OSU. Prior to our work, no algorithms with subquadratic run-times were known in 3D. We have made progress on this front by developing a new meshing algorithm in any fixed dimension, Sparse Voronoi Refinement (SVR). The meshing problem in 3D, for example, takes as input a domain and a collection of features (points, edges, and faces) and decomposes the domain into tetrahedra. The algorithm has guarantees on size, quality and run time.
SVR is a hybrid algorithm using the best features of the Octtree algorithm and Delaunay refinement. It has sequential-time/work bounds of O(n log n + m) for reasonable inputs of size n and outputs of size m. The input is in any fixed dimension with piecewise-linear constraining (PLC) features. The parallel time is O(log L/s log m)$ with the same work. SVR is straightforward enough that our 3D code demonstrates that it is both more robust and faster than other publicly available code.
This represents joint work with Benoit Hudson and Todd Phillips.
Bio: Dr. Miller is a Professor in the Computer Science Department at Carnegie Mellon University. Prof. Miller is most famous for his work in algorithm design, both sequential and parallel. These new algorithms have appeared in over one hundred papers in journals and prestigious conferences. He has also developed a commercial overlay network for the Internet used by Akamai Technologies to increase the speed and reliability of the Internet. For his work on testing for primality he is a co-recipient of the Kanellakis Theory and Practice Award 2003. His most recent interest are in algorithms for both scientific computation and image processing. In particular, interest in 1)spectral graph theory and it application to linear system solvers and image segmentation, and 2) meshing and its application. Prof. Miller received his Ph.D. in Mathematics from Berkeley in 1975. He was held positions at Waterloo, Rochester, MIT, USC, CMU, and Akamai.
Host: Tamal Dey
