Guide to Scientific Computing in C++

1 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 A Brief Introduction to C++ . . . . . . . . . . . . . . . . . . . 1.1.1 C++ is “Object-Oriented” . . . . . . . . . . . . . . . . 1.1.2 Why You Should Write Scientific Programs in C++ . . 1.1.3 Why You Should Not Write Scientific Programs in C++ 1.1.4 Scope of This Book . . . . . . . . . . . . . . . . . . . 1.2 A First C++ Program . . . . . . . . . . . . . . . . . . . . . . 1.3 Compiling a C++ Program . . . . . . . . . . . . . . . . . . . . 1.3.1 Integrated Development Environments . . . . . . . . . 1.3.2 Compiling at the Command Line . . . . . . . . . . . . 1.3.3 Compiler Flags . . . . . . . . . . . . . . . . . . . . . . 1.4 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Basic Numerical Variables . . . . . . . . . . . . . . . . 1.4.2 Other Numerical Variables . . . . . . . . . . . . . . . 1.4.3 Mathematical Operations on Numerical Variables . . . 1.4.4 Division of Integers . . . . . . . . . . . . . . . . . . . 1.4.5 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.6 ASCII Characters . . . . . . . . . . . . . . . . . . . . 1.4.7 Boolean Variables . . . . . . . . . . . . . . . . . . . . 1.4.8 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Simple Input and Output . . . . . . . . . . . . . . . . . . . . . 1.5.1 Basic Console Output . . . . . . . . . . . . . . . . . . 1.5.2 Keyboard Input . . . . . . . . . . . . . . . . . . . . . 1.6 The assert Statement . . . . . . . . . . . . . . . . . . . . . 1.7 Tips: Debugging Code . . . . . . . . . . . . . . . . . . . . . . 1.8 Exercises . . . . . . . . . . . . . . . . . . . . . . 2 Flow of Control . . . . . . . . . . . . . . . . . . . . . 2.1 The if Statement . . . . . . . . . . . . . . . . . 2.1.1 A Single if Statement . . . . . . . . . . 2.1.2 Example: Code for a Single if Statement 2.1.3 if–else Statements . . . . . . . . . . . 2.1.4 Multiple if Statements . . . . . . . . . . 2.1.5 Nested if Statements . . . . . . 2.1.6 Boolean Variables . . . . . . . . . . . . . . . . . . . . 2.2 Logical and Relational Operators . . . . . . . . . . . . . . . . 2.3 The while Statement . . . . . . . . . . . . . . . . . . . . . . 2.4 Loops Using the for Statement . . . . . . . . . . . . . . . . . 2.4.1 Example: Calculating the Scalar Product of Two Vectors 2.5 The switch Statement . . . . . . . . . . . . . . . . . . . . . 2.6 Tips: Loops and Branches . . . . . . . . . . . . . . . . . . . . 2.6.1 Tip 1: A Common Novice Coding Error . . . . . . . . 2.6.2 Tip 2: Counting from Zero . . . . . . . . . . . . . . . . 2.6.3 Tip 3: Equality Versus Assignment . . . . . . . . . . . 2.6.4 Tip 4: Never Ending while Loops . . . . . . . . . . . 2.6.5 Tip 5: Comparing Two Floating Point Numbers . . . . 2.7 Exercises . . . . . . . . . . . . . . . . . . . . 3 File Input and Output . . . . . . . . . . . . . 3.1 Redirecting Console Output to File . . . . 3.2 Writing to File . . . . . . . . . . . . . . . 3.2.1 Setting the Precision of the Output 3.3 Reading from File . . . . . . . . . . . . . 3.4 Reading from the Command Line . . . . . 3.5 Tips: Controlling Output Format . . . . . 3.6 Exercises . . . . . . . . . . 4 Pointers . . . . . . . . . . . . . . . . . . . . . 4.1 Pointers and the Computer’s Memory . . . 4.1.1 Addresses . . . . . . . . . . . . . 4.1.2 Pointer Variables . . . . . . . . . . 4.1.3 Example Use of Pointers . . . . . 4.1.4 Warnings on the Use of Pointers . . 4.2 Dynamic Allocation of Memory for Arrays 4.2.1 Vectors . . . . . . . . . . . . . . . 4.2.2 Matrices . . . . . . . . . . . . . . 4.2.3 Irregularly Sized Matrices . . . . . 4.3 Tips: Pointers . . . . . . . . . . . . . . . 4.3.1 Tip 1: Pointer Aliasing . . . . . . . 4.3.2 Tip 2: Safe Dynamic Allocation . . 4.3.3 Tip 3: Every new Has a delete . 4.4 Exercises . . . . . . . . . . . 5 Blocks, Functions and Reference Variables . . . . . . . 5.1 Blocks . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Functions . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Simple Functions . . . . . . . . . . . . . . 5.2.2 Returning Pointer Variables from a Function 5.2.3 Use of Pointers as Function Arguments . . . 5.2.4 Sending Arrays to Functions . . Example: A Function to Calculate the Scalar Product of Two Vectors . . . . . . . . . . . . . . . . . . . . . . . Reference Variables . . . . . . . . . . . . . . . . . . . . . . . Default Values for Function Arguments . . . . . . . . . . . . . Function Overloading . . . . . . . . . . . . . . . . . . . . . . Declaring Functions Without Prototypes . . . . . . . . . . . . Function Pointers . . . . . . . . . . . . . . . . . . . . . . . . Recursive Functions . . . . . . . . . . . . . . . . . . . . . . . Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tips: Code Documentation . . . . . . . . . . . . . . . . . . . Exercises . . . . . . . . . . . . . . . . . . . . . . An Introduction to Classes . . . . . . . . . . . . . . . . . . . . . . . 6.1 The Raison d’Être for Classes . . . . . . . . . . . . . . . . . . . 6.1.1 Problems That May Arise When Using Modules . . . . . 6.1.2 Abstraction, Encapsulation and Modularity Properties of Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 A First Example Simple Class: A Class of Books . . . . . . . . . 6.2.1 Basic Features of Classes . . . . . . . . . . . . . . . . . 6.2.2 Header Files . . . . . . . . . . . . . . . . . . . . . . . . 6.2.3 Setting and Accessing Variables . . . . . . . . . . . . . . 6.2.4 Compiling Multiple Files . . . . . . . . . . . . . . . . . 6.2.5 Access Privileges . . . . . . . . . . . . . . . . . . . . . 6.2.6 Including Function Implementations in Header Files . . . 6.2.7 Constructors and Destructors . . . . . . . . . . . . . . . 6.2.8 Pointers to Classes . . . . . . . . . . . . . . . . . . . . . 6.3 The friend Keyword . . . . . . . . . . . . . . . . . . . . . . 6.4 A Second Example Class: A Class of Complex Numbers . . . . . 6.4.1 Operator Overloading . . . . . . . . . . . . . . . . . . . 6.4.2 The Class of Complex Numbers . . . . . . . . . . . . . . 6.5 Some Additional Remarks on Operator Overloading . . . . . . . 6.6 Tips: Coding to a Standard . . . . . . . . . . . . . . . . . . . . . 6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Inheritance and Derived Classes . . . . . . . . . . . . . . . . . 7.1 Inheritance, Extensibility and Polymorphism . . . . . . . . . 7.2 Example: A Class of E-books Derived from a Class of Books 7.3 Access Privileges for Derived Classes . . . . . . . . . . . . . 7.4 Classes Derived from Derived Classes . . . . . . . . . . . . 7.5 Run-Time Polymorphism . . . . . . . . . . . . . . . . . . . 7.6 The Abstract Class Pattern . . . . . . . . . . . . . . . . . . . 7.7 Tips: Using a Debugger . . . . . . . . . . . . . . . . . . . . 7.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 8.1 Templates to Control Dimensions and Verify Sizes . . . . . . . . 8.2 Templates for Polymorphism . . . . . . . . . . 8.3 A Brief Survey of the Standard Template Library 8.3.1 Vectors . . . . . . . . . . . . . . . . . . 8.3.2 Sets . . . . . . . . . . . . . . . . . . . . 8.4 Tips: Template Compilation . . . . . . . . . . . 8.5 Exercises . . . . . . . . . . . . . . . . . . . . . Errors and Exceptions . . . . . . . . . . . . . . . . . . . . . . . . 9.1 Preconditions . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.1 Example: Two Implementations of a Graphics Function 9.2 Three Levels of Errors . . . . . . . . . . . . . . . . . . . . . . 9.3 Introducing the Exception . . . . . . . . . . . . . . . . . . . . 9.4 Using Exceptions . . . . . . . . . . . . . . . . . . . . . . . . 9.5 Tips: Test-Driven Development . . . . . . . . . . . . . . . . . 9.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Developing Classes for Linear Algebra Calculations 10.1 Requirements of the Linear Algebra Classes . . . 10.2 Constructors and Destructors . . . . . . . . . . . 10.2.1 The Default Constructor . . . . . . . . . . 10.2.2 The Copy Constructor . . . . . . . . . . . 10.2.3 A Specialised Constructor . . . . . . . . . 10.2.4 Destructor . . . . . . . . . . . . . . . . . 10.3 Accessing Private Class Members . . . . . . . . . 10.3.1 Accessing the Size of a Vector . . . . . . . 10.3.2 Overloading the Square Bracket Operator . 10.3.3 Read-Only Access to Vector Entries . . . . 10.3.4 Overloading the Round Bracket Operator . 10.4 Operator Overloading for Vector Operations . . . 10.4.1 The Assignment Operator . . . . . . . . . 10.4.2 Unary Operators . . . . . . . . . . . . . . 10.4.3 Binary Operators . . . . . . . . . . . . . . 10.5 Functions . . . . . . . . . . . . . . . . . . . . . . 10.5.1 Members Versus Friends . . . . . . . . . . 10.6 Tips: Memory Debugging Tools . . . . . . . . . . 10.7 Exercises . . . . . . . . . . . . . . . . 11 An Introduction to Parallel Programming Using MPI . 11.1 Distributed Memory Architectures . . . . . . . . . 11.2 Installing MPI . . . . . . . . . . . . . . . . . . . . 11.3 A First Program Using MPI . . . . . . . . . . . . . 11.3.1 Essential MPI Functions . . . . . . . . . . . 11.3.2 Compiling and Running MPI Code . . . . . 11.4 Basic MPI Communication . . . . . . . . . . . . . 11.4.1 Point-to-Point Communication . . . . . . . 11.4.2 Collective Communication . . . . 11.5 Example MPI Applications . . . . . . . . . . . 11.5.1 Summation of Series . . . . . . . . . . . 11.5.2 Parallel Linear Algebra . . . . . . . . . 11.6 Tips: Debugging a Parallel Program . . . . . . . 11.6.1 Tip 1: Make an Abstract Program . . . . 11.6.2 Tip 2: Datatype Mismatch . . . . . . . . 11.6.3 Tip 3: Intermittent Deadlock . . . . . . . 11.6.4 Tip 4: Almost Collective Communication 11.7 Exercises . . . . . . . . . . . . . . . 12 Designing Object-Oriented Numerical Libraries . . . . . . . . . . . 12.1 Developing the Library for Ordinary Differential Equations . . . . 12.1.1 Model Problems . . . . . . . . . . . . . . . . . . . . . . . 12.1.2 Finite Difference Approximation to Derivatives . . . . . . 12.1.3 Application of Finite Difference Methods to Boundary Value Problems . . . . . . . . . . . . . . . . . . . . . . . 12.1.4 Concluding Remarks on Boundary Value Problems in One Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2 Designing a Library for Solving Boundary Value Problems . . . . 12.2.1 The Class SecondOrderOde . . . . . . . . . . . . . . . 12.2.2 The Class BoundaryConditions . . . . . . . . . . . . 12.2.3 The Class FiniteDifferenceGrid . . . . . . . . . . 12.2.4 The Class BvpOde . . . . . . . . . . . . . . . . . . . . . 12.2.5 Using the Class BvpOde . . . . . . . . . . . . . . . . . . 12.3 Extending the Library to Two Dimensions . . . . . . . . . . . . . 12.3.1 Model Problem for Two Dimensions . . . . . . . . . . . . 12.3.2 Finite Difference Methods for Boundary Value Problems in Two Dimensions . . . . . . . . . . . . . . . . . . . . . 12.3.3 Setting Up the Linear System for the Model Problem . . . 12.3.4 Developing the Classes Required . . . . . . . . . . . . . . 12.4 Tips: Using Well-Written Libraries . . . . . . . . . . . . . . . . . 12.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . Appendix A Linear Algebra . . . . . . . . . . . . . . . . . A.1 Vectors and Matrices . . . . . . . . . . . . . . . . . A.1.1 Operations Between Vectors and Matrices . A.1.2 The Scalar Product of Two Vectors . . . . . A.1.3 The Determinant and the Inverse of a Matrix A.1.4 Eigenvalues and Eigenvectors of a Matrix . . A.1.5 Vector and Matrix Norms . . . . . . . . . . A.2 Systems of Linear Equations . . . . . . . . . . . . A.2.1 Gaussian Elimination . . . . . . . . . . . . A.2.2 The Thomas Algorithm . . . . . . . . . . . A.2.3 The Conjugate Gradient Method . . . . . . 213 Appendix B Other Programming Constructs You Might Meet . B.1 C Style Output . . . . . . . . . . . . . . . . . . . . . . . B.2 C Style Dynamic Memory Allocation . . . . . . . . . . . B.3 Ternary ?: Operator . . . . . . . . . . . . . . . . . . . . B.4 Using Namespace . . . . . . . . . . . . . . . . . . . . . B.5 Structures . . . . . . . . . . . . . . . . . . . . . . . . . B.6 Multiple Inheritance . . . . . . . . . . . . . . . . . . . . B.7 Class Initialisers . . . . . . . . . . . . . . . . Appendix C Solutions to Exercises . . . . . . . . . . . . . . . . . . . . . 231 C.1 Matrix and Linear System Classes . . . . . . . . . . . . . . . . . . 231 C.2 ODE Solver Library . . . . . . . . . . . . . . . . . . . . . . . . . 240 Further Reading . . . . . . . . . . . . . . . . . . . Mathematical Methods and Linear Algebra C++ Programming . . . . . . . . . . . . . The Message-Passing Interface (MPI) . . .