 Shopping Bag ( 0 items )

All (12) from $51.83

New (6) from $87.47

Used (6) from $51.79
More About This Textbook
Overview
Computational physics is a rapidly growing subfield of computational science, in large part because computers can solve previously intractable problems or simulate natural processes that do not have analytic solutions. The next step beyond Landau's First Course in Scientific Computing and a followup to Landau and Páez's Computational Physics, this text presents a broad survey of key topics in computational physics for advanced undergraduates and beginning graduate students, including new discussions of visualization tools, wavelet analysis, molecular dynamics, and computational fluid dynamics. By treating science, applied mathematics, and computer science together, the book reveals how this knowledge base can be applied to a wider range of realworld problems than computational physics texts normally address.
Designed for a one or twosemester course, A Survey of Computational Physics will also interest anyone who wants a reference on or practical experience in the basics of computational physics. The text includes a CDROM with supplementary materials, including Java, Fortran, and C programs; animations; visualizations; color figures; interactive Java applets; codes for MPI, PVM, and OpenDX; and a PVM tutorial.
Editorial Reviews
Choice  K.D. Fisher
Landau and Piez, authors of Computational Physics, have teamed up with Bordeianu to create an expanded work on introductory computational physics. Even more comprehensive than the first book, this volume contains uptodate treatments of many new topics at the forefront of the field. . . . This volume offers everything needed for a graduate or undergraduate computational physics course.From the Publisher
Rubin H. Landau, Winner of the 2008 Undergraduate Computational Engineering and Sciences Awards, The Krell Institute
"Landau and Piez, authors of Computational Physics, have teamed up with Bordeianu to create an expanded work on introductory computational physics. Even more comprehensive than the first book, this volume contains uptodate treatments of many new topics at the forefront of the field. . . . This volume offers everything needed for a graduate or undergraduate computational physics course."K.D. Fisher, Choice
Choice
Landau and Piez, authors of Computational Physics, have teamed up with Bordeianu to create an expanded work on introductory computational physics. Even more comprehensive than the first book, this volume contains uptodate treatments of many new topics at the forefront of the field. . . . This volume offers everything needed for a graduate or undergraduate computational physics course.— K.D. Fisher
Product Details
Related Subjects
Meet the Author
Rubin H. Landau is professor of physics and director of the computational physics program at Oregon State University. Manuel Jose Paez is professor of physics at Universidad de Antioquia in Colombia. Cristian C. Bordeianu, a PhD candidate at University of Bucharest, is vice principal at Technological High School 1 in Suceava, Romania.
Read an Excerpt
By R. H. Landau M.J. Páez C.C. Bordeianu Princeton University Press
Copyright © 2008 Princeton University Press
All right reserved.
ISBN: 9780691131375
Chapter One Computational Science Basics
Some people spend their entire lives reading but never get beyond reading the words on the page; they don't understand that the words are merely stepping stones placed across a fastflowing river, and the reason they're there is so that we can reach the farther shore; it's the other side that matters. José Saramago
As an introduction to the book to follow, we start this chapter with a description of how computational physics (CP) fits into the broader field of computational science, and what topics we will present as the contents of CP. We then get down to basics and examine computing languages, number representations, and programming. Related topics dealing with hardware basics are found in Chapter 14, "HighPerformance Computing Hardware, Tuning, and Parallel Computing."
1.1 Computational Physics and Computational Science
This book adopts the view that CP is a subfield ofcomputational science. This means that CP is a multidisciplinary subject combining aspects of physics, applied mathematics, and computer science (CS) (Figure 1.1), with the aim of solving realistic physics problems. Other computational sciences replace the physics with biology, chemistry, engineering, and so on, and together face grand challenge problems such as
Climate prediction Materials science Structural biology Superconductivity Semiconductor design Drug design Human genome Quantum chromodynamics Turbulence Speech and vision Relativistic astrophysics Vehicle dynamics Nuclear fusion Combustion systems Oil and gas recovery Ocean science Vehicle signature Undersea surveillance
Although related, computational science is not computer science. Computer science studies computing for its own intrinsic interest and develops the hardware and software tools that computational scientists use. Likewise, applied mathematics develops and studies the algorithms that computational scientists use. As much as we too find math and computer science interesting for their own sakes, our focus is on solving physical problems; we need to understand the CS and math tools well enough to be able to solve our problems correctly.
As CP has matured, we have come to realize that it is more than the overlap of physics, computer science, and mathematics (Figure 1.1). It is also a bridge among them (the central region in Figure 1.1) containing core elements of it own, such as computational tools and methods. To us, CP's commonality of tools and a problemsolving mindset draws it toward the other computational sciences and away from the subspecialization found in so much of physics.
In order to emphasize our computational science focus, to the extent possible, we present the subjects in this book in the form of a problem to solve, with the components that constitute the solution separated according to the scientific problemsolving paradigm (Figure 1.2 left). Traditionally, physics employs both experimental and theoretical approaches to discover scientific truth (Figure 1.2 right). Being able to transform a theory into an algorithm requires significant theoretical insight, detailed physical and mathematical understanding, and a mastery of the art of programming. The actual debugging, testing, and organization of scientific programs is analogous to experimentation, with the numerical simulations of nature being essentially virtual experiments. The synthesis of numbers into generalizations, predictions, and conclusions requires the insight and intuition common to both experimental and theoretical science. In fact, the use of computation and simulation has now become so prevalent and essential a part of the scientific process that many people believe that the scientific paradigm has been extended to include simulation as an additional dimension (Figure 1.2 right).
1.2 How to Read and Use This Book
Figure 1.3 maps out the CP concepts we cover in this book and the relations among them. You may think of this concept map as the details left out of Figure 1.1. On the left are the hardware and software components from computer science; in the middle are the algorithms of applied mathematics; on the right are the physics applications. Yet because CP is multidisciplinary, it is easy to argue that certain concepts should be moved someplace else.
A more traditional way to view the materials in this text is in terms of its use in courses. In our classes [CPUG] we use approximately the first third of the text, with its emphasis on computing tools, for a course in scientific computing (after students have acquired familiarity with a compiled language). Typical topics covered in the 10 weeks of such a course are given in Table 1.1. Some options are indicated in the caption, and, depending upon the background of the students, other topics may be included or substituted. The latter twothirds of the text includes more physics, and, indeed, we use it for a twoquarter (20week) course in computational physics. Typical topics covered for each term are given in Table 1.2. What with many of the latter topics being research level, we suspect that these materials can easily be used for a full year's course as well.
For these materials to contribute to a successful learning experience, we assume that the reader will work through the problem at the beginning of each chapter or unit. This entails studying the text, writing, debugging and running programs, visualizing the results, and then expressing in words what has been done and what can be concluded. Further exploring is encouraged. Although we recognize that programming is a valuable skill for scientists, we also know that it is incredibly exacting and timeconsuming. In order to lighten the workload somewhat, we provide "bare bones" programs in the text and on the CD. We recommend that these be used as guides for the reader's own programs or tested and extended to solve the problem at hand. As part of this approach we suggest that the learner write up a mini lab report for each problem containing
Equations solved Numerical method Code listing Visualization Discussion Critique
The report should be an executive summary of the type given to a boss or manager; make it clear that you understand the materials but do not waste everyone's time.
One of the most rewarding uses of computers is visualizing and analyzing the results of calculations with 2D and 3D plots, with color, and with animation. This assists in the debugging process, hastens the development of physical and mathematical intuition, and increases the enjoyment of the work. It is essential that you learn to use visualization tools as soon as possible, and so in Chapter 3, "Visualization Tools," and Appendix C we describe a number of free visualization 1 tools that we use and recommend. We include many figures showing visualizations 0 (unfortunately just in gray scale), with color versions on the CD.
We have tried to make the multifaceted contents of this book clearer by use of the following symbols and fonts:
in the margin Material on the CD [??] Optional material [??] at line's end End of exercise or problem Monospace font Words as they would appear on a computer screen Italic font Note at beginning of chapter to the reader about what's to follow Sans serif font Program commands from dropdown menus
We also indicate a usercomputer dialog via three different fonts on a line:
Monospace computer's output > Bold monospace user's command Comments
Code listings are formatted within a shaded box, with italic key words and bold comments (usually on the right):
for ( i = 0 ; i <= Nxmax ; i ++ ) { // Comment: Fluid surface u [i] [Nymax] = u [i] [Nymax1] + V0*h; w[i] [Nymax1] = 0 . ; }
public double getI () { return (2./5.) * m * r * r; } // Method getI
Note that we have tried to structure the codes so that a line is skipped before each method, so that each logical structure is indented by two spaces, and so that the ending brace } of a logical element is on a separate line aligned with the beginning of the logic element. However, in order to conserve space, sometimes we do not insert blank lines even though it may add clarity, sometimes the commands for short methods or logical structures are placed on a single line, and usually we combine multiple ending braces on the last line.
Although we try to be careful to define each term the first time it is used, we also have included a glossary in Appendix A for reference. Further, Appendix B describes the steps needed to install some of the software packages we recommend, and Appendix F lists the names and functions of the various items on the CD.
1.3 Making Computers Obey; Languages (Theory)
Computers are incredibly fast, accurate, and stupid; humans are incredibly slow, inaccurate, and brilliant; together they are powerful beyond imagination.  Albert Einstein
As anthropomorphic as your view of your computer may be, keep in mind that 1 computers always do exactly as they are told. This means that you must tell them exactly everything they have to do. Of course the programs you run may have such convoluted logic that you may not have the endurance to figure out the details of what you have told the computer to do, but it is always possible in principle. So your first problem is to obtain enough understanding so that you feel well enough in control, no matter how illusionary, to figure out what the computer is doing.
Before you tell the computer to obey your orders, you need to understand that life is not simple for computers. The instructions they understand are in a basic machine language that tells the hardware to do things like move a number stored in one memory location to another location or to do some simple binary arithmetic. Very few computational scientists talk to computers in a language computers can understand. When writing and running programs, we usually communicate to the computer through shells, in highlevel languages (Java, Fortran, C), or through problemsolving environments (Maple, Mathematica, and Matlab). Eventually these commands or programs are translated into the basic machine language that the hardware understands.
A shell is a commandline interpreter, that is, a set of small programs run by a computer that respond to the commands (the names of the programs) that you key in. Usually you open a special window to access the shell, and this window is called a shell as well. It is helpful to think of these shells as the outer layers of the computer's operating system (OS) (Figure 1.4), within which lies a kernel of elementary operations. (The user seldom interacts directly with the kernel, except possibly when installing programs or when building an operating system from scratch.) It is the job of the shell to run programs, compilers, and utilities that do things like copying files. There can be different types of shells on a single computer or multiple copies of the same shell running at the same time.
Operating systems have names such as Unix, Linux, DOS, MacOS, and MS Windows. The operating system is a group of programs used by the computer to communicate with users and devices, to store and read data, and to execute programs. Under Unix and Linux, the OS tells the computer what to do in an elementary way, while Windows includes various graphical elements as part of the operating system (this increases speed at the cost of complexity). The OS views you, other devices, and programs as input data for it to process; in many ways, it is the indispensable office manager. While all this may seem complicated, the purpose of the OS is to let the computer do the nittygritty work so that you can think higherlevel thoughts and communicate with the computer in something closer to your normal everyday language.
When you submit a program to your computer in a highlevel language, the computer uses a compiler to process it. The compiler is another program that treats your program as a foreign language and uses a builtin dictionary and set of rules to translate it into basic machine language. As you can probably imagine, the final set of instructions is quite detailed and long and the compiler may make several passes through your program to decipher your logic and translate it into a fast code. The translated statements form an object or compiled code, and when linked together with other needed subprograms, form a load module. A load module is a complete set of machine language instructions that can be loaded into the computer's memory and read, understood, and followed by the computer.
Languages such as Fortran and ITLITL use compilers to read your entire program and then translate it into basic machine instructions. Languages such as BASIC and Maple translate each line of your program as it is entered. Compiled languages usually lead to more efficient programs and permit the use of vast subprogram libraries. Interpreted languages give a more immediate response to the user and thereby appear "friendlier." The Java language is a mix of the two. When you first compile your program, it interprets it into an intermediate, universal byte code, but then when you run your program, it recompiles the byte code into a machinespecific compiled code.
1.4 Programming Warmup
Before we go on to serious work, we want to ensure that your local computer is working right for you. Assume that calculators have not yet been invented and that you need a program to calculate the area of a circle. Rather than use any specific language, write that program in pseudocode that can be converted to your favorite language later. The first program tells the computer: Calculate area of circle // Do this computer! This program cannot really work because it does not tell the computer which circle to consider and what to do with the area. A better program would be
read radius // Input calculate area of circle // Numerics print area // Output
The instruction calculate area of circle has no meaning in most computer languages, so we need to specify an algorithm, that is, a set of rules for the computer to follow:
read radius // Input PI = 3.141593 // Set constant area = PI * r * r // Algorithm print area // Output
This is a better program, and so let's see how to implement it in Java (other languageversions are on the CD). In Listing 1.1 we give a Java version of our area program. This is a simple program that outputs to the screen and has its input entered via statements.
(Continues...)
Table of Contents
Preface xxiii
CHAPTER 1: Computational Science Basics 1
1.1 Computational Physics and Science 1
1.2 How to Read and Use This Book 3
1.3 Making Computers Obey; Languages (Theory) 6
1.4 Programming Warmup 8
1.4.1 Structured Program Design 10
1.4.2 Shells, Editors, and Execution 11
1.4.3 Java I/O, Scanner Class with printf 12
1.4.4 I/O Redirection 12
1.4.5 CommandLine Input 13
1.4.6 I/O Exceptions: FileCatchThrow.java 14
1.4.7 Automatic Code Documentation 16
1.5 Computer Number Representations (Theory) 17
1.5.1 IEEE FloatingPoint Numbers 18
1.5.2 Over/Underflows Exercises 24
1.5.3 Machine Precision (Model) 25
1.5.4 Determine Your Machine Precision 27
1.6 Problem: Summing Series 27
1.6.1 Numerical Summation (Method) 28
1.6.2 Implementation and Assessment 29
CHAPTER 2: Errors & Uncertainties in Computations 30
2.1 Types of Errors (Theory) 30
2.1.1 Model for Disaster: Subtractive Cancellation 32
2.1.2 Subtractive Cancellation Exercises 33
2.1.3 Roundoff Error in a Single Step 34
2.1.4 Roundoff Error Accumulation After Many Steps 35
2.2 Errors in Spherical Bessel Functions (Problem) 36
2.2.1 Numerical Recursion Relations (Method) 36
2.2.2 Implementation and Assessment: Recursion Relations 38
2.3 Experimental Error Investigation (Problem) 39
2.3.1 Error Assessment 43
CHAPTER 3: Visualization Tools 45
3.1 Data Visualization 45
3.2 PtPlot: 2D Graphs Within Java 46
3.3 Grace/ACE: Superb 2D Graphs for Unix/Linux 51
3.3.1 Grace Basics 51
3.4 Gnuplot: Reliable 2D and 3D Plots 56
3.4.1 Gnuplot Input Data Format 58
3.4.2 Printing Plots 59
3.4.3 Gnuplot Surface (3D) Plots 60
3.4.4 Gnuplot Vector Fields 62
3.4.5 Animations from a Plotting Program (Gnuplot) 64
3.5 OpenDX for Dicing and Slicing 65
3.6 Texturing and 3D Imaging 65
CHAPTER 4: ObjectOriented Programs: Impedance &
Batons 67
4.1 Unit I. Basic Objects: Complex Impedance 67
4.2 Complex Numbers (Math) 67
4.3 Resistance Becomes Impedance (Theory) 70
4.4 Abstract Data Structures, Objects (CS) 70
4.4.1 Object Declaration and Construction 72
4.4.2 Implementation in Java 73
4.4.3 Static and Nonstatic Methods 76
4.4.4 Nonstatic Methods 77
4.5 Complex Currents (Solution) 79
4.6 OOP Worked Examples 80
4.6.1 OOP Beats 80
4.6.2 OOP Planet 82
4.7 Unit II. Advanced Objects: Baton Projectiles 85
4.8 Trajectory of a Thrown Baton (Problem) 86
4.8.1 Combined Translation and Rotation (Theory) 86
4.9 OOP Design Concepts (CS) 89
4.9.1 Including Multiple Classes 90
4.9.2 Ball and Path Class Implementation 92
4.9.3 Composition, Objects Within Objects 93
4.9.4 Baton Class Implementation 94
4.9.5 Composition Exercise 95
4.9.6 Calculating the Baton's Energy (Extension) 96
4.9.7 Examples of Inheritance and Object Hierarchies 98
4.9.8 Baton with a Lead Weight (Application) 99
4.9.9 Encapsulation to Protect Classes 100
4.9.10 Encapsulation Exercise 101
4.9.11 Complex Object Interface (Extension) 102
4.9.12 Polymorphism, Variable Multityping 104
4.10 Supplementary Exercises 105
4.11 OOP Example: Superposition of Motions 105
4.12 Newton's Laws of Motion (Theory) 106
4.13 OOP Class Structure (Method) 106
4.14 Java Implementation 107
CHAPTER 5: Monte Carlo Simulations (Nonthermal) 109
5.1 Unit I. Deterministic Randomness 109
5.2 Random Sequences (Theory) 109
5.2.1 RandomNumber Generation (Algorithm) 110
5.2.2 Implementation: Random Sequence 113
5.2.3 Assessing Randomness and Uniformity 114
5.3 Unit II. Monte Carlo Applications 116
5.4 A Random Walk (Problem) 116
5.4.1 RandomWalk Simulation 116
5.4.2 Implementation: Random Walk 117
5.5 Radioactive Decay (Problem) 119
5.5.1 Discrete Decay (Model) 119
5.5.2 Continuous Decay (Model) 120
5.5.3 Decay Simulation 121
5.6 Decay Implementation and Visualization 122
CHAPTER 6: Integration 123
6.1 Integrating a Spectrum (Problem) 123
6.2 Quadrature as Box Counting (Math) 123
6.2.1 Algorithm: Trapezoid Rule 125
6.2.2 Algorithm: Simpson's Rule 126
6.2.3 Integration Error (Analytic Assessment) 128
6.2.4 Algorithm: Gaussian Quadrature 130
6.2.5 Integration Implementation and Error Assessment 132
6.3 Experimentation 135
6.4 HigherOrder Rules (Algorithm) 135
6.5 Monte Carlo Integration by Stone Throwing 136
6.5.1 Stone Throwing Implementation 136
6.5.2 Integration by Mean Value (Math) 137
6.6 HighDimensional Integration (Problem) 138
6.6.1 Multidimensional Monte Carlo 139
6.6.2 Error in Multidimensional Integration (Assessment) 139
6.6.3 Implementation: 10D Monte Carlo Integration 139
6.7 Integrating Rapidly Varying Functions (Problem) 140
6.7.1 Variance Reduction (Method) 140
6.7.2 Importance Sampling (Method) 140
6.7.3 Von Neumann Rejection (Method) 141
6.7.4 Simple Gaussian Distribution 141
6.8 Nonuniform Assessment 142
6.8.1 Implementation: Nonuniform Randomness 142
CHAPTER 7: Differentiation & Searching 146
7.1 Unit I. Numerical Differentiation 146
7.2 Forward Difference (Algorithm) 147
7.3 Central Difference (Algorithm) 148
7.4 Extrapolated Difference (Method) 149
7.5 Error Analysis (Assessment) 149
7.6 Second Derivatives (Problem) 151
7.6.1 SecondDerivative Assessment 151
7.7 Unit II. TrialandError Searching 151
7.8 Quantum States in a Square Well (Problem) 152
7.9 TrialandError Roots via the Bisection Algorithm 152
7.9.1 Bisection Algorithm Implementation 153
7.10 NewtonRaphson Searching (A Faster Algorithm) 154
7.10.1 NewtonRaphson Algorithm with Backtracking 156
7.10.2 NewtonRaphson Algorithm Implementation 157
CHAPTER 8: Solving Systems of Equations with Matrices;
Data Fitting 158
8.1 Unit I. Systems of Equations and Matrix Computing 158
8.2 Two Masses on a String 159
8.2.1 Statics (Theory) 160
8.2.2 Multidimensional NewtonRaphson Searching 160
8.3 Classes of Matrix Problems (Math) 163
8.3.1 Practical Aspects of Matrix Computing 165
8.3.2 Implementation: Scientific Libraries, World Wide Web 168
8.3.3 JAMA: Java Matrix Library 169
8.3.4 Exercises for Testing Matrix Calls 173
8.3.5 Matrix Solution of the String Problem 175
8.3.6 Explorations 175
8.4 Unit II. Data Fitting 176
8.5 Fitting an Experimental Spectrum (Problem) 176
8.5.1 Lagrange Interpolation (Method) 177
8.5.2 Lagrange Implementation and Assessment 178
8.5.3 Explore Extrapolation 179
8.5.4 Cubic Splines (Method) 179
8.5.5 Spline Fit of Cross Section (Implementation) 182
8.6 Fitting Exponential Decay (Problem) 182
8.6.1 Theory to Fit 182
8.7 LeastSquares Fitting (Method) 184
8.7.1 LeastSquares Fitting: Theory and Implementation 186
8.7.2 Exponential Decay Fit Assessment 188
8.7.3 Exercise: Fitting Heat Flow 189
8.7.4 Linear Quadratic Fit (Extension) 190
8.7.5 Linear Quadratic Fit Assessment 191
8.7.6 Nonlinear Fit of the BreitWigner Formula to a Cross Section 191
CHAPTER 9: Differential Equation Applications 194
9.1 Unit I. Free Nonlinear Oscillations 194
9.2 Nonlinear Oscillators (Models) 194
9.3 Types of Differential Equations (Math) 196
9.4 Dynamic Form for ODEs (Theory) 198
9.5 ODE Algorithms 200
9.5.1 Euler's Rule 201
9.5.2 RungeKutta Algorithm 202
9.5.3 AdamsBashforthMoulton PredictorCorrector 204
9.5.4 Assessment: rk2 versus rk4 versus rk45 205
9.6 Solution for Nonlinear Oscillations (Assessment) 207
9.6.1 Precision Assessment: Energy Conservation 208
9.7 Extensions: Nonlinear Resonances, Beats, and Friction 209
9.7.1 Friction: Model and Implementation 209
9.7.2 Resonances and Beats: Model and Implementation 210
9.8 Implementation: Inclusion of TimeDependent Force 211
9.9 Unit II. Binding A Quantum Particle 212
9.10 The Quantum Eigenvalue Problem (Theory) 212
9.10.1 Nucleon in a Box (Model) 213
9.11 Combined Algorithms: Eigenvalues via ODE Solver Plus Search 214
9.11.1 Numerov Algorithm for the Schrödinger ODE 216
9.11.2 Implementation: Eigenvalues via an ODE Solver Plus Bisection Algorithm 218
9.12 Explorations 221
9.13 Unit III. Scattering, Projectiles, and Planetary Orbits 222
9.14 Problem 1: Classical Chaotic Scattering 222
9.14.1 Model and Theory 222
9.14.2 Implementation 224
9.14.3 Assessment 225
9.15 Problem 2: Balls Falling Out of the Sky 225
9.16 Theory: Projectile Motion with Drag 226
9.16.1 Simultaneous SecondOrder ODEs 227
9.16.2 Assessment 228
9.17 Problem 3: Planetary Motion 228
9.17.1 Implementation: Planetary Motion 229
CHAPTER 10: Fourier Analysis: Signals and Filters 231
10.1 Unit I. Fourier Analysis of Nonlinear Oscillations 231
10.2 Fourier Series (Math) 232
10.2.1 Example 1: Sawtooth Function 234
10.2.2 Example 2: Halfwave Function 235
10.3 Summation of Fourier Series (Exercise) 235
10.4 Fourier Transforms (Theory) 236
10.4.1 Discrete Fourier Transform Algorithm 237
10.4.2 Aliasing and Antialiasing 241
10.4.3 DFT for Fourier Series (Algorithm) 243
10.4.4 Assessments 244
10.4.5 DFT of Nonperiodic Functions (Exploration) 246
10.5 Unit II. Filtering Noisy Signals 246
10.6 Noise Reduction via Autocorrelation (Theory) 246
10.6.1 Autocorrelation Function Exercises 249
10.7 Filtering with Transforms (Theory) 250
10.7.1 Digital Filters: Windowed Sinc Filters 253
10.8 Unit III. Fast Fourier Transform Algorithm 256
10.8.1 Bit Reversal 258
10.9 FFT Implementation 259
10.10 FFT Assessment 263
CHAPTER 11: Wavelet Analysis & Data Compression 264
11.1 Unit I. Wavelet Basics 264
11.2 Wave Packets and Uncertainty Principle (Theory) 266
11.2.1 Wave Packet Assessment 268
11.3 ShortTime Fourier Transforms (Math) 268
11.4 The Wavelet Transform 269
11.4.1 Generating Wavelet Basis Functions 270
11.4.2 Continuous Wavelet Transform Implementation 273
11.5 Unit II. Discrete Wavelet Transform and Multiresolution Analysis 274
11.5.1 Pyramid Scheme Implementation 279
11.5.2 Daubechies Wavelets via Filtering 283
11.5.3 DWT Implementation and Exercise 286
CHAPTER 12: Discrete & Continuous Nonlinear Dynamics 289
12.1 Unit I. Bug Population Dynamics (Discrete) 289
12.2 The Logistic Map (Model) 289
12.3 Properties of Nonlinear Maps (Theory) 291
12.3.1 Fixed Points 291
12.3.2 Period Doubling, Attractors 292
12.4 Mapping Implementation 293
12.5 Bifurcation Diagram (Assessment) 294
12.5.1 Bifurcation Diagram Implementation 295
12.5.2 Visualization Algorithm: Binning 295
12.5.3 Feigenbaum Constants (Exploration) 297
12.6 Random Numbers via Logistic Map
(Exploration) 297
12.7 Other Maps (Exploration) 298
12.8 Signals of Chaos: Lyapunov Coefficients 298
12.8.1 Shannon Entropy 299
12.9 Unit I Quiz 300
12.10 Unit II. Pendulums Become Chaotic (Continuous) 302
12.11 Chaotic Pendulum ODE 302
12.11.1 Free Pendulum Oscillations 303
12.11.2 Solution as Elliptic Integrals 304
12.11.3 Implementation and Test: Free Pendulum 305
12.12 Visualization: Phase Space Orbits 305
12.12.1 Chaos in Phase Space 307
12.12.2 Assessment in Phase Space 311
12.13 Exploration: Bifurcations of Chaotic Pendulums 313
12.14 Alternative Problem: The Double Pendulum 315
12.15 Assessment: Fourier/Wavelet Analysis of Chaos 317
12.16 Exploration: Another Type of Phase Space Plot 317
12.17 Further Explorations 318
12.18 Unit III. Coupled PredatorPrey Models 319
12.19 LotkaVolterra Model 320
12.19.1 LVM with Prey Limit 321
12.19.2 LVM with Predation Efficiency 322
12.19.3 LVM Implementation and Assessment 323
12.19.4 Two Predators, One Prey (Exploration) 324
CHAPTER 13: Fractals & Statistical Growth 326
13.1 Fractional Dimension (Math) 326
13.2 The Sierpński Gasket (Problem 1) 327
13.2.1 Sierpński Implementation 328
13.2.2 Assessing Fractal Dimension 328
13.3 Beautiful Plants (Problem 2) 329
13.3.1 Selfaffine Connection (Theory) 330
13.3.2 Barnsley's Fern Implementation 331
13.3.3 Selfaffinity in Trees Implementation 332
13.4 Ballistic Deposition (Problem 3) 332
13.4.1 Random Deposition Algorithm 332
13.5 Length of the British Coastline (Problem 4) 334
13.5.1 Coastlines as Fractals (Model) 334
13.5.2 Box Counting Algorithm 335
13.5.3 Coastline Implementation and Exercise 336
13.6 Correlated Growth, Forests, and Films (Problem 5) 338
13.6.1 Correlated Ballistic Deposition Algorithm 338
13.7 Globular Cluster (Problem 6) 339
13.7.1 DiffusionLimited Aggregation Algorithm 339
13.7.2 Fractal Analysis of a DLA (or Pollock)
Graph (Assessment) 342
13.8 Fractal Structures in a Bifurcation Graph
(Problem 7) 343
13.9 Fractals from Cellular Automata 343
13.10 Perlin Noise Adds Realism 345
13.10.1Including Ray Tracing 348
13.11 Quiz 351
CHAPTER 14: HighPerformance Computing Hardware, Tuning, and Parallel Computing 352
14.1 Unit I. HighPerformance Computers (CS) 352
14.2 Memory Hierarchy 353
14.3 The Central Processing Unit 357
14.4 CPU Design: Reduced Instruction Set Computer 357
14.5 CPU Design: MultipleCore Processors 358
14.6 CPU Design: Vector Processor 359
14.7 Unit II. Parallel Computing 360
14.8 Parallel Semantics (Theory) 361
14.9 Distributed Memory Programming 363
14.10 Parallel Performance 365
14.10.1 Communication Overhead 367
14.11 Parallelization Strategy 368
14.12 Practical Aspects of Message Passing for MIMD 369
14.12.1 HighLevel View of Message Passing 370
14.13 Example of a Supercomputer: IBM Blue Gene/L 372
14.14 Unit III. HPC Program Optimization 374
14.14.1 Programming for Virtual Memory (Method) 376
14.14.2 Optimizing Programs; Java versus Fortran/C 376
14.14.3 Experimental Effects of Hardware on Performance 379
14.14.4 Java versus Fortran/C 380
14.15 Programming for the Data Cache (Method) 385
14.15.1 Exercise 1: Cache Misses 386
14.15.2 Exercise 2: Cache Flow 387
14.15.3 Exercise 3: LargeMatrix Multiplication 388
CHAPTER 15: Thermodynamic Simulations & Feynman Quantum Path Integration 390
15.1 Unit I. Magnets via the Metropolis Algorithm 390
15.2 An Ising Chain (Model) 390
15.3 Statistical Mechanics (Theory) 393
15.3.1 Analytic Solutions 393
15.4 Metropolis Algorithm 394
15.4.1 Metropolis Algorithm Implementation 397
15.4.2 Equilibration, Thermodynamic Properties (Assessment) 397
15.4.3 Beyond Nearest Neighbors and 1D (Exploration) 400
15.5 Unit II. Magnets via WangLandau Sampling 400
15.6 WangLandau Sampling 403
15.6.1 WLS Ising Model Implementation 405
15.6.2 WLS Ising Model Assessment 408
15.7 Unit III. Feynman Path Integrals 408
15.8 Feynman's SpaceTime Propagation (Theory) 408
15.8.1 BoundState Wave Function ( Theory) 412
15.8.2 Lattice Path Integration (Algorithm) 413
15.8.3 Lattice Implementation 418
15.8.4 Assessment and Exploration 420
15.9 Exploration: Quantum Bouncer's Paths 421
CHAPTER 16: Simulating Matter with Molecular Dynamics 424
16.1 Molecular Dynamics ( Theory) 424
16.1.1 Connection to Thermodynamic Variables 428
16.1.2 Setting Initial Velocity Distribution 429
16.1.3 Periodic Boundary Conditions and Potential Cutoff 429
16.2 Verlet and VelocityVerlet Algorithms 431
16.3 1D Implementation and Exercise 432
16.4 Trajectory Analysis 435
16.5 Quiz 436
CHAPTER 17: PDEs for Electrostatics & Heat Flow 437
17.1 PDE Generalities 437
17.2 Unit I. Electrostatic Potentials 439
17.2.1 Laplace's Elliptic PDE ( Theory) 439
17.3 Fourier Series Solution of a PDE 440
17.3.1 Polynomial Expansion As an Algorithm 442
17.4 Solution: FiniteDifference Method 443
17.4.1 Relaxation and Overrelaxation 445
17.4.2 Lattice PDE Implementation 446
17.5 Assessment via Surface Plot 447
17.6 Alternate Capacitor Problems 448
17.7 Implementation and Assessment 450
17.8 Electric Field Visualization (Exploration) 452
17.9 Laplace Quiz 452
17.10 Unit II. FiniteElement Method 453
17.11 Electric Field from Charge Density (Problem) 454
17.12 Analytic Solution 454
17.13 FiniteElement (Not Difference) Methods 455
17.13.1 Weak Form of PDE 455
17.13.2 Galerkin Spectral Decomposition 456
17.14 FEM Implementation and Exercises 460
17.15 Exploration 463
17.16 Unit III. Heat Flow via TimeStepping (Leapfrogging) 463
17.17 The Parabolic Heat Equation (Theory) 463
17.17.1 Solution: Analytic Expansion 465
17.17.2 Solution: TimeStepping 466
17.17.3 Von Neumann Stability Assessment 468
17.17.4 Heat Equation Implementation 470
17.18 Assessment and Visualization 470
17.19 Improved Heat Flow: CrankNicolson Method 472
17.19.1 Solution of Tridiagonal Matrix Equations 474
17.19.2 CrankNicolson Method Implementation and Assessment 476
CHAPTER 18: PDEWaves: String, Quantum Packet, and E&M 478
18.1 Unit I. Vibrating String 478
18.2 The Hyperbolic Wave Equation (Theory) 478
18.2.1 Solution via NormalMode Expansion 480
18.2.2 Algorithm: TimeStepping 481
18.2.3 Wave Equation Implementation 483
18.2.4 Assessment and Exploration 484
18.3 Waves with Friction (Extension) 486
18.4 Waves for Variable Tension and Density
(Extension) 487
18.4.1 Waves on a Catenary 488
18.4.2 Derivation of a Catenary Shape 488
18.4.3 Catenary and Frictional Wave Exercises 490
18.5 Unit II. Quantum Wave Packets 491
18.6 TimeDependent Schrödinger Equation (Theory) 492
18.6.1 FiniteDifference Algorithm 493
18.6.2 Wave Packet Implementation and Animation 494
18.7 Wave Packets in Other Wells (Exploration) 496
18.8 Algorithm for the 2D Schrödinger Equation 496
18.9 Unit III. E&M Waves via FiniteDifference Time Domain 499
18.10 Maxwell's Equations 499
18.11 FDTD Algorithm 500
18.11.1 Implementation 503
18.11.2 Assessment 504
18.11.3 Extension: Circularly Polarized EM Waves 506
CHAPTER 19: Solitons & Computational Fluid Dynamics 508
19.1 Unit I. Advection, Shocks, and Russell's Soliton 508
19.2 Theory: Continuity and Advection Equations 509
19.2.1 Advection Implementation 510
19.3 Theory: Shock Waves via Burgers' Equation 510
19.3.1 Algorithm: The LaxWendroff Method for Burgers' Equation 511
19.3.2 Implementation and Assessment of Burgers' Shock Equation 513
19.4 Including Dispersion 514
19.5 ShallowWater Solitons, the KdeV Equation 515
19.5.1 Analytic Soliton Solution 517
19.5.2 Algorithm for KdeV Solitons 518
19.5.3 Implementation: KdeV Solitons 519
19.5.4 Exploration: Solitons in Phase Space and Crossing 520
19.6 Unit II. River Hydrodynamics 521
19.7 Hydrodynamics, the NavierStokes Equation (Theory) 521
19.7.1 Boundary Conditions for Parallel Plates 524
19.7.2 Analytic Solution for Parallel Plates 526
19.7.3 FiniteDifference Algorithm and Overrelaxation 527
19.7.4 Successive Overrelaxation Implementation 529
19.8 2D Flow over a Beam 530
19.9 Theory: Vorticity Form of the NavierStokes Equation 530
19.9.1 Finite Differences and the SOR Algorithm 532
19.9.2 Boundary Conditions for a Beam 534
19.9.3 SOR on a Grid Implementation 536
19.9.4 Assessment 538
19.9.5 Exploration 539
CHAPTER 20: Integral Equations in Quantum Mechanics 540
20.1 Unit I. Bound States of Nonlocal Potentials 540
20.2 MomentumSpace Schrödinger Equation (Theory) 541
20.2.1 Integral to Linear Equations (Method) 542
20.2.2 DeltaShell Potential (Model) 544
20.2.3 Binding Energies Implementation 544
20.2.4 Wave Function (Exploration) 546
20.3 Unit II. Nonlocal Potential Scattering 546
20.4 LippmannSchwinger Equation (Theory) 547
20.4.1 Singular Integrals (Math) 548
20.4.2 Numerical Principal Values 549
20.4.3 Reducing Integral Equations to MatrixEquations
(Algorithm) 549
20.4.4 Solution via Inversion or Elimination 551
20.4.5 Scattering Implementation 552
20.4.6 Scattering Wave Function (Exploration) 553
Appendix A: Glossary 555
Appendix B: Installing Packages 562
B.1 Installing Java Developer's Kit 564
B.2 Using Classes and Packages 565
B.2.1 Including Packages 565
Appendix C: OpenDX: IndustrialStrength Data Visualization 568
C.1 Getting DX and Unix Running (for Windows) 569
C.2 Test Drive of DX Visual Programming 569
C.3 DX Tools Summary 576
C.4 DX Data Structure and Storage 577
C.5 Sample Visual Programs 579
C.5.1 Sample 1: Linear Plot 579
C.5.2 Sample 2: Fourier Transform 580
C.5.3 Sample 3: Potential of a 2D Capacitor 580
C.5.4 Sample 4: Vector Field Plots 581
C.5.5 Sample 5: 3D Scalar Potentials 582
C.5.6 Sample 6: 3D Functions, the Hydrogen Atom 585
C.6 Animations with OpenDX 586
C.6.1 Scripted Animation with OpenDX 588
C.6.2 Wave Packet and Slit Animation 591
Appendix D: An MPI Tutorial 593
D.1 Running on a Beowulf 593
D.2 Running MPI 597
D.2.1 MPI under the SGE Queueing System 598
D.2.2 MPI Under the Torque/PBS Queueing System 600
D.2.3 Running Parallel Jobs with Torque 602
D.3 Your First MPI Program: MPIhello.c 604
D.3.1 MPIhello.c Explained 605
D.3.2 Send/Receive Messages: MPImessage2.c 606
D.3.3 Receive More Messages: MPImessage3.c 608
D.3.4 Broadcast Messages 609
D.3.5 Exercise 610
D.4 Parallel Tuning 611
D.5 A String Vibrating in Parallel 614
D.5.1 MPIstring.c Exercise 617
D.6 Deadlock 618
D.6.1 Nonblocking Communication 619
D.6.2 Collective Communication 619
D.7 Bootable Cluster CD 620
D.8 Parallel Computing Exercises 620
D.9 List of MPI Commands 621
Appendix E: Calling LAPACK from C 623
E.1 Calling LAPACK Fortran from C 624
E.2 Compiling C Programs with Fortran Calls 625
Appendix F: Software on the CD 626
Appendix G: Compression via DWT with Thresholding 635
G.1 More on Thresholding 637
G.2 Wavelet Implementation and Assessment 638
Bibliography 641
Index 651