Dedication V
Preface XIX
1 Introduction 1
1.1 Computational Physics and Computational Science 1
1.2 This Book’s Subjects 3
1.3 This Book’s Problems 4
1.4 This Book’s Language: The Python Ecosystem 8
1.5 Python’s Visualization Tools 13
1.6 Plotting Exercises 30
1.7 Python’s Algebraic Tools 31
2 Computing Software Basics 33
2.1 Making Computers Obey 33
2.2 ProgrammingWarmup 35
2.3 Python I/O 39
2.4 Computer Number Representations (Theory) 40
2.5 Problem: Summing Series 51
3 Errors and Uncertainties in Computations 53
3.1 Types of Errors (Theory) 53
3.2 Error in Bessel Functions (Problem) 58
3.3 Experimental Error Investigation 62
3.3.1 Error Assessment 65
4 Monte Carlo: Randomness, Walks, and Decays 69
4.1 Deterministic Randomness 69
4.2 Random Sequences (Theory) 69
4.3 RandomWalks (Problem) 75
4.4 Extension: Protein Folding and Self-Avoiding RandomWalks 79
4.5 Spontaneous Decay (Problem) 80
4.6 Decay Implementation and Visualization 84
5 Differentiation and Integration 85
5.1 Differentiation 85
5.2 Forward Difference (Algorithm) 86
5.3 Central Difference (Algorithm) 87
5.4 Extrapolated Difference (Algorithm) 87
5.5 Error Assessment 88
5.6 Second Derivatives (Problem) 90
5.7 Integration 91
5.8 Quadrature as Box Counting (Math) 91
5.9 Algorithm: Trapezoid Rule 93
5.10 Algorithm: Simpson’s Rule 94
5.11 Integration Error (Assessment) 96
5.12 Algorithm: Gaussian Quadrature 97
5.13 Higher Order Rules (Algorithm) 103
5.14 Monte Carlo Integration by Stone Throwing (Problem) 104
5.15 Mean Value Integration (Theory and Math) 105
5.16 Integration Exercises 106
5.17 Multidimensional Monte Carlo Integration (Problem) 108
5.18 Integrating Rapidly Varying Functions (Problem) 110
5.19 Variance Reduction (Method) 110
5.20 Importance Sampling (Method) 111
5.21 von Neumann Rejection (Method) 111
5.22 Nonuniform Assessment 113
6 Matrix Computing 117
6.1 Problem 3: N–D Newton–Raphson; Two Masses on a String 117
6.2 Why Matrix Computing? 122
6.3 Classes of Matrix Problems (Math) 122
6.4 Python Lists as Arrays 126
6.5 Numerical Python (NumPy) Arrays 127
6.6 Exercise: TestingMatrix Programs 134
7 Trial-and-Error Searching and Data Fitting 141
7.1 Problem 1: A Search for Quantum States in a Box 141
7.2 Algorithm: Trial-and-Error Roots via Bisection 142
7.3 Improved Algorithm: Newton–Raphson Searching 145
7.4 Problem 2: Temperature Dependence ofMagnetization 148
7.5 Problem 3: Fitting An Experimental Spectrum 150
7.6 Problem 4: Fitting Exponential Decay 156
7.7 Least-Squares Fitting (Theory) 158
7.8 Exercises: Fitting Exponential Decay, Heat Flow andHubble’s Law 162
8 Solving Differential Equations: Nonlinear Oscillations 171
8.1 Free Nonlinear Oscillations 171
8.2 Nonlinear Oscillators (Models) 171
8.3 Types of Differential Equations (Math) 173
8.4 Dynamic Form for ODEs (Theory) 175
8.5 ODE Algorithms 177
8.6 Runge–Kutta Rule 178
8.7 Adams–Bashforth–Moulton Predictor–Corrector Rule 183
8.8 Solution for Nonlinear Oscillations (Assessment) 187
8.9 Extensions: Nonlinear Resonances, Beats, Friction 189
8.10 Extension: Time-Dependent Forces 190
9 ODE Applications: Eigenvalues, Scattering, and Projectiles 193
9.1 Problem: Quantum Eigenvalues in Arbitrary Potential 193
9.2 Algorithms: Eigenvalues via ODE Solver + Search 195
9.3 Explorations 203
9.4 Problem: Classical Chaotic Scattering 203
9.5 Problem: Balls Falling Out of the Sky 208
9.6 Theory: Projectile Motion with Drag 208
9.7 Exercises: 2- and 3-Body Planet Orbits and Chaotic Weather 211
10 High-Performance Hardware and Parallel Computers 215
10.1 High-Performance Computers 215
10.2 Memory Hierarchy 216
10.3 The Central Processing Unit 219
10.4 CPU Design: Reduced Instruction Set Processors 220
10.5 CPU Design:Multiple-Core Processors 221
10.6 CPU Design: Vector Processors 222
10.7 Introduction to Parallel Computing 223
10.8 Parallel Semantics (Theory) 224
10.9 Distributed Memory Programming 226
10.10 Parallel Performance 227
10.11 Parallelization Strategies 230
10.12 Practical Aspects of MIMD Message Passing 231
10.13 Scalability 236
10.14 Data Parallelism and Domain Decomposition 239
10.15 Example: The IBM Blue Gene Supercomputers 243
10.16 Exascale Computing via Multinode-Multicore GPUs 245
11 Applied HPC: Optimization, Tuning, and GPU Programming 247
11.1 General Program Optimization 247
11.2 Optimized Matrix Programming with NumPy 251
11.3 Empirical Performance of Hardware 254
11.4 Programming for the Data Cache (Method) 262
11.5 Graphical Processing Units for High Performance Computing 266
11.5.1 The GPU Card 267
11.6 Practical Tips forMulticore and GPU Programming 267
12 Fourier Analysis: Signals and Filters 275
12.1 Fourier Analysis of Nonlinear Oscillations 275
12.2 Fourier Series (Math) 276
12.3 Exercise: Summation of Fourier Series 279
12.4 Fourier Transforms (Theory) 279
12.5 The Discrete Fourier Transform 281
12.6 Filtering Noisy Signals 290
12.7 Noise Reduction via Autocorrelation (Theory) 290
12.7.1 Autocorrelation Function Exercises 293
12.8 Filtering with Transforms (Theory) 294
12.9 The Fast Fourier Transform Algorithm 299
12.10 FFT Implementation 303
12.11 FFT Assessment 304
13 Wavelet and Principal Components Analyses: Nonstationary Signals and Data Compression 307
13.1 Problem: Spectral Analysis of Nonstationary Signals 307
13.2 Wavelet Basics 307
13.3 Wave Packets and Uncertainty Principle (Theory) 309
13.4 Short-Time Fourier Transforms (Math) 311
13.5 TheWavelet Transform 313
13.6 Discrete Wavelet Transforms, Multiresolution Analysis 317
13.7 Principal Components Analysis 332
14 Nonlinear Population Dynamics 339
14.1 Bug Population Dynamics 339
14.2 The Logistic Map (Model) 339
14.3 Properties of NonlinearMaps (Theory and Exercise) 341
14.4 Mapping Implementation 344
14.5 Bifurcation Diagram (Assessment) 345
14.6 Logistic Map Random Numbers (Exploration) 348
14.7 Other Maps (Exploration) 348
14.8 Signals of Chaos: Lyapunov Coefficient and Shannon Entropy 349
14.9 Coupled Predator–PreyModels 353
14.10 Lotka–Volterra Model 354
14.11 Predator–Prey Chaos 356
15 Continuous Nonlinear Dynamics 363
15.1 Chaotic Pendulum 363
15.2 Visualization: Phase-Space Orbits 367
15.3 Exploration: Bifurcations of Chaotic Pendulums 374
15.4 Alternate Problem: The Double Pendulum 375
15.5 Assessment: Fourier/Wavelet Analysis of Chaos 377
15.6 Exploration: Alternate Phase-Space Plots 378
15.7 Further Explorations 379
16 Fractals and Statistical Growth Models 383
16.1 Fractional Dimension (Math) 383
16.2 The Sierpin Gasket (Problem 1) 384
16.3 Growing Plants (Problem 2) 386
16.4 Ballistic Deposition (Problem 3) 390
16.5 Length of British Coastline (Problem 4) 391
16.6 Correlated Growth, Forests, Films (Problem 5) 395
16.7 Globular Cluster (Problem 6) 396
16.8 Fractals in Bifurcation Plot (Problem 7) 400
16.9 Fractals from Cellular Automata 400
16.10 Perlin Noise Adds Realism 402
16.11 Exercises 407
17 Thermodynamic Simulations and Feynman Path Integrals 409
17.1 Magnets via Metropolis Algorithm 409
17.2 An IsingChain (Model) 410
17.3 Statistical Mechanics (Theory) 412
17.4 Metropolis Algorithm 413
17.5 Magnets viaWang–Landau Sampling 420
17.6 Wang–Landau Algorithm 423
17.7 Feynman Path Integral Quantum Mechanics 429
17.8 Feynman’s Space–Time Propagation (Theory) 429
17.9 Exploration: Quantum Bouncer’s Paths 440
18 Molecular Dynamics Simulations 445
18.1 Molecular Dynamics (Theory) 445
18.2 Verlet and Velocity–Verlet Algorithms 451
18.3 1D Implementation and Exercise 453
18.4 Analysis 456
19 PDE Reviewand Electrostatics via Finite Differences and Electrostatics via Finite Differences 461
19.1 PDE Generalities 461
19.2 Electrostatic Potentials 463
19.2.1 Laplace’s Elliptic PDE (Theory) 463
19.3 Fourier Series Solution of a PDE 464
19.4 Finite-Difference Algorithm 467
19.5 Assessment via Surface Plot 471
19.6 Alternate Capacitor Problems 471
19.7 Implementation and Assessment 474
19.8 Electric Field Visualization (Exploration) 475
19.9 Review Exercise 476
20 Heat Flow via Time Stepping 477
20.1 Heat Flow via Time-Stepping (Leapfrog) 477
20.2 The Parabolic Heat Equation (Theory) 478
20.3 Assessment and Visualization 483
20.4 Improved Heat Flow: Crank–Nicolson Method 484
21 Wave Equations I: Strings and Membranes 491
21.1 A Vibrating String 491
21.2 The HyperbolicWave Equation (Theory) 491
21.3 Strings with Friction (Extension) 499
21.4 Strings with Variable Tension and Density 500
21.5 Vibrating Membrane (2DWaves) 504
21.6 Analytical Solution 505
21.7 Numerical Solution for 2DWaves 508
22 Wave Equations II: QuantumPackets and Electromagnetic 511
22.1 Quantum Wave Packets 511
22.2 Time-Dependent Schrodinger Equation (Theory) 511
22.3 Algorithm for the 2D Schrodinger Equation 517
22.4 Wave Packet–Wave Packet Scattering 518
22.5 E&MWaves via Finite-Difference Time Domain 525
22.6 Maxwell’s Equations 525
22.7 FDTD Algorithm 526
22.8 Application:Wave Plates 533
22.9 Algorithm 534
22.10 FDTD Exercise and Assessment 535
23 Electrostatics via Finite Elements 537
23.1 Finite-Element Method 537
23.2 Electric Field from Charge Density (Problem) 538
23.3 Analytic Solution 538
23.4 Finite-Element (Not Difference) Methods, 1D 539
23.5 1D FEMImplementation and Exercises 544
23.6 Extension to 2D Finite Elements 547
24 Shocks Waves and Solitons 555
24.1 Shocks and Solitons in ShallowWater 555
24.2 Theory: Continuity and Advection Equations 556
24.3 Theory: ShockWaves via Burgers’ Equation 559
24.4 Including Dispersion 562
24.5 Shallow-Water Solitons: The KdeV Equation 563
24.6 Solitons on Pendulum Chain 567
25 Fluid Dynamics 575
25.1 River Hydrodynamics 575
25.2 Navier–Stokes Equation (Theory) 576
25.3 2D Flow over a Beam 581
25.4 Theory: Vorticity Form of Navier–Stokes Equation 582
26 Integral Equations of QuantumMechanics 591
26.1 Bound States of Nonlocal Potentials 591
26.2 Momentum–Space Schrodinger Equation (Theory) 592
26.3 Scattering States of Nonlocal Potentials 597
26.4 Lippmann–Schwinger Equation (Theory) 598
Appendix A Codes, Applets, and Animations 607
Bibliography 609
Index 615
