15-859E: Hierarchical Methods for Simulation

Instructor: Paul Heckbert

Time: TR 10:30-11:50, First class is 15 Sept., last class is 4 Dec. 1998
Place: Wean 5409A

Shortcuts: schedule ; links on n-body , multigrid , wavelets

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.

• Guests are welcome to come to the project presentations 1-4 December (schedule)
• 17 Nov: See the tips for presentations and report, below.
• Written reports are due 4 December.
• Old announcements are here.

Class Resources

• Administrative Info
• n-body assignment, due 5 Oct.
• multigrid assignment, due 21 Oct.
• wavelet assignment, due 2 Nov.
• project handout, proposal due 5 Nov. tips for presentations and written report.
• software libraries used in this course
• pictures we've created in this course

Schedule

• T 15 Sept.: Summary of course, introduction to n-body problem.

• R 17 Sept.: Simple n-body algorithms. Grant Brommel presents paper: An Efficient Program for Many-Body Simulation, Andrew Appel, SIAM J. Sci. Stat. Comput., Jan. 1985.; Frank Dellaert presents paper: A hierarchical O(NlogN) force-calculation 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. N-body programming assignment out.

• R 24 Sept.: Logistics of n-body assignment (compiling, linking), potential laws for 2-D and 3-D, 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 n-body lecture. Application of n-body methods to radiosity (graphics) and surface modeling (see Witkin paper below). Testing n-body 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' n-body 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. 1165-1172.
  Lecture Notes: Survey of Multigrid Applications: 2-up postscript (good for printing), pdf (full-page - good for reading on-screen), postscript (full-page) .

• 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 n-body 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 n-body 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:40-2: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

Links to Information

• N-Body Problem
  • why is space three-dimensional? Max Tegmark's thoughts
  • Web Links and Tutorials on N-Body / Particle Simulation Methods, collected by Amara Graps, graduate student in Heidelberg, Germany
  • Tree Codes for N-Body Simulations tutorial, section of the book Parallel Computing Works, on work done at the Caltech Concurrent Computation Program
  • Lectures by Jim Demmel, Berkeley, on Barnes-Hut and Greengard algorithms.
  • Links on N-Body Algorithms, collected by Guy Blelloch for "Algorithms in the Real World" course
  • Girija Narlikar and Guy Blelloch's n-body 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 n-body 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 n-body 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)
    • Cosmic Voyage home page, has quicktime videos
    • UIUC info on movie - lots of links
    • text about movie
    • stills of galaxy collision
    • IMAX Corp info
• Multigrid
  • MGNet multigrid repository (papers, newsletters, code). Note: the old mgnet URL, http://na.cs.yale.edu/mgnet/www/mgnet.html, is defunct.
  • SEL-HPC Article Archive collection of papers. The London & South-East 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 & fast-moving article, but thought-provoking; not in CMU E&S library)
    • A. Brandt, Guide to multigrid development, Multigrid Methods, W. Hackbusch and U. Trottenberg, eds., 1982, pp. 220-312. (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