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 please send me an email and I will provide the sources. All lectures have been updated in 2020.

All lectures are available here, as a package PSC2 Slides (42 MB), with the latest version released September 1, 2022. The format is gzipped tar. 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:

Page last updated on September 15, 2022 by Rob H. Bisseling.