WIXLIB

Rubin H. Landau, Manuel J. Päez,and Cristian C. BordeianuComputational PhysicsProblem Solving with Computers2nd, Revised and Enlarged EditionBICENTENN I AL.JElAZ1 807 n.leWILEY 7J.;,' 2007ZDBICENTENNIALrWILEY-VCH Verlag GmbH & Co. KGaA

I vHContents1Introduction 11.11.2Computational Physics and Computational Science 1How to Use this Book 32Computing Software Basics 12.122.132.142.15Making Computers Obey 7Computer Languages 7Programming Warmup 9Java-Scanner Implementation 10C Implementation 11Fortran Implementation 12Shells, Editors, and Programs 12Limited Range and Precision of Numbers 13Number Representation 13IEEE Floating Point Numbers 14Over/Underflows Exercise 20Machine Precision 21Determine Your Machine Precision 23Structured Program Design 24Summing Series 26Numeric Summation 26Good and Bad Pseudocode 27Assessment 273Errors and Uncertainties in Computations 29Living with Errors 293.13.23.33.43.5Types of Errors 29Model for Disaster: Subtractive Cancellation 31Subtractive Cancellation Exercises 32Model for Roundoff Error Accumulation 34Computationyal Physics. Problem Solving with Computers (2nd edn).Rubin H. Landau, Manuel Josi Paez, Cristian C. BordeianuCopyright 2007 WILEY-VCH Verlag GmbH & Co. KGaA, WeinheimISBN: 978-3-527-40626-5

VIIII Contents3.63.73.83.93.103.113.12Errors in Spherical Bessel Functions (Problem) 35Numeric Recursion Relations (Method) 35Implementation and Assessment: Recursion Relations 37Experimental Error Determination 39Errors in Algorithms 39Minimizing the Error 41Error Assessment 424Object-Oriented Programming: Kinematics 04.14.24.2.14.34.44.54.5.14.5.2Problem: Superposition of Motions 45Theory: Object-Oriented Programming 45OOP Fundamentals 46Theory: Newton's Laws, Equation of Motion 46OOP Method: Class Structure 47Implementation: Uniform 1D Motion, unimld.cpp 48Uniform Motion in 1D, Class Um1D 49Implementation: Uniform Motion in 2D, Child Um2D,unimot2d.cpp 50Class Um2D: Uniform Motion in 2D 51Implementation: Projectile Motion, Child Accm2D, accm2d.cppAccelerated Motion in Two Directions 54Assessment: Exploration, shms.cpp 5.6.15.6.25.75.85.9Problem: Integrating a Spectrum 59Quadrature as Box Counting (Math) 59Algorithm: Trapezoid Rule 61Algorithm: Simpson's Rule 63Integration Error 65Algorithm: Gaussian Quadrature 66Mapping Integration Points 68Gauss Implementation 69Empirical Error Estimate (Assessment) 71Experimentation 72Higher Order Rules 72596Differentiation 756.16.26.36.46.5Problem 1: Numerical Limits 75Method: Numeric 75Forward Difference 75Central Difference 76Extrapolated Difference 774553

Contents IIX6.66.76.86.8.1Error Analysis 78Error Analysis (Implementation and Assessment) 79Second Derivatives 80Second Derivative Assessment 807Triel and Error Searching 817.17.27.2.17.37.3.17.3.2Quantum States in Square Well 81Trial-and-Error Root Finding via Bisection Algorithm 83Bisection Algorithm Implementation 84Newton-Raphson Algorithm 84Newton-Raphson with Backtracking 86Newton-Raphson Implementation 878Matrix Computing and N-D Newton Raphson 898.18.1.18.1.28.28.2.18.2.28.2.38.2.48.2.5Two Masses an a String 90Statics 91Multidimensional Newton-Raphson Searching 92Classes of Matrix Problems 95Practical Aspects of Matrix Computing 96Implementation: Scientific Libraries, WWW 100Exercises for Testing Matrix Calls 106Matrix Solution of Problem 108Explorations 1089Data Fitting 9.4.29.4.39.4.49.4.59.59.5.19.5.2Fitting Experimental Spectrum 111Lagrange Interpolation 112Lagrange Implementation and Assessment 114Explore Extrapolation 116Cubic Splines 116Spline Fit of Cross Section 118Fitting Exponential Decay 120Theory to Fit 120Theory: Probability and Statistics 121Least-Squares Fitting 124Goodness of Fit 126Least-Squares Fits Implementation 126Exponential Decay Fit Assessment 128Exercise: Fitting Heat Flow 129Nonlinear Fit of Breit-Wigner to Cross Section 130Appendix: Calling LAPACK from C 132Calling LAPACK Fortran from C 134Compiling C Programs with Fortran Calls 134

XI ContentsDeterministic Randomness 13710Random Sequences 13710.110.1.1 Random-Number Generation 13810.1.2 Implementation: Random Sequence 14010.1.3 Assessing Randomness and Uniformity 141Monte Carlo Applications 14511A Random Walk 14511.111.1.1 Simulation 14511.1.2 Implementation: Random Walk 147Radioactive Decay 14811.211.2.1 Discrete Decay 14811.2.2 Continuous Decay 15011.2.3 Simulation 150Implementation and Visualization 15111.3Integration by Stone Throwing 15211.411.5Integration by Rejection 15311.5.1 Implementation 15411.5.2 Integration by Mean Value 15411.6High-Dimensional Integration 15511.6.1 Multidimensional Monte Carlo 15611.6.2 Error in N-D Integration 15611.6.3 Implementation: 10D Monte Carlo Integration 15711.7Integrating Rapidly Varying Functions 0 15711.7.1 Variance Reduction 0 (Method) 15711.7.2 Importance Sampling 0 15811.7.3 Implementation: Nonuniform Randomness 0 15811.7.4 von Neumann Rejection 0 16211.7.5 Nonuniform Assessment 0 16312Thermodynamic Simulations: Ising Model 16512.1Statistical Mechanics 16512.2An Ising Chain (Model) 16612.2.1 Analytic Solutions 16912.3The Metropolis Algorithm 16912.3.1 Implementation 17312.3.2 Equilibration 17312.3.3 Thermodynamic Properties 17512.3.4 Beyond Nearest Neighbors and 1D 177

Contents IXI13Computer Hardware Basics: Memory and CPU 17913.1High-Performance Computers 17913.1.1 Memory Hierarchy 18013.2The Central Processing Unit 18413.2.1 CPU Design: RISC 18513.2.2 Vector Processor 18614High-Performance Computing: Profiling and Tuning 18914.1Rules for Optimization 18914.1.1 Programming for Virtual Memory 19014.1.2 Optimizing Programs; Java vs. Fortran/C 19014.1.3 Good, Bad Virtual Memory Use 19214.1.4 Experimental Effects of Hardware an Performance 19314.1.5 Java versus Fortran/C 195Programming for Data Cache 20314.214.2.1 Exercise 1: Cache Misses 20414.2.2 Exercise 2: Cache Flow 20414.2.3 Exercise 3: Large Matrix Multiplication 2051515.1Differential Equation Applications 207UNIT I. Free Nonlinear Oscillations 207Nonlinear Oscillator 208Math: Types of Differential Equations 20915.315.4Dynamical Form for ODEs 212ODE Algorithms 21315.5Euler's Rule 21515.5.115.5.2 Runge-Kutta Algorithm 21515.5.3 Assessment: rk2 v. rk4 v. rk45 221Solution for Nonlinear Oscillations 22315.615.6.1 Precision Assessment: Energy Conservation 224Extensions: Nonlinear Resonances, Beats and Friction 22515.715.7.1 Friction: Model and Implementation 22515.7.2 Resonances and Beats: Model and Implementation 226Implementation: Inclusion of Time-Dependent Force 22615.8UNIT II. Balls, not Planets, Fall Out of the Sky 22815.915.10 Theory: Projectile Motion with Drag 22815.10.1 Simultaneous Second Order ODEs 22915.10.2 Assessment 230Exploration: Planetary Motion 23115.1115.11.1 Implementation: Planetary Motion 23215.2

XII ContentsQuantum Eigenvalues via ODE Matching 23516Theory: The Quantum Eigenvalue Problem 23616.116.1.1 Model: Nucleon in a Box 23616.1.2 Algorithm: Eigenvalues via ODE Solver Search 23816.1.3 Implementation: ODE Eigenvalues Solver 24216.1.4 Exploration 243Fourier Analysis of Linear and Nonlinear Signals 24517Harmonics of Nonlinear Oscillations 24517.1Fourier Analysis 24617.217.2.1 Example 1: Sawtooth Function 24817.2.2 Example 2: Half-Wave Function 249Summation of Fourier Series(Exercise) 25017.3Fourier Transforms 25017.4Discrete Fourier Transform Algorithm (DFT) 25217.5Aliasing and Antialiasinge 25717.6DFT for Fourier Series 25917.7Assessments 26017.8DFT of Nonperiodic Functions (Exploration) 26117.917.10 Model Independent Data Analysis 0 26217.11Assessment 26418Unusual Dynamics of Nonlinear Systems 26718.1The Logistic Map 26718.2Properties of Nonlinear Maps 26918.2.1 Fixed Points 26918.2.2 Period Doubling, Attractors 27018.3Explicit Mapping Implementation 27118.4Bifurcation Diagram 27218.4.1 Implementation 27318.4.2 Visualization Algorithm: Binning 27418.5Random Numbers via Logistic Map 27518.6Feigenbaum Constants 27618.7Other Maps 27619Differential Chaos in Phase Space 27719.1Problem: A Pendulum Becomes Chaotic (Differential Chaos) 27719.2Equation of Chaotic Pendulum 27819.2.1 Oscillations of a Free Pendulum 27919.2.2 Pendulum's "Solution" as Elliptic Integrals 28019.2.3 Implementation and Test: Free Pendulum 28019.3Visualization: Phase-Space Orbits 28219.3.1 Chaos in Phase Space 285

Contents 'XIII19.3.2 Assessment in Phase Space 28619.4Assessment: Fourier Analysis of Chaos 28819.5Exploration: Bifurcations in Chaotic Pendulum 29019.6Exploration: Another Type of Phase-Space Plot 29119.7Further Explorations 29120Fractals 29320.1Fractional Dimension 29320.2The Sierpiriski Gasket 29420.2.1 Implementation 29520.2.2 Assessing Fractal Dimension 29520.3Beautiful Plants 29720.3.1 Self-Affine Connection 29720.3.2 Barnsley's Fern (fern.c) 29820.3.3 Self-Affinity in Trees (tree.c) 30020.4Ballistic Deposition 30120.4.1 Random Deposition Algorithm (film.c) 30120.5Length of British Coastline 30320.5.1 Coastline as Fractal 30320.5.2 Box Counting Algorithm 30420.5.3 Coastline Implementation 30520.6Problem 5: Correlated Growth, Forests, and Films 30620.6.1 Correlated Ballistic Deposition Algorithm (column.c) 30720.6.2 Globular Cluster 30820.6.3 Diffusion-Limited Aggregation Algorithm (dla.c) 30820.6.4 Fractal Analysis of DLA Graph 31020.7Problem 7: Fractals in Bifurcation Graph 31121Parallel Computing 313Parallel Semantics 314Granularity 31521.121.1.121.2Distributed Memory Programming 31621.3Parallel Performance 31721.3.1 Communication Overhead 31922Parallel Computing with MPI 321Running on a Beowulf 32222.122.1.1 An Alternative: BCCD Your Cluster on a CD 326Running MPI 32622.222.2.1 MPI under a Queuing System 32722.2.2 Your First MPI Program 32922.2.3 MPlhello.c Explained 330

XIV I Contents22.2.4 Send/Receive Messages 33222.2.5 Receive More Messages 33322.2.6 Broadcast Messages: MPIpi.c 33422.2.7 Exercise 336Parallel Tuning: TuneMPI.c 34022.3A String Vibrating in Parallel 34222.422.4.1 MPlstring.c Exercise 345Deadlock 34622.522.5.1 Nonblocking Communication 34722.5.2 Collective Communication 347Supplementary Exercises 34822.6List of MPI Commands 34922.723Electrostatics Potentials via Finite Differences (PDEs) 351PDE Generalities 35123.123.2Electrostatic Potentials 35323.2.1 Laplace's Elliptic PDE 353Fourier Series Solution of PDE 35423.323.3.1 Shortcomings of Polynomial Expansions 35623.4Solution: Finite Difference Method 35723.4.1 Relaxation and Over-Relaxation 35923.4.2 Lattice PDE Implementation 36123.5Assessment via Surface Plot 36223.6Three Alternate Capacitor Problems 36323.7Implementation and Assessment 36523.8Other Geometries and Boundary Conditions 36824Heat Flow 36924.1The Parabolic Heat Equation 36924.2Solution: Analytic Expansion 37024.3Solution: Finite Time Stepping (Leap Frog) 37124.4von Neumann Stability Assessment 37324.4.1 Implementation 37424.5Assessment and Visualization 37625PDE Waves an Strings and Membranes 37925.1The Hyperbolic Wave Equation 37925.1.1 Solution via Normal Mode Expansion 38125.1.2 Algorithm: Time Stepping (Leapfrog) 38225.1.3 Implementation 38625.1.4 Assessment and Exploration 38625.1.5 Including Friction (Extension) 388