Author: Rob H. Bisseling

Publisher: Oxford University Press

Publication date (UK): September 30, 2020

Pages: 416 pages

ISBN 9780198788348 (hardback)

ISBN 9780198788355 (paperback)

ISBN 9780191092572 (ebook)

- Book page at Oxford University Press
- Electronic version at Oxford Academic
- Ebook at eBooks.com
- Book page at Amazon US
- Book page at bol.com NL
- Book page at Google Books (with sample parts from the book)
- Course Parallel Algorithms at Utrecht University by the author, Fall 2022
- Book review by Bill Satzer, Mathematical Association of America (MAA)

This is a complete set of class-tested lectures which are supplementary to the main text of the book. Each lecture corresponds to one section (or a few) of the book and has up to 25 slides, which takes about 45 min. It is given as a PDF file. The slides have been written in LaTeX/Beamer with most figures produced by TikZ or Gnuplot. If you are a teacher and want to use the slides, but would like to modify them, for instance to turn my jokes into better ones, then use the LaTeX/Beamer sources. All lectures have been updated in 2023.

All lectures are available here, as a package PSC2 Slides (42 MB), with the latest version released March 27, 2023. The format is gzipped tar. The LaTeX/Beamer sources are also available, as a package PSC2 Slides Sources (74 MB). The lectures can also be downloaded separately, through the following list.

- 1.1 The Bulk Synchronous Parallel Model
- 1.3 Parallel Inner Product Computation
- 1.4 Starting with BSPlib
- 1.5-1.7 BSP Benchmarking
- 1.8 Sorting
- 1.9 Bulk Synchronous Message Passing: bspsort
- 1.10 Experimental Results for Samplesort on Cartesius
- 2.1-2.2 Sequential LU Decomposition
- 2.3 Parallel LU Decomposition
- 2.4 Two-phase Broadcasting
- 2.5 High-Performance LU Decomposition
- 2.6-2.7 Experiments with bsplu
- 3.1-3.2 Sequential Fast Fourier Transform
- 3.3 Sequential Nonrecursive FFT
- 3.4 Parallel Fast Fourier Transform
- 3.5 Weights for the FFT
- 3.6 Program bspfft
- 3.7 Experimental results for the FFT
- 4.1 Sequential Sparse Matrix-Vector Multiplication
- 4.2 Sparse Matrices and Their Data Structures
- 4.3 Parallel Sparse Matrix-Vector Multiplication
- 4.4 Cartesian Matrix Distribution
- 4.5 Mondriaan Sparse Matrix Distribution
- 4.6 Fine-Grain and Medium-Grain Matrix Distribution
- 4.7 Vector distribution
- 4.8 Random Sparse Matrices
- 4.9 Laplacian Matrices
- 4.10 Parallel algorithm for hybrid-BSP
- 4.11 Program bspmv
- 4.12 Experimental results on Cartesius
- 5.1-5.2 Sequential Graph Matching
- 5.3 Suitors and Sorting
- 5.4 Parallel Graph Matching
- 5.5 Correctness
- 5.6-5.7 Tie-breaking and Load Balancing
- 5.8 Further improvements
- 5.9 Program bspmatch
- 5.10 Experimental results on Cartesius

I have recorded a set of videos on the theoretical parts of the book. These can be found on my YouTube channel, Professor Rob H. Bisseling, Utrecht University. Each video ends with a homework question. The answer to all these questions can be found in Solutions. But first try to solve the questions yourself, before peeking here!

A list of videos, in the order of the book sections:

- Video: The Bulk Synchronous Parallel model
- Video: Data distributions
- Video: Simple parallel algorithm
- Video: Parallel sorting
- Video: Experimental results for parallel sorting
- Video: LU decomposition
- Video: Parallel LU decomposition
- Video: Two-phase broadcasting
- Video: High-performance LU decomposition
- Video: Discrete Fourier Transform
- Video: Recursive Fast Fourier Transform
- Video: Nonrecursive Fast Fourier Transform
- Video: Parallel Fast Fourier Transform
- Video: Sequential sparse matrix-vector multiplication
- Video: Parallel sparse matrix-vector multiplication
- Video: Cartesian matrix distribution
- Video: Mondriaan sparse matrix distribution
- Video: Comparing sparse matrix distributions
- Video: Random sparse matrices
- Video: Laplacian matrices
- Video: Parallel algorithm for the hybrid-BSP model
- Video: Sequential graph matching
- Video: Suitors and sorting in graph matching
- Video: Parallel graph matching
- Video: Tie-breaking and load balancing
- Video: Reducing communication in parallel graph matching

Page last updated on March 27, 2023 by Rob H. Bisseling.