Thursday, May 4, 2006
4:15 pm
B17 Upson Hall

Computer Science
Spring 2006

Doug L. James
Carnegie Mellon University


Sub-linear time algorithms for deformable systems


Analyzing deforming mechanical systems using classical numerical methods is computationally demanding. The sheer complexity of realistic systems and their interactions makes low-latency simulation difficult. This frustrates important human-computer applications such as surgical simulation and multi-modal interaction using sound or haptic force feedback.

In this talk, I will describe a variety of sub-linear time algorithms that use a two-stage approach to compile discrete simulation models into optimized representations. The first stage "preprocesses away" system complexity using precomputation, model reduction, compression, and novel system parameterizations. The second stage performs interactive computations using sub-linear time algorithms that reason efficiently about the complete system by exploiting the precomputed information. I will propose sub-linear time algorithms for a range of problems including output-sensitive collision detection; subspace dynamics for large-deformation models; haptic force-feedback rendering; efficient mesh animation using rotation-sequence clustering; and precomputed acoustic transfer for output-sensitive sound generation from geometrically complex vibration sources.

ABOUT THE SPEAKER: Doug L. James has been an Assistant Professor of Computer Science and Robotics at Carnegie Mellon University since Fall 2002. He received his Ph.D. from the Institute of Applied Mathematics at the University of British Columbia, Vancouver, Canada, advised by Dinesh K. Pai. Doug received an NSF Early Career Development Award for his work on "Precomputing Data-driven Deformable Systems for Multimodal Interactive Simulation," he was one of Popular Science magazine's "Brilliant 10" young scientists for 2005, and is an Alfred P. Sloan research fellow.