15-859E Project

1. do literature search on related previous work,
2. do your new work,
3. give a presentation in class, and
4. write up a description of your work, with comparison of your results to previous work, if possible. Papers should be 8-12 pages in length. The "new work" of phase (2) above could be application of existing algorithms to a new problem; a variation on an existing algorithm; design, implementation, and testing of a new algorithm; novel theoretical analysis of an algorithm; or a survey of previous work on some topic. In a select cases, a project intentionally entailing rediscovery of a known method will be acceptable, in which case there will probably be papers/books that you should avoid looking at in phase (1).

   ---

   Schedule

   • Meet with me to discuss your project idea: 3 or 4 Nov.
   • Turn in one-page proposal of what you plan to do: 5 Nov. in class. Try to narrow the scope so it's do-able in a month. Try to skim some of the relevant references before you write up this proposal (Hit the library early, in case you need to order any papers by inter-library loan! Or ask me; I might have a copy.)
   • Tips on the presentations and written reports.
   • Give a 20-minute presentation: 1 or 3 Dec. or another day that week (to be scheduled).
   • Submit written report: 4 Dec.

   ---

   Project Topic Ideas

   The following are some possible project topics. The list is not exclusive! You can also modify an idea listed here, or propose something totally new. To get other ideas, see survey papers such as Gree90, Gree94, Bran88, bibliographies such as chapter 14 of Stol96, or popular press books such as Hubb98. I've listed references that I know of, but the list is incomplete, so you should plan on doing your own literature search.

   • Interactive 2-D n-body simulation: Do a nice implementation of two-dimensional Barnes-Hut or fast multipole method (FMM). This is an extension of the first assignment. Add options for log(r) or 1/r potential. Optimize code so it's very fast. If Barnes-Hut, try Salmon's improved multipole acceptability criteria to make sure solution is accurate. Maybe improved interaction. Run it on a fast machine (SGI Octane, DEC Alpha, say) and make a nice demo. A good project if you like user interfaces and optimization.
     References: Salm94, Blel97, Barn86, Gree87, Guy Blelloch (CMU CS prof.)

   • Simulate galactic collisions in 3-D: This project would be best for someone with experience in 3-D graphics. Implement Barnes-Hut or FMM in 3-D. Optimize it. Get or synthesize some 3-D galaxy data. Do a simulation, make some animation of it, and perhaps record it to videotape.
     References: 859E, Salm94, Blel97, Guy Blelloch (CMU CS prof.), Bob Nichol (CMU physics prof.)

   • Solve an elliptic PDE using Green's functions and multipole methods/wavelets: Green's functions are a method for converting a PDE into an integral equation (equivalently, turn a sparse system of equations into a dense system). This sounds like a step backwards, but since the matrix is smooth, the fast multipole method can be applied, often allowing the problem to be solved in O(N) time. Similarly, wavelets can transform it into a sparse matrix, and solve it in O(N) time. These techniques are related to the boundary element method and potential theory.
     References: Gree90, textbooks on PDE's, Noel Walkington (CMU Math prof.)

   • Simulate fluid flow using multipole methods: Certain flow simulations can be done using FMM.
     References: Gree90

   • Visualize fast multipole methods: FMM is confusing. See if you can demystify it by creating some really nice pictures of the terms in a multipole expansion (3-D plots from Mathematica or Maple?) or find some other way to visualize it. This is more of a visualization project than a simulation project, but still challenging. It's for someone with a knack for creating visualizations.
     References: Gree87, Wong

   • Implement multigrid on a complex domain: You might try a stress/strain problem from solid mechanics on a two-dimensional L-shaped domain, for example. Extra relaxation steps are needed near the concave corner.
     References: Bran82, Bran88, Shlomo Ta'asan (CMU Math prof.).

   • Devise a multigrid method for anisotropic PDE's: Make multigrid work on the PDE eps*Uxx+Uyy=f. This is an anisotropic variant of Poisson's equation when eps<<1. (Anisotropic means not the same in all directions.) If you standard Poisson multigrid code, it won't converge fast. Use "local mode analysis", a form of symbolic Fourier analysis, to determine how to do "line relaxation" or "semi-coarsening" to make it work. This is an applied math project.
     References: Bran82, Shlomo Ta'asan (CMU Math prof.). For this project, read a bit but not too much, since solutions have been published.

   • Simulate cloth using multigrid methods: Start with the algorithms in [Bara98] and see if you can replace their PDE solver with a multigrid method. Would it work? Maybe attempt to simulate something simple like a piece of cloth flapping in the wind. Create a short animation. Note: before starting project, check that the PDE's are elliptic. If they're not, probably punt.
     References: Bara98

   • Global optimization using multigrid: Brandt says that difficult optimization problems with lots of local minima can be solved using multigrid. Is he right? Can you do it?
     References: Bran88

   • Simulate fluid flow using multigrid: Stokes' equation yields elliptic PDE's, while Euler's equations and Navier-Stokes equations are non-elliptic. You take it from there and simulate one of these.
     References: Wess92, Bran88

   • Visualize multigrid: This is similar to the multipole visualization project above. Create a sequence of images or animation (in Mathematica or Maple?) to show how multigrid works on, say, Poisson's equation. Show us high frequencies getting attenuated and the method stepping up and down in grid level.

   • Reaction-diffusion textures using multigrid: Reaction-diffusion textures are PDE's that can be used to create organic-looking patterns such as animal skins or coral. Simulate them using multigrid methods.
     References: Witk91

   • Survey unstructured multigrid: Read up on the latest methods in multigrid methods for unstructured grids (a new research topic) and summarize them. No implementation involved.
     References: Chan97, papers by Mavriplis

   • Optical flow via multigrid: Optical flow is the field of vectors, one per pixel, showing the motion of objects from frame to frame in a video sequence. Computing optical flow is an expensive (and underconstrained) computation. Implement it using multigrid methods. Is multigrid overkill? Are coarse-to-fine pyramid methods just as good?
     References: Cohe96

   • Variational surface design using multigrid/wavelets: Find a smooth surface interpolating (passing through) or approximating specified control points. This is useful for computer vision (creating a higher level surface model from range data), for cartography (fitting a terrain model to elevation samples), and for computer-aided design (e.g. interactive sculpture of car bodies). Implement either multigrid or wavelets. For multigrid, a fine grid of quadrilaterals would probably suffice. For wavelets, you'd probably want to use quadratic or cubic B-splines as basis, set up a sparse linear system, then solve with the conjugate gradient method. I'm not sure anyone knows which is better, wavelets or multigrid. This project could be done non-interactively, but an interactive version using OpenGL would be preferable.
     References: Terz83 and Fors93 did multigrid; Gort95a and Gort95b did wavelets. See also chapter 12 of Stol96, papers by Schr and Kobb and other papers by Terzopoulos, code in VL.

   • Interactive image warping using multigrid/wavelets: Image warping and morphing are mathematically much like surface fitting: you want to find functions that smoothly interpolate (or approximate) a number of control points. In this case the functions are u(x,y) and v(x,y) -- which define the source coordinates (u,v) as a function of destination coordinates (x,y). Once you've found those functions, the rest can be done very easily using OpenGL texture mapping. If you can compute smooth functions u and v at 30Hz while the user adjusts control points, then you could do real-time (high quality) interactive image warping. Very cool. My guess is that multigrid might be fastest. Maybe this has never been done before?
     References: Beie92, Wolb90, Litw94, Fors93, plus variational surface modeling refs above.

   • Solve PDE's using wavelets: A project proposed above solved PDE's by transforming them into integral equations. There is a more direct approach that does not employ integral equations. It is supposed to yield sparse matrices with bounded condition number, which could be solved fast using the conjugate gradient method. Verify this empirically. It would be interesting to implement both the standard, non-hierarchical method (set up sparse system using finite differences) and the wavelet method, and analyze the matrices you get. You could compute their spectra (all their eigenvalues) using matlab.
     References: Jaff92, Lore91, code in VL

   • Empirical comparison of wavelet basis functions: Pick a problem (PDE, image compression, ...) and then select three or more wavelet basis functions (perhaps Haar, Daubechies, B-spline), implement them and do an empirical comparison of the results: which solved the problem fastest, or compressed best?
     References: ?

   • Literature survey of wavelet basis functions: Choose some wavelet application (image compression, say), and read a bunch (10?) papers that use various wavelets for it, glean what you can, and write up a comparison of the wavelets for this application ("Consumer's Reports Guide to Wavelets"). This is a good project for those who love to do literature search and read heavily mathematical papers.
     References: ?

   • Wavelet compression of images or terrain data: This is a more complete version of the third programming assignment. Try a more sophisticated wavelet than Haar, and pay more attention to quantization and encoding of coefficients. If image compression, do color, not just grayscale. You will need to devise a compressed wavelet file format.
     References: Stol96 cites De Vore, Eck95, Gros95

   • Wavelets on the sphere: You could use this to model data sampled around the earth, functions of direction such as the radiance of reflected light, or perhaps the shape of electron orbitals in quantum mechanics. Implement wavelets on the sphere and compare them to other methods for representing functions on a sphere, such as spherical harmonics, or latitude-longitude grids.
     References: two papers by Schr

   • Simulate fluid flow with wavelets: References: Qian93

   ---

   References

   [859E]

   Web pages for this course: http://www.cs.cmu.edu/~ph/859E/www/

   [Bara98]

   David Baraff and Andrew Witkin, Large Steps in Cloth Simulation, Proc. SIGGRAPH 98, 1998, pp. 43-54, http://www.cs.cmu.edu/~baraff/papers/index.html

   [Barn86]

   Josh Barnes and Piet Hut, A hierarchical O(NlogN) force-calculation algorithm, Nature, 324, Dec. 1986, pp. 446-449

   [Beie92]

   Thaddeus Beier and Shawn Neely, Feature-based Image Metamorphosis, Computer Graphics (SIGGRAPH '92 Proceedings), 26 (2), July 1992, pp. 35-42

   [Blel97]

   Guy Blelloch and Girija Narlikar, A Practical Comparison of N-Body Algorithms, Parallel Algorithms, American Mathematical Society, 1997, on web

   [Bran82]

   A. Brandt, Guide to multigrid development, Multigrid Methods, W. Hackbusch and U. Trottenberg, eds., Springer-Verlag, 1982, pp. 220-312

   [Bran88]

   A. Brandt, The Weizmann Institute research in multilevel computation: 1988 report, Proc. 4th Copper Mountain Conf. on Multigrid Methods, J. Mandel and others, eds. SIAM, 1989, pp. 13-53, (I have copy)

   [Chan97]

   Tony F. Chan and Susie Go and L. Zikatanov, Lecture Notes on Multilevel Methods for Elliptic Problems on Unstructured Grids, UCLA Math. Dept., (97-11), Mar. 1997, http://www.math.ucla.edu/~chan/mgpapers.html

   [Cohe96]

   I. Cohen, (paper on multigrid optical flow), Marie-Odile Berger and others, eds., Images, wavelets and PDE's., Proc. 12th Intl. Conf. on Analysis and Optimization of Systems, Springer-Verlag, 1996

   [Eck95]

   Matthias Eck and Tony DeRose and Tom Duchamp and Hugues Hoppe and Michael Lounsbery and Werner Stuetzle, Multiresolution Analysis of Arbitrary Meshes, SIGGRAPH '95 Proc., Aug 1995, pp. 173-182, probably on web

   [Fors93]

   David R. Forsey and Lifeng Weng, Multi-resolution surface approximation for animation, Proc. Graphics Interface '93, 1993, pp. 192-200

   [Gort95a]

   Steven J. Gortler, Wavelet Methods for Computer Graphics, Princeton, NJ Department of Computer Science, Princeton University PhD thesis, (CS-TR-473-94), jan 1995, http://hillbilly.deas.harvard.edu/~sjg/

   [Gort95b]

   Steven J. Gortler and Michael F. Cohen, Hierarchical and Variational Geometric Modeling with Wavelets, 1995 Symposium on Interactive 3D Graphics, pp. 35-42, http://www.research.microsoft.com/research/graphics/cohen/

   [Gree87]

   Leslie Greengard and V. Rokhlin, A Fast Algorithm for Particle Simulations, Journal of Computational Physics, 73, 1987, pp. 325-348

   [Gree90]

   L. Greengard, The numerical solution of the N-body problem, Computers in Physics, 4 (2), mar-apr 1990, pp. 142-152

   [Gree94]

   L. Greengard, Fast algorithms for classical physics, Science, 265 (5174), 12 Aug. 1994, pp. 909-914

   [Gros95]

   Markus H. Gross and R. Gatti and O. Staadt, Fast Multiresolution Surface Meshing, Proc. IEEE Visualization '95, jul 1995, http://www.inf.ethz.ch/publications/tr.html

   [Hubb98]

   Barbara Burke Hubbard, The World According to Wavelets: The Story of a Mathematical Technique in the Making, A K Peters, 1998

   [Jaff92]

   Stephane Jaffard, Wavelet Methods for Fast Resolution of Elliptic Problems, SIAM Journal on Numerical Analysis, 29 (4), aug 1992, pp. 965-986,

   [Kobb]

   papers by Leif Kobbelt: http://www9.informatik.uni-erlangen.de/Persons/Kobbelt/publist.html

   [Litw94]

   Peter Litwinowicz and Lance Williams, Proceedings of SIGGRAPH '94, Animating Images with Drawings, jul 1994, pp. 409-412

   [Lore91]

   R. A. Lorentz and W. R. Madych, Spline wavelets for ordinary differential equations, Gesellschaft fur Mathematik und Datenverarbeitung , no. 562, 1991 (in E&S library)

   [Qian93]

   Sam Qian and John Weiss, Wavelets and the numerical solution of partial differential equations, J. Comp. Phys., 106, 1993, pp. 155-175

   [Salm94]

   John K. Salmon and Michael S. Warren, Skeletons from the Treecode Closet, J. Comp. Phys., 111 (1), 1994, pp. 136-155, http://www.cacr.caltech.edu/~johns/papers.html

   [Schr]

   papers by Peter Schroeder: http://www.multires.caltech.edu/pubs/

   [Stol96]

   Eric J. Stollnitz and Tony D. DeRose and David H. Salesin, Wavelets for Computer Graphics, 1996, Morgann Kaufmann

   [Terz83]

   D. Terzopoulos, Multilevel computational processes for visual surface reconstruction, Computer Vision, Graphics, and Image Processing, 24, 1983, pp. 52-96

   [VL]

   Andrew Willmott's VL library (fancier brother of SVL): http://www.cs.cmu.edu/~ajw/public/dist/

   [Wess92]

   P. Wesseling, An Introduction to Multigrid Methods, John Wiley & Sons, 1992

   [Wit91]

   Andrew Witkin and Michael Kass, Reaction-diffusion textures, Computer Graphics (SIGGRAPH '91 Proceedings), 25 (4), jul 1991, pp. 299-308, http://www.cs.cmu.edu/~aw/gallery.html, see Ray Tracing News, v.5, n. 1 & 2 for errata: http://www.acm.org/tog/resources/RTNews/html/

   [Wolb90]

   George Wolberg, Digital Image Warping, IEEE Computer Society Press, 1990

   [Wong]

   Stephen Wong's multipole diagrams, http://wong.physics.oberlin.edu/

   ---

   Bibliographies

   • fast summation (n-body) bibliography: http://sobolev.mit.edu/~jurgen/References/fastsum.bib
   • multigrid bibliography: http://www.mgnet.org/mgnet-bib.html
   • wavelet bibliographies: http://www.amara.com/current/wavelet.html#wbiblio
   • and many of these are parts of the bigger, very nice Computer Science Bibliography: http://liinwww.ira.uka.de/bibliography/index.html

   ---

   15-859E, Hierarchical Methods for Simulation
   Paul Heckbert

   This file is http://www.cs.cmu.edu/~ph/859E/www/project.html