Introduction to Python

This workshop will provide an introduction to the Python programming language. It will cover the basics of Python 3 syntax, and will also introduce programming aspects such as NumPy and Matplotlib that are especially relevant for AM205. The workshop will be run using Google Colab, a free cloud-based Python programming environment.

There will be several short programming exercises for students to complete, covering probability, cellular automata, and fractals.

Jovana Andrejevic, Jiayin Lu, and Matthieu Meeus

Introduction to the command line

The Linux command line is an extremely powerful tool, allowing the user to remotely access servers around the world, run simulations, and perform complex file manipulations and transfers. The command line is also built into Mac OS (via the Terminal app) and is available on Windows (e.g. via Cygwin).

The workshop will begin by covering basic commands for copying and editing files. It will discuss regular expressions for manipulating text, remote computer access via SSH, and using the “screen” and “tmux” commands for launching programs remotely. The workshop will be interspersed with several exercises drawn from codebreaking and game theory.

Danyun He and Chris Rycroft

Introduction to compiled languages

In AM205 we'll primarly use interpreted languages like Python and MATLAB. But why are compiled languages the go-to tool in coding applications as small as apps in our phones and as big as simulations on supercomputers? The reason is greater control, better performance, and a 100% legit reason to have a long break.

In this workshop, we will take a critical look at the differences between compiled languages and interpreted ones. We will also work on some coding examples together to get familiar with C++, a widely-used language in scientific computing.

Luna Lin and Baptiste Lemaire

Introduction to multithreading

For decades, each new generation of CPUs was faster than the last. This is no longer the case; since 2005, processor speeds have topped out around 4 GHz. CPU manufacturers have compensated by designing CPUs with multiple cores capable of performing multiple tasks at the same time, so advancements in hardware chiefly correspond to increases in the degree of parallelism possible. To get the best performance out of any piece of hardware, your code needs to exploit this architecture.

In this workshop, we'll discuss two frameworks for parallelization: distributed and shared memory. We will introduce the concepts for implementing shared memory parallelization in your code using Python (with joblib) and C++ (with OpenMP). Finally, we'll discuss how these concepts are used by default in libraries such as NumPy or SciPy. While there is a huge benefit to increasing performance without requiring any knowledge of parallel computing, this default can paradoxically also lead to slower performance.

With your newfound knowledge of multithreading, you'll be ready to push your laptop to the limit, fully exploit the breadth of a cluster, and avoid the pitfalls of hidden parallelism in system libraries! Either Python or C++ experience required.

Nick Derr and Luna Lin

Introduction to Cython

Here we are in 2020, the year of all tradeoffs. Nonexistent studies have explicitly shown our student community is torn by endless disputes between Pythonians and Cplusplussors. And here is why: on one end, Python is so handy, easy to use, and an excellent tool for fast prototyping. But when it comes to scientific computing, Python is slow, and sometimes too slow for a busy Harvard student. In comparison, C++ is lightning fast, but hard to use; debugging can be so complex that it will probably turn your evening work session on the latest AM205 homework into a dreadful all-nighter. Enter Cython. In an increasingly polarized world, Cython offers compromises. A bridge between Python aficionados and C++ die-hards. How? Cython can turn your Python syntax into a C-optimized executable. Actually, your favorite Python libraries like NumPy and SciPy all make use of Cython under the hood.

In this performance-or-nothing activity, we will talk about what makes Python slow and C++ fast, how to use Cython, and more importantly, when to use Cython. The world is an adventure, and by the end of this session, Cython should be your faithful companion. No C++ experience required, Python knowledge required.

Baptiste Lemaire and Matthieu Meeus

Introduction to the Kalman filter

Do you wonder how a navigation system on a car estimates its position, even when GPS signals are lost? How do we estimate quantities like position and temperature, when we don't have direct measurement, or when the measured data is noisy? The Kalman filter is an optimization algorithm that combines a physical model of the system and noisy measurements to give a best estimate of the system states (e.g. position or temperature). In this workshop, we will discuss the mathematical basis of Kalman filter, and use it in an example application.

Luna Lin and Zhiming Kuang

Introduction to POV-Ray

POV-Ray is a free ray-tracing program for making photo-realistic renderings and has a large following on the internet. On the POV-Ray website, you can browse some amazing images that people have created. POV-Ray uses a simple markup language for describing elements of a scene, such as the camera position, lights, and objects. As such, it is excellent for scientific visualization, since you can write functions in your programs to output your results in the POV-Ray syntax. This workshop will cover the basics of the POV-Ray language, and demonstrate how to create beautiful visualizations of program output.

Jiayin Lu and Chris Rycroft

Randomized linear algebra

Solving matrix problems is a cornerstone of scientific computing. As we enter the age of big data, we need scalable linear algebra (LA) algorithms more than ever. Randomized linear algebra (RLA) has been an active area of research; it applies randomization to matrix problems with a very large size, mainly to reduce data dimensionality. RLA has been applied to least squares, SVD, low rank approximation, and solving elliptic equations, among others. In this workshop, we will look at how some of these algorithms work, in particular, how to randomize in a clever way.

Luna Lin

Using the SVD for image processing

This tutorial will delve deeper into practical applications of the singular value decomposition (SVD) of a matrix. Applications of SVD are found across disciplines and include data compression, pattern or outlier detection, and unsupervised learning. This activity will focus on three image-based applications: compression, denoising, and 3D reconstruction, which are useful for building intuition about this versatile matrix factorization.

Jovana Andrejevic and Zhao Lyu

Data fitting for imaging Comet NEOWISE

Chris lives in Central Square, an urbanized neighborhood in the middle of Cambridge that has high levels of light pollution. Even on a Moonless night the sky appears as a dim gray, and only the brightest stars can be seen with the naked eye. In late July, Comet NEOWISE was visible from Earth, and Chris took a sequence of images from Central Square, where the comet is washed out by light pollution and only appears as a tiny dot.

In this workshop, we'll use the power of data fitting to eliminate the spatially-varying light pollution, revealing much more structure in the comet image. This workshop will not be dependent on any programming language, although it will involve reading and writing image files.

Chris Rycroft

Detecting abnormal heart rates in electrocardiogram signals

The Fourier transform is widely used in many scientific fields (e.g. medical imaging, seismology, astronomy) and in everyday life (e.g. your cell phones and iPods). An elegant algorithm published by Tukey and Cooley in 1965 (although Gauss apparently had the idea in 1805) known as the Fast Fourier Transform (FFT) turns the operation counts from O(N²) for a brute force approach to O(Nlog 2N), where N is the size of the problem. N of 10⁶ or more is very common these days, and you can convince yourself the time saving is worthwhile.

FFT is widely used in signal detection and signal processing. The purpose of this activity is to develop a rudimentary detector for abnormal heart beats (arrhythmias) by monitoring an electrocardiogram (ECG) signal. The ECG represents electrical activity generated by the pumping heart measured from body surface potentials. Sample ECG segments taken from the MIT-Beth Israel Hospital Malignant Ventricular Arrhythmia database with diagnoses by trained cardiologists will be provided for you to design and test your detector.

Zhiming Kuang

ENO schemes for simulating traffic and supernovae

Most numerical methods depend on smoothness in the underlying solution, usually via assumptions on the scaling of discretization error arising from Taylor series truncations. The presence of discontinuities, or “shocks,” violate these assumptions. As a result, numerical methods may fail when applied to such systems unless they are designed specifically to capture shocks. Generally, this failure takes the form of spurious oscillations in the simulated solution near the discontinuity which experience unstable growth.

Essentially non-oscillatory (ENO) schemes are a class of methods developed for the simulation of systems containing shocks. In this session, we will discuss aspects of physical systems which experience shocks, such as traffic and supernovae. We will introduce the family of ENO methods and examine two particular examples (ENO2 and WENO4). Finally, we will look at the methods in action.

No particular programming language required.

Nick Derr

Modeling an epidemic with ODEs

While taking classes in the University of Zoom under COVID-19, one may wonder how soon our life will return to normal. In this workshop, we'll learn how the SIR (susceptible, infectious, removed) model describes the spread of infectious diseases, and visualize a typical trend of infectious diseases by numerical methods. Meanwhile, we'll apply real data to summarize COVID-19 in the past few months under varying policies, and how those variabilities reflect on the SIR model and datasets.

Some programming experience in either Python or MATLAB required. This workshop will also introduce the pandas library for data analysis.

Zhao Lyu and Zhiming Kuang

Delay differential equations

While fully autonomous vehicles are not yet a reality, driver assistant programs exist in a number of car models. Through the use of radars and computers, these programs have a much shorter reaction time than human drivers. How will the introduction or adoption of such programs affect traffic jams (and accidents)? In this workshop, we will investigate such questions using Delay Differential Equations.

Zhiming Kuang

Implementing a DAE solver to simulate the chaotic double pendulum

Unlike an ODE system, a differential-algebraic system of equations (DAE) contains both differential and algebraic (constraint) equations, and thus requires special considerations to integrate. Examples of DAEs arise in complex mechanical systems, electronic circuits, and chemical kinetics problems. In this activity we will implement a DAE solver, which builds on concepts of implicit integration and Newton's method covered in lecture, and explore its application to a fun (and chaotic!) mechanical system: the double pendulum.

The structure of code in this tutorial will highlight object-oriented programming, and some basics of Python classes will be covered.

Jovana Andrejevic

Neural networks and their connection to numerical methods

In the last few years, the term 'neural network' has increasingly become a buzzword. Given enough data, the black-box modeling of deep learning is presumed to be able to tackle many of the hard problems we face. But how does it work? Is it really that hard? And how does it relate to the traditional numerical methods as covered in AM205?

This workshop is designed to unravel some of the mystery that is often associated with neural networks and aims to connect them to some of the techniques taught throughout the course. We'll cover the basic mathematical formulation of a NN (layers, weights, backpropagation) and briefly touch upon some of their many applications (such as curve-fitting, classification, CNNs, RNNs, …). We could expand on how optimization plays a decisive role, how curve-fitting from AM205 compares to NN predictions, and on how some recent research is using NNs to solve ODEs and PDEs.

The workshop would be supported by Jupyter notebook, running in an environment where Pytorch should be installed. It could be cool to use the NeuroDiffEq package to solve some basic ODEs and PDEs (link).

Matthieu Meeus

Further optimization methods

In AM205, we introduce the derivative-based optimization method: Newton's method. What if you don't know the derivative? This workshop is going to introduce two no-derivative-based optimization methods: the Golden section search method and the Brent method. It will start with the basic concepts and algorithms. We will compare different optimization methods and discuss their limitations and advantages. There will be several exercises about implementing the algorithms.

Danyun He and Jiayin Lu

Atmospheric gravity waves

Atmospheric gravity waves are an important phenomenon for weather and climate. They are also an example of interesting boundary conditions in hyperbolic equations. To represent the upwards propagation of gravity waves away from sources near the surface, it is desirable to implement a nonreflective upper boundary condition. Implementing this boundary condition however is complicated by the fact that the vertical phase speed and group velocity are of opposite signs in gravity waves. We will discuss how to implement the non-reflective boundary condition in this case and write a piece of code to simulate gravity waves excited by a thunderstorm.

Zhiming Kuang

Applying class concepts to describe convection cells

When fluid is heated from below, the density near the container bottom becomes smaller than that near the top. Above a critical temperature, the low-density fluid begins to rise, and the resulting exchange of fluid organizes into convection cells. (This instability is remarkably general: it describes behavior you can generate on your stove as well as convection zones in stars.) We can combine a variety of concepts of AM205 to calculate the size of these cells and the onset temperature of convection!

In this activity, we will analyze the system of equations describing Rayleigh–Bénard convection (i.e. in a container with open top heated from the bottom.) We will show that various modes of convection correspond to eigenfunctions of a differential operator whose corresponding eigenvalues represent the temperature at which the mode arises. We will discuss how to represent the differential operator as a matrix, and how to use the concept of ghost nodes to implement appropriate boundary conditions. Finally, we will apply a Krylov subspace method to calculate the operator's eigenspectrum.

No particular programming language required.

Nick Derr

A one-dimensional implementation of multigrid method

AM205 will introduce the multigrid method, a highly efficient iterative approach for solving a class of sparse matrix problems. This workshop will go into more detail about the theory and application of multigrid methods. We will implement the multigrid method in one dimension, and compare its efficiency to other approches such as the Jacobi and Gauss–Seidel methods. We will also discuss contemporary developments in multigrid research, as well as available software libraries that implement the method.

Danyun He

Final project presentations

In this special group activity, students will give a talk on their final project. This will be organized into several 2 h sessions.

For a project team of n students, the talk length should be (3n+6) min in total. Each student in the group should speak for part of the talk. Each talks will be followed by a short Q&A session. Students are expected to attend the full 2 h session and listen to the talks given by other students.

For grading, this will count as two group activities.