Scientific Computing Overview

Carnegie Mellon University, School of Computer Science

15-859C Introduction to Scientific Computing (Spring 2003)
Prof. Gary Miller

Time T-TH 10:30-12
Location Wean 4623
Instructor Gary Miller 
[mail | Wean 7130 | 8-2631]
office hours: ?
Secretary Charlotte Yano
[mail | Wean 7120 | 8-7656]
Textbooks None
Web page Scientific Computing
Other references
  • TBA


Scientific computation is the broad field concerned with the design and analysis of numerical algorithms. The simplest examples are solving a linear system of equations or finding the eigenvalue and eigenvectors of a matrix. These numerical algorithms are central to design, testing, and understanding of enumerable physical objects. The design of building, ships, artificial organs, to ink jet printers all use these algorithms. Numerical algorithms also appear in other parts of science and engineering. Google uses eigenvectors of graphs to rank pages on the Internet. Eigenvectors are used to partition large graphs for storage over multiple machines.

On the other hand computer science algorithm theory is playing a larger role in the design of new faster numerical algorithms. As an example in the 1970's researcher showed how efficient algorithms for Gaussian elimination could be expressed as a purely graph theoretic problem. This formulation dramatically changed how we view Gaussian elimination and how we design algorithms for it.

More recently, the focus has been on iterative system solvers. Here again, at least for some very important special cases, the problem can be expressed in graph theoretic ways. In this case understanding eigenvalues of graphs plays an important role.

In this class we shall cover both classic numerical algorithms as well as show the interplay with combinatorics, graph theory, and spectral graph theory.


There will be about five graded problem sets. Students will be expected to take and prepare notes for one or two lectures. There will be no exams .


Tentative list of topics

Solving Sparse Linear Systems
 Direct Methods
 Pivot Strategies
    For fill:  Nested Dissection
    For Numerical Stability

Solving Sparse Linear Systems
 Iterative Methods
   General Framework
   Chebyshev Method
   Conjugate Gradient
   Preconditioners for iterative methods

Eigenvalue Calculations and Estimation
   QR Algorithm
   The Singular Value Decomposition
   Lanczos Algorithm
   Graph Embeddings as an Eigenvalue Estimator
   Cheeger inequality

Graph Separators
   Spectral Methods
   Geometric Methods
   Multi-Commodity Flow
   Application to Linear Equations

Mesh Generation
   Related Computational Geometry
      Delaunay Triangulations
      Voronoi Diagrams
      Convex hull
   Quadtree Based Methods
   Delaunay Based Methods
   Conformal Mapping Methods

Algorithms for Approximating PDEs
   Structure of Elliptic PDEs
   Finite Element
   Finite Difference
   Control Volume