#### 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

##### 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