Parallel Algorithms in Scientific Computing and Many Body Problems

    Term: Spring 2003
    Course: G63.2011/G22.2945, Selected Topics in Numerical Analysis
    Day/Time: Thu, 9:30--11:20am

    Instructors:

    George Biros email: biros@cs.nyu.edu
    Bastiaan J. Braams email: braams@math.nyu.edu

    Class description

    We will cover the design, implementation and evaluation of selected algorithms in scientific computing with applications to the numerical solution of partial differential equations, and to numerical simulations in statistical physics and molecular dynamics.

    Topics

    • Introduction to parallel computing.
      Models of computation: PRAM, Vector, BSB Algorithmic primitives: scanning, searching, sorting Programming paradigms: MPI, OpenMP, HPF
    • Parallel linear algebra.
      Sparse and dense linear solvers, multigrid methods, preconditioned Krylov methods, Fast Fourier Transform.
    • Statistical physics.
      Monte Carlo approach for finding the lowest energy state and for evaluating thermodynamic properties of liquids and solids. Metropolis algorithm. Importance Sampling. Critical slowing down and methods to overcome it.
    • N-body algorithms.
      Barnes-Hut algorithm, Fast Multipole Method. Parallel implementation: graph partitioning and load balancing, non-uniform particle distributions and adaptivity.

    Recommended texts

    (intended to be on course reserve)
    • Joseph Jaja, "Introduction to Parallel Algorithms", Addison-Wesley, 1992
    • Leslie Greengard "The Rapid Evaluation of Potential fields in Particle Systems", MIT Press, 1988
    • Gregory Andrews: "Foundations of Multithreaded, Parallel, and Distributed Computing", Addison-Wesley, 1999.
    • K. Binder and D. W. Heermann, "Monte Carlo Simulation in Statistical Physics", Springer Verlag (4th edition, 2002).
    • Daan Frenkel and Berend Smit, "Understanding Molecular Simulation", 2nd Ed., Academic Press, 2001.
    • J. M. Thijssen, "Computational Physics", Cambridge Univ. Press, 1999.

    Prerequisite

    Numerical analysis

    Lectures

    Jan 23 G,B Introduction pdf
    30 G Algorithmic Primitives
    Feb 07 B Shared memory programming I
    14 B Shared memory programming II
    21 B Shared memory programming III
    28 G MPI library programmingpdf
    Mar 06 G N-body algorithms, Fundamentals
    13 G N-body algorithms, Data structures/Algorithms
    27 G N-body algorithms, Particle-Cell methods
    Apr 03 B Multigrid
    10 G Dense and Sparse Linear Algebra
    17 B Monte Carlo simulations
    24 B Ising model
    May 01 G,B TBA

    Readings

    • First chapter Jaja.
    • "A fast algorithm for particle simulations", L. Greengard and V. Rokhlin, Journal of Computational Physics 73, 325--348, 1987
    • "A fast adaptive multipole algorithm in three dimensions", H. Cheng, L. Greengard, V. Rokhlin, Journal of Computational Physics 155, 468--498, 1999

    Resources