write up a description of your work, with
comparison of your results to previous work, if possible.
Papers should be 812 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 onepage proposal of what you plan to do: 5 Nov.
in class.
Try to narrow the scope so it's doable 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 interlibrary loan! Or ask me;
I might have a copy.)

Tips on the presentations and written reports.

Give a 20minute 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 2D nbody simulation:
Do a nice implementation of twodimensional BarnesHut
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 BarnesHut,
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 3D:
This project would be best for someone with experience in 3D
graphics.
Implement BarnesHut or FMM in 3D.
Optimize it.
Get or synthesize some 3D 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 (3D 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 twodimensional Lshaped 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 "semicoarsening"
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 NavierStokes equations are nonelliptic.
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.

Reactiondiffusion textures using multigrid:
Reactiondiffusion textures are PDE's that can be used to create
organiclooking 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 coarsetofine 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 computeraided 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 Bsplines
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 noninteractively, 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 realtime (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,
nonhierarchical 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, Bspline),
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 latitudelongitude 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. 4354,
http://www.cs.cmu.edu/~baraff/papers/index.html

[Barn86]

Josh Barnes and Piet Hut,
A hierarchical O(NlogN) forcecalculation algorithm,
Nature,
324,
Dec.
1986,
pp. 446449

[Beie92]

Thaddeus Beier and Shawn Neely,
Featurebased Image Metamorphosis,
Computer Graphics (SIGGRAPH '92 Proceedings),
26 (2),
July 1992,
pp. 3542

[Blel97]

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

[Bran82]

A. Brandt,
Guide to multigrid development,
Multigrid Methods,
W. Hackbusch and U. Trottenberg, eds.,
SpringerVerlag,
1982,
pp. 220312

[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. 1353,
(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.,
(9711),
Mar.
1997,
http://www.math.ucla.edu/~chan/mgpapers.html

[Cohe96]

I. Cohen,
(paper on multigrid optical flow),
MarieOdile Berger and others, eds.,
Images, wavelets and PDE's.,
Proc. 12th Intl. Conf. on Analysis and Optimization of Systems,
SpringerVerlag,
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. 173182,
probably on web

[Fors93]

David R. Forsey and Lifeng Weng,
Multiresolution surface approximation for animation,
Proc. Graphics Interface '93,
1993,
pp. 192200

[Gort95a]

Steven J. Gortler,
Wavelet Methods for Computer Graphics,
Princeton, NJ
Department of Computer Science, Princeton University
PhD thesis,
(CSTR47394),
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. 3542,
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. 325348

[Gree90]

L. Greengard,
The numerical solution of the Nbody problem,
Computers in Physics,
4
(2),
marapr
1990,
pp. 142152

[Gree94]

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

[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. 965986,

[Kobb]

papers by
Leif Kobbelt:
http://www9.informatik.unierlangen.de/Persons/Kobbelt/publist.html

[Litw94]

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

[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. 155175

[Salm94]

John K. Salmon and Michael S. Warren,
Skeletons from the Treecode Closet,
J. Comp. Phys.,
111
(1),
1994,
pp. 136155,
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. 5296

[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,
Reactiondiffusion textures,
Computer Graphics (SIGGRAPH '91 Proceedings),
25
(4),
jul
1991,
pp. 299308,
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
15859E, Hierarchical Methods for Simulation
Paul Heckbert
This file is
http://www.cs.cmu.edu/~ph/859E/www/project.html