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).
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.
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
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.
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
Implement Barnes-Hut or FMM in 3-D.
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
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.
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
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.
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?
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
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.
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?
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.
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
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.
My guess is that multigrid might be fastest.
Maybe this has never been done before?
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,
(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?
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.
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:
Web pages for this course:
David Baraff and Andrew Witkin,
Large Steps in Cloth Simulation,
Proc. SIGGRAPH 98,
Josh Barnes and Piet Hut,
A hierarchical O(NlogN) force-calculation algorithm,
Thaddeus Beier and Shawn Neely,
Feature-based Image Metamorphosis,
Computer Graphics (SIGGRAPH '92 Proceedings),
Guy Blelloch and Girija Narlikar,
A Practical Comparison of N-Body Algorithms,
American Mathematical Society,
Guide to multigrid development,
W. Hackbusch and U. Trottenberg, eds.,
The Weizmann Institute research in multilevel computation: 1988 report,
Proc. 4th Copper Mountain Conf. on Multigrid Methods,
J. Mandel and others, eds.
(I have copy)
Tony F. Chan and Susie Go and L. Zikatanov,
Lecture Notes on Multilevel
Methods for Elliptic Problems on Unstructured Grids,
UCLA Math. Dept.,
(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,
Matthias Eck and Tony DeRose and Tom Duchamp and
Hugues Hoppe and Michael Lounsbery and Werner
Multiresolution Analysis of Arbitrary Meshes,
SIGGRAPH '95 Proc.,
probably on web
David R. Forsey and Lifeng Weng,
Multi-resolution surface approximation for animation,
Proc. Graphics Interface '93,
Steven J. Gortler,
Wavelet Methods for Computer Graphics,
Department of Computer Science, Princeton University
Steven J. Gortler and Michael F. Cohen,
Hierarchical and Variational Geometric Modeling with Wavelets,
1995 Symposium on Interactive 3D Graphics,
Leslie Greengard and V. Rokhlin,
A Fast Algorithm for Particle Simulations,
Journal of Computational Physics,
The numerical solution of the N-body problem,
Computers in Physics,
Fast algorithms for classical physics,
12 Aug. 1994,
Markus H. Gross and R. Gatti and O. Staadt,
Fast Multiresolution Surface Meshing,
Proc. IEEE Visualization '95,
Barbara Burke Hubbard,
The World According to Wavelets: The Story of a
Mathematical Technique in the Making,
A K Peters,
Wavelet Methods for Fast Resolution of Elliptic Problems,
SIAM Journal on Numerical Analysis,
Peter Litwinowicz and Lance Williams,
Proceedings of SIGGRAPH '94,
Animating Images with Drawings,
R. A. Lorentz and W. R. Madych,
Spline wavelets for ordinary differential equations,
Gesellschaft fur Mathematik und Datenverarbeitung ,
(in E&S library)
Sam Qian and John Weiss,
Wavelets and the numerical solution of partial differential equations,
J. Comp. Phys.,
John K. Salmon and Michael S. Warren,
Skeletons from the Treecode Closet,
J. Comp. Phys.,
papers by Peter Schroeder:
Eric J. Stollnitz and Tony D. DeRose and David H. Salesin,
Wavelets for Computer Graphics,
Multilevel computational processes for visual surface reconstruction,
Computer Vision, Graphics, and Image Processing,
Andrew Willmott's VL library
(fancier brother of SVL):
An Introduction to Multigrid Methods,
John Wiley & Sons,
Andrew Witkin and Michael Kass,
Computer Graphics (SIGGRAPH '91 Proceedings),
see Ray Tracing News, v.5, n. 1 & 2 for errata:
Digital Image Warping,
IEEE Computer Society Press,
Stephen Wong's multipole diagrams,
15-859E, Hierarchical Methods for Simulation
This file is