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

These advanced videos present research results connected to recently published articles. Often these are based on earlier videos from the book. The videos beyond the book can be found on the same YouTube channel.

Page last updated on October 5, 2023 by Rob H. Bisseling.