Computational Physics Richard Fitzpatrick Professor of Physics The University of Texas at Austin

1 Introduction 1.1 Intended Audience These set of lecture notes are designed for an upper-division undergraduate course on computational physics. 1.2 Major Sources The sources which I have consulted most frequently whilst developing course material are as follows: C/C++ PROGRAMMING: Software engineering in C, P.A. Darnell, and P.E. Margolis (Springer-Verlag, New York NY, 1988). The C++ programming language, 2nd edition, B. Stroustrup (Addison-Wesley, Reading MA, 1991). Schaum’s outline: Programming with C, 2nd edition, B. Gottfried (McGrawHill, New York NY, 1996). Schaum’s outline: Programming with C++, 2nd edition, J.R. Hubbard (McGrawHill, New York NY, 2000). NUMERICAL METHODS AND COMPUTATIONAL PHYSICS: Computational physics, D. Potter (Wiley, New York NY, 1973). Numerical recipes in C: the art of scientific computing, W.H. Press, S.A. Teukolsky, W.T. Vettering, and B.R. Flannery (Cambridge University Press, Cambridge UK, 1992). Computational physics, N.J. Giordano (Prentice-Hall, Upper Saddle River NJ, 1997). Numerical methods for physics, 2nd edition, A.L. Garcia (Prentice-Hall, Upper Saddle River NJ, 2000). 81.3 Purpose of Course 1 INTRODUCTION PHYSICS OF BASEBALL: The physics of baseball, R.K. Adair (Harper & Row, New York NY, 1990). The physics of sports, A.A. Armenti, Jr., Ed. (American Institute of Physics, New York NY, 1992). CHAOS: Chaos in a computer-animated pendulum, R.L. Kautz, Am. J. Phys. 61, 407 (1993). Nonlinear dynamics and chaos, S.H. Strogatz, (Addison-Wesley, Reading MA, 1994). Chaos: An introduction to dynamical systems, K.T. Alligood, T.D. Sauer, and J.A. Yorke, (Springer-Verlag, New York NY, 1997). 1.3 Purpose of Course The purpose of this course is demonstrate to students how computers can enable us to both broaden and deepen our understanding of physics by vastly increasing the range of mathematical calculations which we can conveniently perform. 1.4 Course Philosophy My approach to computational physics is to write self-contained programs in a high-level scientific language—i.e., either FORTRAN or C/C++. Of course, there are many other possible approaches, each with their own peculiar advantages and disadvantages. It is instructive to briefly examine the available options. 1.5 Programming Methodologies Basically, there are three possible methods by which we could perform the numerical calculations which we are going to encouter during this course. 91.5 Programming Methodologies 1 INTRODUCTION Firstly, we could use a mathematical software package, such as MATHEMATICA1, MAPLE2 or MATLAB.3 The main advantage of these packages is that they facilitate the very rapid coding up of numerical problems. The main disadvantage is that they produce executable code which is interpreted, rather than compiled. Compiled code is translated directly from a high-level language into machine code instructions, which, by definition, are platform dependent—after all, an Intel x86 chip has a completely different instruction set to a Power-PC chip. Interpreted code is translated from a high-level language into a set of meta-code instructions which are platform independent. Each meta-code instruction is then translated into a fixed set of machine code instructions which is peculiar to the particular hardware platform on which the code is being run. In general, interpreted code is nowhere near as efficient, in terms of computer resource utilization, as compiled code: i.e., interpreted code run a lot slower than equivalent compiled code. Thus, although MATHEMATICA, MAPLE, and MATLAB are ideal environments in which to perform relatively small calculations, they are not suitable for full-blown research projects, since the code which they produce generally runs far too slowly. Secondly, we could write our own programs in a high-level language, but use calls to pre-written, pre-compiled routines in commonly available subroutine libraries, such as NAG,4 LINPACK,5 and ODEPACK,6 to perform all of the real numerical work. This is the approach used by the majority of research physicists. Thirdly, we could write our own programs—completely from scratch—in a high-level language. This is the approach used in this course. I have opted not to use pre-written subroutine libraries, simply because I want students to develop the ability to think for themselves about scientific programming and numerical techniques. Students should, however, realize that, in many cases, pre-written library routines offer solutions to numerical problems which are pretty hard to improve upon. 1See 2See 3See 4See 5See 6ibid. 101.6 Scientific Programming Languages 1 INTRODUCTION 1.6 Scientific Programming Languages What is the best high-level language to use for scientific programming? This, unfortunately, is a highly contentious question. Over the years, literally hundreds of high-level languages have been developed. However, few have stood the test of time. Many languages (e.g., Algol, Pascal, Haskell) can be dismissed as ephemeral computer science fads. Others (e.g., Cobol, Lisp, Ada) are too specialized to adapt for scientific use. Let us examine the remaining options: FORTRAN 77: FORTRAN was the first high-level programming language to be developed: in fact, it predates the languages listed below by decades. Before the advent of FORTRAN, all programming was done in assembler code! Moreover, FORTRAN was specifically designed for scientific computing. Indeed, in the early days of computers all computing was scientific in nature— i.e., physicists and mathematicians were the original computer scientists! FORTRAN’s main advantages are that it is very straightforward, and it interfaces well with most commonly available, pre-written subroutine libraries (since these libraries generally consist of compiled FORTRAN code). FORTRAN’s main disadvantages are all associated with its relative antiquity. For instance. FORTRAN’s control statements are fairly rudimentary, whereas its input/output facilities are positively paleolithic. FORTRAN 90: This language is a major extension to FORTRAN 77 which does away with many of the latter language’s objectionable features. In addition, many “modern” features, such as dynamic memory allocation, are included in the language for the first time. The major disadvantage of this language is the absence of an inexpensive compiler. There seems little prospect of this situation changing in the near future. C: This language was originally developed by computer scientists to write operating systems. Indeed, all UNIX operating systems are written in C. C is, consequently, an extremely flexible and powerful language. Amongst its major advantages are its good control statements and excellent input/output facilities. C’s main disadvantage is that, since it was not specifically written to be a scientific language, some important scientific features (e.g., complex 111.6 Scientific Programming Languages 1 INTRODUCTION arithmetic) are missing. Although C is a high-level language, it incorporates many comparatively low-level features, such as pointers (this is hardly surprisingly, since C was originally designed to write operating systems). The low-level features of C—in particular, the rather primitive implementation of arrays—sometimes make scientific programming more complicated than need be the case, and undoubtedly facilitate programming errors. On the other hand, these features allow scientific programmers to write extremely efficient code. Since efficiency is generally the most important concern in scientific computing, the low-level features of C are, on balance, advantageous. C++: This language is a major extension of C whose main aim is to facilitate object-orientated programming. Object-orientation is a completely different approach to programming than the more traditional procedural approach: it is particularly well suited to large projects involving many people who are each writing different segments of the same code. However, objectorientation represents a large, and somewhat unnecessary, overhead for the type of straightforward, single person programming tasks considered in this course. Note, however, that C++ incorporates some non-object-orientated extensions to C which are extremely useful. Of the above languages, we can immediately rule out C++, because objectorientation is an unnecessary complication (at least, for our purposes), and FORTRAN 90, because of the absence of an inexpensive compiler. The remaining options are FORTRAN 77 and C. I have chosen to use C (augmented by some of the useful, non-object-orientated features of C++) in this course, simply because I find the archaic features of FORTRAN 77 too embarrassing to teach students in the 21st century. 122 SCIENTIFIC PROGRAMMING IN C 2 Scientific Programming in C 2.1 Introduction As we have already mentioned, C is a flexible, extremely powerful, high-level programming language which was initially designed for writing operating systems and system applications. In fact, all UNIX operating systems, as well as most UNIX applications (e.g., text editors, window managers, etc.) are written in C. However, C is also an excellent vehicle for scientific programming, since, almost by definition, a good scientific programming language must be powerful, flexible, and high-level. Having said this, many of the features of C which send computer scientists into raptures are not particularly relevant to the needs of the scientific programmer. Hence, in the following, we shall only describe that subset of the C language which is really necessary to write scientific programs. It may be objected that our cut-down version of C bears a suspicious resemblance to FORTRAN. However, this resemblance is hardly surprising. After all, FORTRAN is a high-level programming language which was specifically designed with scientific computing in mind. As discussed previously, C++ is an extension of the C language whose main aim is to facilitate object-orientated programming. The object-orientated features of C++ are superfluous to our needs in this course. However, C++ incorporates some new, non-object-orientated features which are extremely useful to the scientific programmer. We shall briefly discuss these features towards the end of this section. Finally, we shall describe some prewritten C++ classes which allow us to incorporate complex arithmetic (which is not part of the C language), variable size arrays, and graphics into our programs. 2.2 Variables Variable names in C can consist of letters and numbers in any order, except that the first character must be a letter. Names are case sensitive, so upper- and lowercase letters are not interchangeable. The underscore character (_) can also be 132.2 Variables 2 SCIENTIFIC PROGRAMMING IN C included in variable names, and is treated as a letter. There is no restriction on the length of names in C. Of course, variable names are not allowed to clash with keywords that play a special role in the C language, such as int