Find this at http://www.npac.syr.edu/users/gcf/cps615E/

CPS615 Foils -- set E: ODE's and Particle Dynamics

This uses the simple O(N2) Particle Dynamics Problem as a motivator to discuss solution of ordinary differential equations

We discuss Euler, Runge Kutta and predictor corrector methods

The simple data parallel O(N2) algorithm is given in Fortran90 and HPF

The better Pipeline version is also given

We analyse Performance

Table of Contents for CPS615 Foils -- set E: ODE's and Particle Dynamics

001 CPS 615 -- Computational Science in
    Simulation Track
    Data Parallel Module on ODE's and Particle Dynamics
    October 23, 1995
    Updated Oct 11,1996
002 Abstract of Data Parallel ODE and Particle Dynamics Module  
003 Particle (N-Body) Applications and Ordinary Differential Equations
     (ODE's)
004 Particle Applications - Ordinary Differential Equations (ODE's)
005 Particle Applications - the N-body problem
006 Newton's First Law -- The Gravitational Force on a Particle
007 Equations of Motion -- Newton's Second Law
008 Numerical techniques for solving ODE's
009 Second and Higher Order Equations
010 Basic Discretization of Single First Order Equation
011 Errors in numerical approximations 
012 Runge-Kutta Methods: Euler's method
013 Estimate of Error in Euler's method
014 Relationship of Error to Computation
015 Example using Euler's method from the CSEP book
016 Approximate solutions at t=1,using Euler's method with different 
    values of h
017 Runge-Kutta Methods: Modified Euler's method
018 Approximate solutions of the ODE for et at t=1, using modified 
    Euler's method with different values of h
019 The Classical Runge-Kutta -- In Words
020 The Classical Runge-Kutta -- Formally
021 The Classical Runge-Kutta Pictorially
022 Predictor / Corrector Methods
023 Definition of Multi-step methods
024 Features of Multi-Step Methods
025 Comparison of Explicit and Implicit Methods
026 Solving the N-body equations of motion
027 Representing the Data Parallel N-Body problem
028 Form of the Computation -- Data v. Message Parallel
029 N-body Runge Kutta Routine in Fortran90 - I
030 Runge Kutta Routine in Fortran90 - II
031 Computation of accelerations - a simple parallel array algorithm
032 Simple Data Parallel Version of N Body Force Computation -- Grav 
    -- I
033 The Grav Function in Data Parallel Algorithm - II
034 Some Inefficiencies of the Data Parallel N2 Algorithm - I
035 Some Inefficiencies of the Data Parallel N2 Algorithm - II
036 Better Data Parallel Pipeline Algorithm for Computation of 
    Accelerations,
    taking 1/2 the time for iterations over force computation 
037 Data Parallel Pipeline Algorithm in detail
038 Basic Data Parallel pipeline operation
039 Examples of Data Parallel Pipeline Algorithm
040 Data Parallel Pipeline Algorithm Grav -- Part I
041 Data Parallel Pipeline Algorithm for Grav -- Part II
042 Data Parallel Grav Pipeline Algorithm, concluded
043 Data Parallel Parallel Decomposition
044 Data Parallel Parallel Execution Time -I
045 Data Parallel Parallel Execution Time -II
046 N-body Problem is a one dimensional Algorithm
047 Excerpts from an HPF program for this algorithm
048 HPF program excerpts - II
049 HPF program excerpts - finished
050 Notes and References
051 CPS 615 -- Computational Science in
    Simulation Track
    Message Parallel Module on ODE's and Particle Dynamics
    October 20, 1997
052 Abstract of Message Parallel ODE and Particle Dynamics 
053 Summary of Parallel N-Body Programming Methods and Algorithms
054 Status of Parallelism in Various N Body Cases
055 Other N-Body Like Problems - I
056 Other N-Body Like Problems - II
057 Essential Structure of Message Parallel O(N2) Algorithm - I
058 Essential Structure of Message Parallel O(N2) Algorithm - II
059 Structure of Runge Kutta Phases
060 The 9 Fortran Phases in Runge Kutta Update
061 Features of Message Parallel Computation
062 Message Parallel Force Computation MPGrav
063 Very Bad Naive Message Parallel Algorithm
064 Features of Very Bad Naive Message Parallel Algorithm
065 Much Better Message Parallel Algorithm
066 Blocking of Messages
067 Compilers, Caches and Data Locality
068 Communication and Computation Complexity
069 Best Message Parallel N Body Algorithm - I
070 Best Message Parallel N Body Algorithm - II
071 Choice of Place to Compute Fi,j
072 Final Remarks on Best Algorithm
073 CPS 615 -- Computational Science in
    Simulation Track
    Data Parallel Module on ODE's and Particle Dynamics
    February 20, 1998
074 Abstract of Message Parallel ODE and Particle Dynamics 
075 Representing the Message Parallel N-Body problem
076 Form of the Computation -- Message Parallel
077 Pipeline Algorithm in detail
078 Basic Message Parallel pipeline operation
079 Examples of Message Parallel Pipeline Algorithm
080 Factor of Two in the Parallel O(N2) Algorithm