CSCI-GA.2112-001

Scientific Computing

Aaditya Rangan

Graduate Division

Computer Science


Lecture: Class meets for 2 hours each week; Thursday: 5:10pm - 7:10pm.

Topics covered: This course is intended to provide a practical introduction to computational problem solving.

The first part of the course involves a rather in-depth review of linear-algebra, culminating in the numerical solution of ordinary-differential-equations (ODEs).

To begin with, we will review some basic techniques for the numerical solution of linear and nonlinear equations, and for numerical optimization [Topics include LU and QR factorizations, as well as Newton's method]. This will set the stage for the discussion of well-conditioned and poorly conditioned problems [Topics include condition number of a matrix]. This discussion relies heavily on the singular-value-decomposition (SVD), which we explain in some detail [Topics include SVD/PCA, as well as power-iteration for finding eigenvectors]. If we have time, we'll touch on the related notions of forward and backward stability of an algorithm [Topics include floating-point-arithmetic and the "modified" graham-schmidt algorithm].

Following this review, we will then discuss the basic principles underlying numerical interpolation, differentiation and integration [Topics include regression/least-squares, splines, gaussian quadrature and Runge's phenomenon]. This will lead to numerical methods for solving ordinary differential equations [Topics include multistep, Runge-Kutta and collocation methods]. Along the way, we'll discuss concepts such as convergence and linear stability, which are important for the practical application of these numerical methods.

At this point, we'll have the basic tools at our disposal to manage many of the simpler systems of ODEs that emerge from mechanics and chemical kinetics. In the second part of the course I'd like to discuss the numerical solution of elliptic/parabolic partial-differential-equations (PDEs).

To provide motivation for this topic, we'll begin by reviewing some of the basic principles of discrete markov processes [Topics include the page-rank algorithm]. At this point we'll be able to make a connection between Markov processes at a microscopic scale and diffusion processes at a larger scale [Topics include conservation laws]. We can then use the diffusion equation (i.e., heat equation) to frame a discussion of finite-element methods for elliptic/parabolic PDEs. I'll briefly mention boundary-integral methods, but won't go into details. If I have time, I'll expand the discussion above to include stochastic processes at an intermediate scale -- introducing stochastic calculus [Topics include Brownian motion, Ito's Lemma and Kolmogorov forward/backward equations].

Finally, we'll use our previous discussion of the heat-equation as motivation for the discrete/fast Fourier transform (FFT). We will conclude with some applications of the FFT, including the convolution theorem [Topics also include basic signal processing and data compression].

Evaluation: There will be weekly homework assignments (roughly 14 total). These will include a mixture of theory (e.g., proofs) and practice (e.g., code). Some will be slightly larger than others, serving as take-home exams. You are encouraged to work in groups on these homeworks, but each student is required to hand in their own version of each homework.