Gary Miller

Professor Emeritus

Website

Email gm2f@andrew.cmu.edu

Phone (412) 268-2631

Department
Computer Science Department

Research Interests
Theory
Algorithms and Complexity

My main interest is in sequential and parallel algorithm design. Of particular interest are problems that arise in scientific computation and image processing. We have been working on three classes of problems. Our work is both more theoretical yet more practical since we require two important properties of our algorithms: they should be both be fast and have strong guarantees of quality, size, and speed.

Mesh Generation The question of correctly and efficiently partitioning space into tetrahedra with good aspect ratio so that the features appear in the mesh is at least a fifty year old problem. The computer science community has been working on this problem for about twenty years. The most accurate simulations in the science, engineering, and graphic require small size quality meshes. CMU has been a leader on this problem for the last fifteen years.

Spectral Graph Theory The interplay between graph theory and linear algebra is possibly one of the most interesting and practical areas in modern algorithm design. Possibly the most famous example is Google PAGE-RANK which is the Perron-Frobenius eigenvector of the link graph. The second example is the interplay between fast linear solvers and graph theory. We have ongoing collaboration on fast solvers and eigen calculations. These new algorithm work in near linear time.

Image Processing We are interested in fast and reliable algorithm for image processing. Of special interest is 3D medical image processing. Our main tool that allows us to get new fast algorithms is spectral graph theory. This has allowed us to compute eigenvectors of our image as speed comparable to many simple filtering algorithms. We are also using interior point methods from convex optimization to de-noise images. Again these methods all use our fast solvers for speed.

Publications