Events - Colloquia & Seminars

CCIS Colloquia Fall 2004
TUMBLE a software package for the simulation of soft tissues in 2D

Gary Miller
CS, CMU

Date:Nov 03, 2004
Talk:12:00pm, 366 West Village H

Abstract

As biology, as well as many other fields, requires computer simulations of highly deformable materials, we have developed a 2D moving-mesh package for the simulation of soft tissues. We have started with the simulation of red blood cells in a fluid flow where the cells as well as the containing vessel, such as a heart, may be highly deformable and have interesting dynamics. We have chosen the Lagrangian approach, that is, we move the mesh with the material. This method over say Eulerian has the advantage that the systems to be solved at each time frame, for say Navier-Stokes with immerse membrane, are all linear. In addition, there are many other advantages that we will discuss in the talk. The main downside, though, is that the meshing problems become much more difficult. We show how to address these meshing problems, as well as show some interesting simulations. This represents joint work with David E. Cardoze, Mark Olah, and Todd Phillips.

Biography

Summary

Dr. Miller has over the past 30 years contributed to the design and analysis of many practical and fundamental algorithms, including such algorithms as Miller-Rabin primality test, Parallel Tree Contraction, Geometric Separator Algorithm.

Biography

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. He has designed both sequential and parallel algorithms. These new algorithms have appeared in over eighty 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. His most recent interest is in parallel algorithm design for problems arising from Scientific Computation including parallel algorithms for; partitioners for finite element meshes, parallel preconditioners for iterative linear system solvers, parallel and sequential algorithms for mesh generation, and parallel algorithms for mesh partitioners. Prof. Miller received his Ph.D. in Mathematics from U.C. Berkeley in 1975. He was a post-doc at the U. of Waterloo, Assistant Professor at the U. of Rochester, Associate Professor of Applied Mathematics at MIT, Professor of Computer Science at the USC, Professor of Computer Science at CMU, and Principal Research Scientist for Akamai Technologies.

Research Overview

Professor Miller's main contribution to Computer Science has been in the area of design and analysis of algorithms. Because of his work in algorithm design, Computer Scientists can now generate algorithms from a wide area of problems that are more efficient and often much simpler than were possible before.

In his thesis, he gave a new algorithm for testing for primality of integers. He showed that, assuming a long outstanding conjecture in number theory, The Extended Riemann Hypothesis, one can quickly test primality. There is also a highly practical randomized version of this algorithm, which was independently discovered by Rabin, and commonly known as the Miller-Rabin randomized primality test. These primality tests were critical in the deployment of ubiquitous public key cryptographic systems such as RSA and Diffie-Hellman.

He has also found fundamental algorithms for a variety of problems including; testing whether the roots of a polynomial are expressible in radicals (with Susan Landau), testing if two graphs isomorphic, finding small circuit layouts for the Shuffle-Exchange graph (with Tom Leighton, Margaret Lepley, and, Daniel Kleitman), embedding graphs on surfaces (with Ion Filotti and John Reif), and finding small separators for planar graphs.

He has also worked on fine grain parallel algorithm design, with an emphasis on processor efficient algorithms. Possibly, the most famous of this work is a paradigm for constructing efficient parallel algorithms known as Parallel Tree Contraction (with John Reif). This paradigm is fundamental for almost all known problems that have an underlying tree, such as; parsing, expression evaluation, algorithms on planar graphs, and graph connectivity. Other fundamental algorithms he developed include; optimal algorithms for list ranking (with Richard Anderson) and expression evaluation (with Hillel Gazit). He also found the first almost processor optimal parallel algorithms for general graph problems: testing 3-connectivity of a graph (with Vijaya Ramachandran), finding planar separators (with Gazit), and finding a maximum flows for multi-sink and multi-source planar graph (with Seffi Naor). Other problems for which he and his collaborators have found the best known parallel algorithms include; parallel circuit evaluation (with Eric Kaltofen and Ramachandran) and constructing Huffman codes in parallel (with ShangHua Teng and others). It is noteworthy that, unlike many theoretical algorithms, most of these algorithms are simple enough to be of practical significance. These algorithms form a key part of many courses on parallel algorithm design.

Another area of Miller's research has been in finding graph separators. The separator theorems for planar graphs have had a major impact on the area of design and analysis of algorithms. Divide-and-conquer graph algorithms rely on separators for graphs. Lipton and Tarjan showed that every planar graph has a $n^{1/2}$ separator. The class of planar graphs is a very important one but it is quite restrictive. Planar graphs, in some sense, restrict one to problems arising from two-dimensional problems. It has been said that one of the major goals of the next generation of supercomputers is to do simulations of problems arising from three dimensions. With William Thurston, he found a method for extending the separator algorithms to graphs arising from such 3-dimensional problems. Prior to this work it had been assumed that the planar separator results could not be extended in a meaningful way to 3-dimensional graphs, but many natural simulation problems are 3-D and not just 2-D. He was able to show that, under a very natural assumption, 3-D separators of size $O(n^{2/3})$ exist and can be efficiently found.

In join work with ShangHua Teng and Steven Vavasis, he greatly improved the analysis and and simplified the algorithm. They were able to extended the work to any dimension and to improve the run time through better statistical methods. For the two years Professor Miller was a full-time Principal Research Scientist at Akamai Technologies. During this time he developed a commercial overlay network for the Internet. The project was based on experiments performed by him on the Internet measuring download times both around the world as well as across North America. These tests were very instructive. They showed that Akamai could obtain systematic improvements in both download times and reliability by routing packets destined for one Akamai machine first to another Akamai machine and from this intermediate machine on to the final machine, also known as an overlay network. Based on these experiments he headed a group to design and build a commercial-grade system to direct the traffic in the overlay system. The system was designed to run 24/7 with several layers of redundancies. Keynote tests with real client data show download times improve by \%15 to \%30 systematically. When the Internet is not performing well or has a major outage the overlay network may be the only way for Akamai to get its data delivered to the end user.

Since returning to CMU he has focused his attention to computer simulations of blood flow at the level of individual cells. By working in the Lagrangian framework and using moving meshes with higher order elements his group have produced code which is 10 to 100 times faster than earlier methods.