And Cristian C. Bordeianu

Rubin H. Landau, Manuel J. Paez,and Cristian C. BordeianuComputational PhysicsProblem Solving with Computers2nd, Revised and Enlarged EditionBICENTENNIAL18 O7 WILEY2 OO7WILEY-VCH Verlag GmbH & Co. KGaA

Contents1Introduction1.11.2Computational Physics and Computational ScienceHow to Use this Book 312Computing Software 102.112.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 UOver/Underflows Exercise 20Machine Precision 21Determine Your Machine Precision 23Structured Program Design 24Summing Series 26Numeric Summation 26Good and Bad Pseudocode 27Assessment 2773Errors and Uncertainties in Computations3.13.23.33.43.5Living with Errors 29Types of Errors 29Model for Disaster: Subtractive Cancellation 32Subtractive Cancellation Exercises 32Model for Roundoff Error Accumulation 3429Computationyal Physics. Problem Solving with Computers (2nd edn).Rubin H. Landau, Manuel Jose Paez, Cristian C. BordeianuCopyright 2007 WILEY-VCH Verlag GmbH & Co. KGaA, WeinheimISBN: 978-3-527-40626-5

VIIIContents3.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 4.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 ID Motion, unimld.cpp 48Uniform Motion in ID, Class UmlD 49Implementation: Uniform Motion in 2D, Child Um2D,unimot2d.cpp 50Class Um2D: Uniform Motion in 2D 51Implementation: Projectile Motion, Child Accm2D, accm2d.cpp 53Accelerated 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 72596Differentiation6.16.26.36.46.5Problem 1: Numerical Limits 75Method: Numeric 75Forward Difference 75Central Difference 76Extrapolated Difference 777545

Contents6.66.76.86.8.1Error Analysis 78Error Analysis (Implementation and Assessment) 79Second Derivatives 80Second Derivative Assessment 807Trial and Error Searching7.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 o Masses on a String 90Statics 91Multidimensional Newton-Raphson Searching 92Classes of Matrix Problems 95Practical Aspects of Matrix Computing 96Implementation: Scientific Libraries, WWW 200Exercises for Testing Matrix Calls 206Matrix Solution of Problem 108Explorations 10881899Data .4.19.4.29.4.39.4.49.4.59.59.5.19.5.2Fitting Experimental Spectrum 111Lagrange Interpolation 112Lagrange Implementation and Assessment 224Explore Extrapolation 2 26Cubic Splines 126Spline Fit of Cross Section 118Fitting Exponential Decay 220Theory to Fit 220Theory: Probability and Statistics 222Least-Squares Fitting 224Goodness of Fit 226Least-Squares Fits Implementation 226Exponential Decay Fit Assessment 228Exercise: Fitting Heat Flow 229Nonlinear Fit of Breit-Wigner to Cross Section 230Appendix: Calling LAPACK from C 232Calling LAPACK Fortran from C 234Compiling C Programs with Fortran Calls 234/11IX

XContents10Deterministic Randomness10.110.1.110.1.210.1.3Random Sequences 137Random-Number Generation 238Implementation: Random Sequence 140Assessing Randomness and Uniformity 14113711Monte Carlo Applications74511.1A Random Walk 24511.1.1 Simulation 14511.1.2 Implementation: Random Walk 14711.2Radioactive Decay 14811.2.1 Discrete Decay 14811.2.2 Continuous Decay 15011.2.3 Simulation 25011.3Implementation and Visualization 25111.4Integration by Stone Throwing 15211.5Integration by Rejection 15311.5.1 Implementation 15411.5.2 Integration by Mean Value 25411.6High-Dimensional Integration 25511.6.1 Multidimensional Monte Carlo 25611.6.2 Error in N-D Integration 25611.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 16211.7.5 Nonuniform Assessment 26312Thermodynamic Simulations: Ising tistical Mechanics 265An Ising Chain (Model) 266Analytic Solutions 169The Metropolis Algorithm 269Implementation 273Equilibration 173Thermodynamic Properties 175Beyond Nearest Neighbors and ID 177165

Contents13Computer Hardware Basics: Memory and CPU13.113.1.113.213.2.113.2.2High-Performance Computers 179Memory Hierarchy 280The Central Processing Unit 284CPU Design: RISC 285Vector Processor 2867 7914High-Performance Computing: Profiling and 14.2.214.2.3Rules for Optimization 289Programming for Virtual Memory 290Optimizing Programs; Java vs. Fortran/C 290Good, Bad Virtual Memory Use 292Experimental Effects of Hardware on PerformanceJava versus Fortran/C 295Programming for Data Cache 203Exercise 1: Cache Misses 204Exercise 2: Cache Flow 204Exercise 3: Large Matrix Multiplication 20515Differential Equation Applications15.115.215.315 5.815.915.1015.10.115.10.215.1115.11.1I. Free Nonlinear Oscillations 207Nonlinear Oscillator 208Math: Types of Differential Equations 209Dynamical Form for ODEs 222ODE Algorithms 223Euler's Rule 225Runge-Kutta Algorithm 225Assessment: rk2 v. rk4 v. rk45 222Solution for Nonlinear Oscillations 223Precision Assessment: Energy Conservation 224Extensions: Nonlinear Resonances, Beats and Friction 225Friction: Model and Implementation 225Resonances and Beats: Model and Implementation 226Implementation: Inclusion of Time-Dependent Force 226U N I T II. Balls, not Planets, Fall Out of the Ski/ 228Theory: Projectile Motion with Drag 228Simultaneous Second Order ODEs 229Assessment 230Exploration: Planetary Motion 232Implementation: Planetary Motion 232UNIT189293207XI

XIIContents16Quantum Eigenvalues via ODE Matching 23516.116.1.116.1.216.1.316.1.4Theory: The Quantum Eigenvalue Problem 236Model: Nucleon in a Box 236Algorithm: Eigenvalues via ODE Solver Search 238Implementation: ODE Eigenvalues Solver 242Explorations 24317Fourier Analysis of Linear and Nonlinear Signals 917.1017.11Harmonics of Nonlinear Oscillations 245Fourier Analysis 246Example 1: Sawtooth Function 248Example 2: Half-Wave Function 249Summation of Fourier Series(Exercise) 250Fourier Transforms 250Discrete Fourier Transform Algorithm (DFT) 252Aliasing and Antialiasing 257DFT for Fourier Series 259Assessments 260DFT of Nonperiodic Functions (Exploration) 262Model Independent Data Analysis 0 262Assessment 26418Unusual Dynamics of Nonlinear Systems 618.7The Logistic Map 267Properties of Nonlinear Maps 269Fixed Points 269Period Doubling, Attractors 270Explicit Mapping Implementation 272Bifurcation Diagram 272Implementation 273Visualization Algorithm: Binning 274Random Numbers via Logistic Map 275Feigenbaum Constants 276Other Maps 27619Differential Chaos in Phase Space19.119.219.2.119.2.219.2.319.319.3.1Problem: A Pendulum Becomes Chaotic (Differential Chaos) 277Equation of Chaotic Pendulum 278Oscillations of a Free Pendulum 279Pendulum's "Solution" as Elliptic Integrals 280Implementation and Test: Free Pendulum 280Visualization: Phase-Space Orbits 282Chaos in Phase Space 285277

Contents19.3.219.419.519.619.7Assessment in Phase Space 28bAssessment: Fourier Analysis of Chaos 288Exploration: Bifurcations in Chaotic Pendulum 290Exploration: Another Type of Phase-Space Plot 291Further Explorations 29220Fractals 0.6.420.7Fractional Dimension 293The Sierpinski Gasket 294Implementation 295Assessing Fractal Dimension 295Beautiful Plants 297Self-Affine Connection 297Barnsley's Fern (fern.c) 298Self-Affinity in Trees (tree.c) 300Ballistic Deposition 302Random Deposition Algorithm (film.c) 301Length of British Coastline 303Coastline as Fractal 303Box Counting Algorithm 304Coastline Implementation 305Problem 5: Correlated Growth, Forests, and Films 306Correlated Ballistic Deposition Algorithm (column.c) 307Globular Cluster 308Diffusion-Limited Aggregation Algorithm (dla.c) 308Fractal Analysis of DLA Graph 320Problem 7: Fractals in Bifurcation Graph 32221Parallel Computing21.121.1.121.221.321.3.1Parallel Semantics 324Granularity 325Distributed Memory Programming 326Parallel Performance 327Communication Overhead 32931322Parallel Computing with MPI 32122.122.1.122.222.2.122.2.222.2.3Running on a Beowulf 322An Alternative: BCCD Your Cluster on a CD 32bRunning MPI 326MPI under a Queuing System 327Your First MPI Program 329MPIhello.c Explained 330XIII

2.522.5.122.5.222.622.7Send/Receive Messages 332Receive More Messages 333Broadcast Messages: MPIpi.c 334Exercise 336Parallel Tuning: TuneMPI.c 340A String Vibrating in Parallel 342MPIstring.c Exercise 345Deadlock 346Nonblocking Communication 347Collective Communication 347Supplementary Exercises 348List of MPI Commands 34923Electrostatics Potentials via Finite Differences (PDEs) 623.723.8PDE Generalities 352Electrostatic Potentials 353Laplace's Elliptic PDE 353Fourier Series Solution of PDE 354Shortcomings of Polynomial Expansions 356Solution: Finite Difference Method 357Relaxation and Over-Relaxation 359Lattice PDE Implementation 361Assessment via Surface Plot 362Three Alternate Capacitor Problems 363Implementation and Assessment 365Other Geometries and Boundary Conditions 36824Heat Flow 36924.124.224.324.424.4.124.5The Parabolic Heat Equation 369Solution: Analytic Expansion 370Solution: Finite Time Stepping (Leap Frog) 372von Neumann Stability Assessment 373Implementation 374Assessment and Visualization 37625PDE Waves on Strings and Membranes 37925.1The Hyperbolic Wave Equation 37925.1.1 Solution via Normal Mode Expansion 38225.1.2 Algorithm: Time Stepping (Leapfrog) 38225.1.3 Implementation 38625.1 A Assessment and Exploration 38625.1.5 Including Friction (Extension) 388

Contents25.1.625.225.325A25.5Variable Tension and Density 390Realistic ID Wave Exercises 391Vibrating Membrane (2D Waves) 392Analytical Solution 394Numerical Solution for 2D Waves 39626Solitons; KdeV and 6.8.126.8.226.8.326.8.426.8.5Chain of Coupled Pendulums (Theory) 399Wave Dispersion 400Continuum Limit, the SGE 402Analytic SGE Solution 403Numeric Solution: 2D SGE Solitons 4032D Soliton Implementation 406Visualization 408Shallow Water (KdeV) Solitons 409Theory: The Korteweg-de Vries Equation 420Analytic Solution: KdeV Solitons 422Algorithm: KdeV Soliton Solution 422Implementation: KdeV Solitons 423Exploration: Two KdeV Solitons Crossing 425Phase-Space Behavior 42539927Quantum Wave Packets 27.127.1.127.1.227.1.327.227.2.1Time-Dependent Schrodinger Equation (Theory) 427Finite Difference Solution 429Implementation 429Visualization and Animation 422Wave Packets Confined to Other Wells (Exploration) 422Algorithm for 2D Schrodinger Equation 42341728Quantum Paths for Functional Integration28.128.1.128.1.228.1.328.1.4Feynman's Space-Time Propagation 427Bound-State Wave Function 432Lattice Path Integration (Algorithm) 432Implementation 439Assessment and Exploration 44229Quantum Bound States via Integral Equations29.129.1.129.1.229.1.3Momentum-Space Schrodinger Equation 444Integral to Linear Equations 445Delta-Shell Potential (Model) 447Implementation 448427443XV