Revised May 23, 2014

CS 371: Introduction to Computational Mathematics

Watch a video introduction to the course on YouTube.

General description

This course introduces computational mathematics through an in-depth study of the properties of numerical algorithms.

Logistics

Audience

• CS major students and students pursuing a CS minor
• Students interested in both mathematics and computer science and interested in the computational aspects that one would encounter when solving various mathematical or scientific problems

Normally available

• Winter and Spring

Related courses

• Predecessors: (One of CS 116, 134, 136, 138, 145 taken fall 2010 or earlier, CS 146), MATH 235 or 245, 237, or 247; Not open to General Mathematics students
• Successors: CS 473, 475, 476
• Anti-requisites: CS 335, 337, 370, ECE 204
• Conflicts: AMATH 242/341, CM 271

CS 371 may be substituted for CS 370 in any degree plan or for prerequisite purposes

For official details, see the UW calendar.

Software/hardware used

• MATLAB

Typical reference(s)

• Numerical Analysis, 9th ed., R. Burden and J. Faires, Brooks Cole
• Course notes

Required preparation

At the start of the course, students should be able to

• Program in a high-procedural programming language and use control instructions, such as loops and conditional statements, basic datatypes, and simple data structures, such as arrays
• Use limits and derivatives, Taylor series, curves, max/min of multivariate functions, partial derivatives, other basic concepts encountered in calculus, and multi-dimensional integration
• Use matrix operations, inverse, products, etc., Gaussian elimination, eigenvalues, and eigenvectors

Learning objectives

• Explain the principles of floating point number systems and the concepts of chopping, rounding, machine precision, and error of floating point arithmetic
• Analyze stability and conditioning of numerical problems
• Solve nonlinear equations using iterative methods and analyze convergence of various methods
• Use MATLAB built-in functions and graphing capabilities of 1D and 2D data
• Implement efficient code using vectorization
• Use the principles of polynomial interpolation to derive and apply splines
• Use numerical methods to integrate one dimensional functions and analyze the efficiency of these methods
• Give examples of the concept of data representation using different basis functions, Fourier basis, and the FFT algorithm
• Use alternate representations in applications, such as tomographic reconstruction and filtering
• Solve linear equations in a floating point environment taking into consideration error propagation and measures of conditioning
• Explain the computational and mathematical issues involved in a large scale linear algebra problem (e.g., sparse matrix solving)

Typical syllabus

Floating point number systems (3 hours)

• Floating point numbers, propagation of round off, stability of recursions

Polynomial interpolation (4 hours)

• Interpolation: Lagrange and cubic spline

Nonlinear equations (4 hours)

• Fixed point, Newton iteration Analysis of convergence, rate of convergence

Numerical linear algebra (11 hours)

• LU decomposition, pivoting, condition number, sparse matrices, iterative methods, analysis of convergence of iterative methods, power method for eigenvectors, Google Page Rank, analysis of convergence of the power method, sparse matrices and graphs

Discrete Fourier analysis (11 hours)

• DFT pair, sampling theorem, aliasing, FFT algorithm, slice theorem, Radon Transformation, filtered backprojection for CT image reconstruction

Numerical integration (3 hours)

• Midpoint, trapezoidal, Simpson's rule, error analysis, Gaussian quadrature, Monte Carlo