15859E: Hierarchical Methods for Simulation
A Graduate Course in the Carnegie Mellon University
Computer Science Dept., Fall 1998
Instructor:
Paul Heckbert
Time: TR 10:3011:50,
First class is 15 Sept., last class is 4 Dec. 1998
Place: Wean 5409A
Shortcuts:
schedule ;
links
on
nbody ,
multigrid ,
wavelets
Description:
This course will cover hierarchical methods for simulating physical
phenomena. In recent years, the development of nbody algorithms,
multigrid methods, and wavelets have permitted very large simulation
problems in science and engineering to be solved. We will study these
algorithms and implement some of them.
Announcements:

Guests are welcome to come to the
project presentations 14 December
(schedule)

17 Nov: See the tips for presentations and report, below.

Written reports are due 4 December.

Old announcements are
here.
Class Resources
(T = Tuesday, R = Thursday)

T 15 Sept.:
Summary of course, introduction to nbody problem.

R 17 Sept.:
Simple nbody algorithms.
Grant Brommel presents paper:
An Efficient Program for ManyBody Simulation,
Andrew Appel,
SIAM J. Sci. Stat. Comput.,
Jan. 1985.;
Frank Dellaert presents paper:
A hierarchical O(NlogN) forcecalculation algorithm,
Josh Barnes and Piet Hut,
Nature,
Dec. 1986.

T 22 Sept.:
Preview of fast multipole method, and survey of some applications.
Stephen Vinay presents paper:
Fast Algorithms for Classical Physics,
Leslie Greengard,
Science, 12 Aug. 1994.
Nbody programming assignment out.

R 24 Sept.:
Logistics of nbody assignment (compiling, linking),
potential laws for 2D and 3D,
adaptive time steps,
software demo by Professor Heckbert.

T 29 Sept.:
John Huebner and Professor Heckbert present paper:
A Fast Algorithm for Particle Simulations,
Leslie Greengard and Vladimir Rokhlin,
J. of Computational Physics, 1987.

R 1 Oct.:
Final nbody lecture.
Application of nbody methods to radiosity (graphics)
and surface modeling (see Witkin paper below).
Testing nbody software.
Sign up for group order of Briggs' book,
A Multigrid Tutorial,
about $17 or $18 each.

T 6 Oct.:
No lecture;
instead we meet in Wean 5205 (SGI's), 5203 (PC's), and 5201 (Suns)
for demos of students' nbody programs.

R 8 Oct.:
Begin multigrid.
Professor Heckbert and George Bulwinkle present chapters 1 and 2
of Briggs' A Wavelet Tutorial.

T 13 Oct.:
Franklin Chen presents chapter 3 of Briggs.

R 15 Oct.:
Professor Heckbert discusses chapter 4 of Briggs.
Reading for Tuesday will be available on Friday afternoon (16 Oct.)
outside Doherty 4309.

T 20 Oct.:
Professor Heckbert discusses multigrid applications.
Reading for today:
Achi Brandt, Multilevel Adaptive Computations in
Fluid Dynamics, AIAA Journal, Oct. 1980, pp. 11651172.
Lecture Notes: Survey of Multigrid Applications:
2up postscript (good for printing),
pdf (fullpage  good for reading
onscreen),
postscript (fullpage) .

R 22 Oct.:
Multigrid assignments due the night before.
We'll discuss them and cover basis functions and simple (Haar) wavelets.

T 27 Oct.:
Nicholas Konidaris will present chapter 3 of Stollnitz.
Please read chapters 1,2,4 also.
Prof. Heckbert will discuss the wavelet programming assignment,
which will be image compression.

R 29 Oct.:
Read Stollnitz chapter 6 (except 6.2, 6.3)
chapter 7 through 7.3,
and chapter 14.
and Prof. Heckbert will summarize example topics for the
research project.
A list will be distributed on paper and also on the web.
Start thinking about picking a project idea.

T 3 Nov.:
Wavelet assignments due the night before.
We'll discuss them briefly in class.
Read the rest of chapter 7.
Prof. Heckbert will discuss subdivision curves and multiresolution analysis.
Discuss your project idea with Prof. Heckbert outside class time
today and tomorrow.

R 5 Nov.:
Hand in a one page summary of your project idea.
More discussion of multiresolution analysis.

T 10 Nov.:
Special event: Franklin Chen will present his work on
nbody simulations using the ML programming language.
Skim Stollnitz chapters 10 and 11, read chapter 12.
German Cheung will present chapter 12  variational
surface modeling.

R 12 Nov.:
Franklin Chen will complete his ML nbody talk.
Read Stollnitz chapter 13.
Prof. Heckbert will give an intro. to global illumination.
Demos of wavelet radiosity by Andrew Willmott,
and wavelet image compression by Prof. Heckbert,
in Doherty 4301 lab.

T 17 Nov.:
Prof. Heckbert will
discuss the solution of integral equations
using wavelets, namely simulating global illumination
(thermal radiation and radiosity).
Tips for presentations and reports.
Greg Zornetzer will present Stollnitz section 7.4  biorthogonal wavelets.

R 19 Nov.:
More wavelets.
Read/skim
Building Your Own Wavelets at Home,
Wim Sweldens and Peter Schroeder.
Anurag Gupta will present the first part of this.

T 24 Nov.:
Jane Wang will present the second part of Building Your Own
Wavelets at Home.
Later that day:
field trip to the
Pittsburgh Supercomputing Center (PSC)
for an astrophysics and virtual reality demo from
Joel Welling.
Meet at Wean 5th floor lobby at 1:25,
walk to Mellon Institute on Fifth Ave a few blocks beyond Craig St
(see map).
PSC is inside.
Demo there from approx. 1:402:30.
See
some of their visualizations here if you can't come.

R 26 Nov.: no class (Thanksgiving)

T 1 Dec.:
Project presentations, day 1. Wean 5409A
 10:30 Greg Zornetzer, Wavelets for Noise Removal from NMR Signals
 10:55 Nick Konidaris, Wavelets for Cluster Analysis of Galaxies

R 3 Dec.:
Project presentations, day 2. Wean 5409A
 10:30 Randon Warner, Wavelet Image Compression, I
 10:55 Anurag Gupta, Wavelet Image Compression, II
 11:20 Franklin Chen, Wavelets for Interactive Multiresolution
Image Editing

F 4 Dec. (special meeting of class)
Project presentations, day 3. Wean 4623  NOTE SPECIAL ROOM
 9:30 Jianlin Wang, Solution of Anisotropic PDE's using Multigrid
 rescheduled from Tuesday to this slot
 10:00 Steven Vinay, Simulating Diffusion using Multigrid Methods
 10:25 German Cheung, Interactive Image Warping using Multigrid
 10:50 John Huebner, Variational Surface Design Using Wavelets
 11:15 George Bulwinkle, Optical Flow and the Multigrid Method

NBody Problem

why is space threedimensional?
Max Tegmark's thoughts

Web Links and Tutorials on NBody / Particle Simulation Methods,
collected by Amara Graps,
graduate student in Heidelberg, Germany

Tree Codes for NBody Simulations tutorial,
section of the book Parallel Computing Works,
on work done at the Caltech Concurrent Computation Program

Lectures by Jim Demmel, Berkeley, on
BarnesHut
and
Greengard
algorithms.

Links on NBody Algorithms,
collected by Guy Blelloch for "Algorithms in the Real World" course

Girija Narlikar and Guy Blelloch's nbody research at CMU

John Salmon,
astrophysicist, Caltech, parallel tree codes,
and his paper
Skeletons from the Treecode Closet
(hold down shift key when you click on this),
Journal of Computational Physics, 1994.

Mario Antonioletti's large collection of nbody links

Bibliography on fast summation methods,
by Juergen Singer

MPEG animations and pictures of astrophysics simulations,
Michael Warren, Los Alamos

Physically Based Modeling notes,
notes on
"Differential Equation Basics" and
"Particle Dynamics" are relevant to our programming assignment.

Josh Barnes,
Univ. of Hawaii,
astrophysics videos, pictures, and software

Eric Weisstein's encyclopedia of mathematics
has definitions of mathematical terms,
pictures of spherical harmonics.

Stephen Wong's Multipole Diagrams

Using Particles to Sample and Control Implicit Surfaces,
Andy Witkin and Paul Heckbert, SIGGRAPH '94,
method that uses Gaussian potential (short range forces)
to make particles repel, for interactive surface design.

how big is N?

other nbody links,
my collection  links that I found less valuable

Cosmic Voyage:
IMAX movie containing simulation of colliding galaxies.
Found these using
AltaVista
advanced search
with query:
"cosmic voyage" and imax and galax* and
(image:.jpg or image:.jpeg or image:.gif)

Multigrid

MGNet
multigrid repository
(papers, newsletters, code).
Note: the old mgnet URL, http://na.cs.yale.edu/mgnet/www/mgnet.html,
is defunct.

SELHPC Article Archive
collection of papers.
The London & SouthEast centre for High Performance Computing
(HPC, computational math, vision, multigrid, misc)

Multigrid Algorithm Library,
Augsburg, Germany

my collection of mesh generation links
(most of these only peripherally related to multigrid)

Shlomo Ta'asan
in CMU's Math Department does multigrid research.

Recommended additional reading:

The book
Applied Numerical Linear Algebra
by James Demmel has a section on multigrid.
(nice brief explanation of multigrid, with comparison to
other iterative methods for linear systems)

Achi Brandt,
The Weizmann Insitute Research in Multilevel Computation:
1988 Report, Proc. Copper Mtn. Conf. on Multigrid Methods,
1989, 53 pp.
(covers many applications, advanced & fastmoving article,
but thoughtprovoking; not in CMU E&S library)

A. Brandt,
Guide to multigrid development,
Multigrid Methods,
W. Hackbusch and U. Trottenberg, eds.,
1982,
pp. 220312.
(long; gives rules of thumb for multigrid tuning;
in CMU E&S library)

The
Numerical Recipes
book is available online!
See section 19.6:
Multigrid Methods for Boundary Value Problems.
(terse; has code)

Wavelets

U. of Washington wavelet info

Web Links and Tutorials on Wavelets,
collected by Amara Graps,
graduate student in Heidelberg, Germany

Wavelet NetCare,
wavelet info at Washington University, St. Louis

engineering mathematics links (wavelets+),
from the
Edinburgh Engineering Virtual Library (EEVL)

The paper
Hierarchical and Variational Geometric Modeling with Wavelets,
Steven J. Gortler and Michael F. Cohen,
1995 Symposium on Interactive 3D Graphics,
is available from
Cohen's web page.
That paper is based on chapter 7 of
Gortler's PhD thesis.

Wim Sweldens,
Bell Labs,
inventor of "lifting" scheme for wavelet construction

Peter Schroeder,
Caltech,
subdivision surfaces and wavelets

other wavelet links,
my collection  links that I found less valuable

Miscellaneous

NA Digest,
archive of articles on numerical analysis
(do search for "multigrid", for example)
Paul Heckbert, Oct. 1998