15-859E: Hierarchical Methods for Simulation

Instructor: Paul Heckbert, ph@cs.cmu.edu, Doherty 4301A, phone 8-7899, meetings by appointment (please phone or email)

Time: TR 10:30-11:50
First class is 15 Sept., last class is 3 Dec. (First class meets on Sept. 15, three weeks into the semester, because of the CS immigration course.)
Place: Wean 5409A

Description: This course will cover hierarchical methods for simulating physical phenomena. In recent years, the development of n-body 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.

Primary emphasis will be on scientific computing, that is algorithms, data structures, and mathematics; but application problems from science and engineering will also be studied to motivate and test the ideas, and methods from graphics will be used for visualization. Although the registrar lists the full title of the course as "Advanced Topics in Theory: Hierarchical Methods for Simulation", this is a practically-oriented, not theory-oriented, course.

Audience: The course is intended for graduate students interested in scientific computing of any form, including students in computer science (e.g. graphics, robotics, algorithms), and students in other areas of science and engineering. Advanced undergraduates may also take the course, with permission of the instructor.

Prerequisites: Undergraduate classes in algorithms (e.g. 15-212) and linear algebra, and some knowledge of C++. Knowledge of calculus (partial differential equations) and basic Newtonian physics.

Textbooks and Readings:

• A Multigrid Tutorial by William Briggs.
• Wavelets for Computer Graphics by Eric Stollnitz, Tony DeRose, David Salesin.
• For a good book on C++, I recommend C++ Primer by Stanley Lippmann (optional).
• Additional material (research papers, lecture notes) will be photocopied and distributed, or available on the web. We will typically read one or two papers each week.

Grading:

• programming assignments: N-Body Algorithm, Wavelets, and possibly a third.
• midterm or written homework
• class participation
• oral presentation of readings during the semester (one or two talks per student of about 20 minutes each)
• research project at end of semester (talk and paper)

Programming assignments can be done in C++, C, Java, or almost any other language. Starter code in C++ will be provided for most assignments. Where necessary, this code will use Xforms for user interface and OpenGL for graphics, but students are free to use other libraries and systems, e.g. tk, fltk, DirectX, Maple, Matlab, or Mathematica. See the summary of software libraries for the class. We will discuss and implement sequential, not parallel, algorithms, mostly.

If you need a public machine, Suns with 24 bit graphics are in Wean 5201, PC's running Linux are in Wean 5203, and SGI Indy's are in Wean 5205. See the Wean cluster information. There are also some more powerful SGI machines (Octanes) in the College of Fine Arts building.

Students are expected to do the programming by themselves unless group collaboration or use of public software is approved by the instructor. Late policy: 14% off per school day late (weekends aren't on the clock).

Syllabus (tentative)

• N-Body Problem (about 5 meetings)
  • applications: gravity, astrophysics, electrostatics, surface design, thermal radiation
  • brute force O(n^2) algorithm
  • Barnes-Hut algorithm
  • quadtrees and octrees
  • Greengard-Rokhlin (fast multipole) algorithm
  • (possibly) newer methods such as Callahan-Kosaraju
• Multigrid Methods (about 4 meetings)
  • applications: heat diffusion, tents, image warping, variational methods in computer vision
  • review: elliptic partial differential equations (PDE's)
  • finite difference method
  • straightforward solution with a single grid
  • pyramids
  • solution with multigrid
  • multigrid on unstructured meshes
• Wavelets (about 6 meetings)
  • applications: compression, surface modeling, image storage, PDE's for heat diffusion or computer animation (spacetime constraints), integral equations for thermal radiation or graphics
  • review of basis functions
  • orthogonality and scale
  • Haar and higher order wavelets
  • tensor-product wavelets in multi-dimensional space
  • wavelets on surfaces of general topology
  • wavelets on unstructured meshes
• Miscellaneous (about 2 meetings)
  • topics to be determined
• Project Reports (about 3 meetings)

There is a news group for the class, cmu.cs.class.cs859e, that students are invited to read and contribute to. It will be particularly useful for programming assignments.

Registrar's info about this course

Related courses at CMU