Semester Course

Computational Science and Engineering

1.Applications, Algorithms, and Architectures.

1.1.Introduction

The purpose of this course is to introduce concepts of computational science and engineering or CSE. CSE is the conduct of application area research and development in which the computer plays an essential role. Essential is the operative term: computation and computational concepts are indispensible. For most students, the application area is science or mathematics and CSE means modeling of physical phenomena and solving the problems posed by the model. There are other applications, such as economics, which are model based. But there can be non-modeling issues: financial algorithms often suffer from having been defined and standardized without the benefit of understanding finite arithmetic.

Once the mathematical problems are posed, we need to develop algorithms to solve those problems. If a problem is one that commonly occurs, there may well be appropriate algorithms defined. It is quite possible that a new algorithm must be found. Mathematical functions must be discretized, thereby introducing numerical error and introducing the theory of Taylor series. But there are many problems that are not mathematical functions in the usual undergraduate sense: functions based on stochasitic information, for example.

Having stated an algorithm is not the same as having a good implementation of the algorithm. The entire software and hardware architecture adds to the complexity of the solution and also introduces its own errors.

Finally, we still have questions of correctness to address. There are two types: verification and validation. Seen in a software engineering perspective, the model represents the specification for the algorithm and attendant software. The verification question asks “Did we build the system right?” That is, given the specification, does the algorithm and implementation correctly follow the specification? Even if the system is verified, it could be the case that the model itself is not corret. The validation question is “Did we build the right system?” Both questions must be answered in the affirmative.

1.2.Course Conduct

This course is primarily a seminar type course. It is also a quintessential problem-based learning (PBL) course. The PBL approach uses problems as the organizational principle, not traditional text books. We will do much experimentation with the computer, including some programming, use of standardly available numerical software, and computer aided algebra programs like Maple. We will follow the A3V2 rubric.

2.IEEE 754 Floating Point Standard — “String Around the World”

2.1.Synopsis

Consider taking a weightless string and winding it once around the earth at the equator. The string has some length, call it L, measured in meters. Now add 10 inches to L. You are a project manager for a project to design a vertical tower that will pull this string taut. Write a computer program to compute the height of this tower and give the bounds of certainty on your answer.

2.2.Formulation and Hints

This problem is a simple trigonometric equation that can be formulated based on a simple diagram. You will need to remember that the arc length l of an arc on a circle of radius r and of  radians is l=r.

2.3.Requirement

Once the problem has been formulated, you will have a transcendental equation to solve. The simplest to code is the bisection algorithm. You can use online codes (such as are available at Netlib) or a computer algebra system such as Maple or Mathematica.

2.4.Initial Reading Assignment

Read the IEEE Standard 754 on binary floating point arithmetic. Follow the directions for reading and concept development.

3.Using Multiple Evaluations For Statisitical Properties — “String Around the World Revisited”

3.1.Synopsis

One way we could determine the uncertainty of the length of the string is to statistically evaluate the algorithm. Such a library is available for writing such algorithms. We will experiment with the software to determine its validity.

4.Root Finder in Interval Arithmetic with C-XSC

4.1.Synopsis

The traditional view of numerical algorithms is to do round-off error analysis and then determine the size of the error of the result from this analysis. An alternative proposed by Moore in the late 1950s was to compute the interval in which the result lies. This is not the same as the round-off analysis. The compiler C-XSC is a C language compiler that does interval arithmetic. We will use the C-XSC language to finish the String problem.

5.Simulated Annealing — The Roller Coaster

5.1.Synopsis

The brachistochrone problem was one of the first problems solved by Newton after he had a working version of calculus. The brachistochrone problem is as follows: Given a particle at initial coordinates (0,y) and final coordinates (x,0), what is the trajectory of the path from the initial to final coordinates that takes the shortest time? For any realistic discretization, the time complexity of the deterministic solution is very long. We will use simulated annealing to solve this problem. You will be provided a working Java driver.

6.Discrete Event Simulation — 3-dimensional Billiards

6.1.Synopsis

Many problems in science are stated in terms of stochasitic functions: functions defined by probabilities. We will investigate such a problem us the technique of discrete event simulation.

7.Systems of Ordinary Differential Equations — The Non-Linear Pendulum

7.1.Synopsis

We take on your sophomore physics book by re-developing the “theory of pendula.” This is the exploration of systems of linear and non-linear ordinary differnetial equations using standardly available software.

8.Partial Differential Equations — The Hot Rod

8.1.Synopsis

Partial differential equations have more than one spatial dimension. We develop a simple solution for the heating of a rod which sits on a hot plate.