CSE Courses

Engineering at Illinois Engineering at Illinois

Course Syllabus

Course Objectives
To learn how to design and implement efficient parallel numerical algorithms for commonly occurring problems in scientific computing and how to analyze their performance and scalability. Primary focus will be on problems in linear algebra and differential equations, but design principles learned are applicable to a wide variety of problems in science and engineering.
Detailed Syllabus
Parallel Computing
  • Motivation
  • Architectures
    • Taxonomy
    • Memory Organization
  • Networks
    • Network Topologies
    • Graph Embedding
  • Communication
    • Message Routing
    • Communication Concurrency
    • Collective Communication
Parallel Algorithm Design
  • Computational Model
  • Design Methodology
    • Partitioning
    • Communication
    • Agglomeration
    • Mapping
  • Example
Parallel Programming
  • Parallel Programming Paradigms
    • Functional languages
    • Parallelizing compilers
    • Object parallel
    • Data parallel
    • Shared memory
    • Remote memory access
    • Message passing
  • MPI – Message-Passing Interface
    • MPI Basics
    • Communication and Communicators
    • Virtual Process Topologies
    • Performance Monitoring and Visualization
Parallel Performance
  • Analysis
    • Basic Definitions
    • Amdahl's Law
    • Problem Scaling
    • Isoefficiency and Scalability
    • Speedup and efficiency
    • Scalability
    • Communication modeling
    • Isoefficiency function
  • Modeling
Vector and Matrix Products
  • Inner product
  • Outer product
  • Matrix-vector product
  • Matrix-matrix product
  • Row, column, and submatrix partitioning
LU Factorization
  • ijk forms of Gaussian elimination
  • Row, column, and submatrix partitioning
  • Partial pivoting and alternatives
Cholesky Factorization
  • ijk forms of Cholesky factorization
  • Memory access patterns
  • Data dependences
  • Sparse Cholesky factorization
  • Elimination trees
  • Fan-out, fan-in, and multifrontal algorithms
Triangular Systems
  • Row vs. column partitioning
  • Fan-in and fan-out algorithms
  • Wavefront algorithms
  • Cyclic algorithms
  • Submatrix partitioning
Band and Tridiagonal Systems
  • Cyclic reduction
Iterative Methods for Linear Systems
  • Stationary iterative methods
  • Conjugate gradient method
  • Preconditioning
  • Partitioning
  • Coloring
QR Factorization
  • Householder QR factorization
  • Givens QR factorization
Eigenvalue Problems
  • Power and inverse iteration
  • Preliminary reduction and QR iteration
  • Arnoldi and Lanczos methods
  • Spectrum-slicing methods
  • Divide-and-conquer method
  • Singular value decomposition
Fast Fourier Transform
  • Discrete Fourier transform
  • FFT algorithm
  • Binary exchange algorithm
  • Transpose algorithm
Other Numerical Problems
  • Nonlinear equations
  • Optimization
  • Numerical integration
  • Ordinary differential equations
Partial Differential Equations
  • Domain decomposition
  • Schwarz method
  • Schur method
  • Multigrid
Particle Simulations