15-852A 21-860 Scientific Computation, Fall 1997

Course Information

Lectures: MW 12-1:20PM , 206 Student Center

NOTE TIME and ROOM CHANGE

Instructors:

Gary Miller (Doherty 4307, glmiller@cs.cmu.edu, 268-2631. Office Hours: TBA)

Noel Walkington (Wean 6208, noelw@cmu.edu, 268-6291. Office Hours: Any Time)

Course Secretary: Cleah Schlueter (Doherty 4301J, cleah@cs.cmu.edu, x8-3779)

Credits: 12 Units, 1 CU

Evaluation and Responsibilities: Grading will be based on a collection of homework assignments (50%), a final exam (30%), and class project (20%). The class project will consist of either an implementation or review of a topic. Time permitting, the student will present to the class their project.

Text: There is no assigned text. Relevant chapters and note will be made available. Rough lecture notes will be made available on the web page http://www.cs.cmu.edu/~glmiller/sci-comp/home.html.

Course description: This course will apply techniques from Computer Science and Numerical Analysis to problems in large scale Scientific Computation. The goal of this course is to give a broad introduction to algorithmic and combinatorial issues that arise in scientific computation. Our main emphasis will be the design and analysis of efficient parallel and sequential algorithms with good numerical properties. The problems are motivated by problem from the Sciences as well as the Engineering.

Specific topics to be covered include:

• Finite Precision Arithmetic
  • Motivation: Examples where Precision Problems Occur
  • Basics of IEEE 754/854 Standard
  • Forward and (Wilkinson's) Backward Error Analysis
  • Special Algorithms for Accurate Computation
  • Comments on Interval and Other Exact Computational Models
• Mesh Generation
  • Related Computational Geometry
    • Delaunay Diagrams
    • Voronoi Diagrams
    • Convex hull
  • Quadtree Based Methods
  • Delaunay Based Methods
  • Conformal Mapping Methods
• Application to Algorithms for Approximating PDE
  • Structure of Elliptic PDE's
  • Approximation Theory
  • Error Estimates for FE, FD, CV Methods
  • Role of Mesh Geometry
• Linear Algebra
  • Graph Embeddings to Estimate Eigenvalues
  • Solving Sparse Linear Systems
    • General Framework
    • Cost of Direct Methods
    • Nested Dissection
    • Iterative Methods
    • Preconditioners for Iterative Methods
• Graph Separators
  • Spectral Methods
  • Geometric Methods
  • Multi-Commodity Flow
  • Application to Linear Equations
• Elementary Hilbert Space Methods: The analysis of Iterative Methods for linear equations, Algorithms for PDE's, Eigenvalue Calculations and Approximation Theory will be facilitated using techniques of normed linear and inner product spaces. These topics will be introduced as needed and will provide a unifying framework for understanding the various problems and algorithms.