Rob Bisseling
Name : Rob Bisseling
Function : Professor in Scientific Computing
Department : Mathematics
Utrecht University
the Netherlands
Postal Address: PO Box 80010
3508 TA Utrecht
the Netherlands
For visiting : Budapestlaan 6
De Uithof
Utrecht
room MI 517
Email (note the spam prevention) : R. H. Bisseling "AT" uu. nl
Phone : +31 302531481
Fax : +31 302518394
Bulk: a Modern C++ Interface for BulkSynchronous Parallel Programs (August 20, 2018)
Bulk: a Modern C++ Interface for BulkSynchronous Parallel Programs by JanWillem Buurlage, Tom Bannink, and Rob H. Bisseling,
in Proceedings EuroPar 2018, Lecture Notes in Computer Science, Vol. 11014, Springer, 2018, pp. 519532.
Published version.
Software available from Bulk repository on Github.
New: release of Mondriaan 4.2 (September 14, 2017)
Information on the Mondriaan package.
Download the latest version of the
Mondriaan software, version 4.2 (tar gzipped).
Version 4.2 contains several improvements compared to version 4.1.
These are:
 A zerovolume search based on finding connected components is performed before every bipartitioning, to perform easy splits quickly if they exist.
 Improved load balance by moving free nonzeros (in a row and column that are both cut) after every bipartitioning.
 Overall speed improvements.
 A separate MondriaanStats program which is able to quickly determine the communication volume and other information about a computed partitioning.
Right: linocut "Dr. Mondrian" by Henk van der Vorst (August 2010).
Henk's web gallery.
New: release of SAWdoubler version 2.0 (March 28, 2017)
SAWdoubler software.
SAWdoubler is a software package for counting the number
of selfavoiding walks on a regular lattice, based on
the lengthdoubling method described in:
Exact enumeration of selfavoiding walks
by Raoul D. Schram, Gerard T. Barkema, and Rob H. Bisseling,
Journal of Statistical Mechanics: Theory and Experiment (2011)
p06019.
The aim of the package is to enable counting selfavoiding walks on a variety
of lattices, and stimulate research into this topic.
Please feel free to explore the possibilities of modifying this program.
Have fun!
New features of version 2.0:
 The number of walks Z_N can now be determined for every integer N,
in particular odd N. The lengthdoubling method computes Z_(N+M) for every
pair of integers N, M >= 1.
 The squared endtoend distance P_N is also computed, defined as the sum
of the squared Euclidean distances of the endpoints of all the
selfavoiding walks.
 New lattices have been added to the simple cubic (SC) lattice:
BodyCentred Cubic (BCC), FaceCentred Cubic (FCC).
 A parallel version is included based on the
MulticoreBSP library for
easy shared memory parallel programming.
Results on the BCC and FCC lattice are obtained and analysed in
Exact enumeration of selfavoiding walks on BCC and FCC lattices
by Raoul D. Schram, Gerard T. Barkema, Rob H. Bisseling, and Nathan Clisby",
arXiv:1703.09340 [condmat.statmech] March 27, 2017.
Accepted for publication in Journal of Statistical Mechanics: Theory and Experiment.
New: Slides (in Dutch) Lunchlezing tentoonstelling Imaginary, February 8, 2017, Stadskantoor Utrecht
Slides of the lecture Wiskunde in Stijl; van Mondriaan tot matrix
Download of the embedded movies:
Matrix LNS_3937
Matrix pi
New:
Hot Topic in ACM Computing Reviews (June 2016)
Thinking in Sync: The BulkSynchronous Parallel Approach to LargeScale Computing
by Rob H. Bisseling and AlbertJan N. Yzelman,
ACM Computing reviews, Vol. 57, No. 6 (2016), pp. 322327.
Essay on stateoftheart in bulksynchronous parallel computing,
with related web resources.
Oratie (Inaugural lecture)
Tuesday December 8, 2009 16.15 hour: Oratie Rob Bisseling,
"Parallel, groen en snel" (in Dutch),
Aula Academiegebouw, Domplein 29, Utrecht.
Information
Books
Proceedings 58th European Study Group Mathematics with Industry,
Utrecht 29 Jan.  2 Feb. 2007. Edited by Rob Bisseling, Karma Dajani, Tammo Jan Dijkema,
Johan van de Leur, Paul Zegeling. Published 30 December 2007.
115 pages.
PDF file of book (2.6 MB).
Topics: Modeling a heart pump (AMC), cabin crew rostering (KLM),
sampling for maskless lithography of computer chips (ASML),
optimising a closed greenhouse (Innogrow), optimising a 7tesla
MRI scanner for individual patients (UMC), pricing options based on variable interest rates and
volatilities (ING).
Website of the Study Group.
Parallel
Scientific Computation: A Structured Approach using BSP and MPI,
by Rob H. Bisseling,
Oxford University Press,
March 2004. 324 pages. ISBN 9780198529392.
Official home page of the book at the UK site of Oxford University Press.
The page contains a detailed description of the book contents, but also the complete first chapter, 49 pages, as a sample in PDF format.
This chapter is a primer on BSP and BSPlib.
Electronic version from Oxford Scholarship Online (OSO).
Available since September 2007. The book is available as part
of a collection of 1300 Online books from Oxford University Press.
The full texts of the collection are accessible
if your library has subscribed to OSO.
This book is the first text explaining how to use the bulk synchronous parallel (BSP) model and the freely available BSPlib communication library
in parallel algorithm design and parallel programming.
Aimed at upper level undergraduates,
graduate students and researchers in mathematics, physics and computer science,
the main topics treated in the book are core topics in the area
of scientific computation and many additional topics are treated in
numerous exercises. An appendix on the messagepassing interface (MPI)
discusses how to program in BSP style using the MPI communication library.
MPI equivalents of all the programs are also presented.
Book page at Amazon (US). New feature: this page gives access to sample pages, complete table of contents, index,
front/back cover, and it allows you to search in the complete text.
It even has a concordance: the most frequently used words (out of 78,753) are:
processor (903), matrix (624), algorithm (522), distribution (519),
communication (419), vector (406), cost (334), parallel (320), number (312),
superstep (297), row (292), computation (285), time (283),
data (282).
Book page at Barnes and Noble (US).
An extensive book review has appeared in
ACM Computing Reviews June 5, 2006
by Diego Llanos.
Other book reviews have appeared in
Scalable Computing:
Practice and Experience Volume 7, No. 2, June 2006 by Ami Marowka;
Zentralblatt MATH
2006, by Willi Schonauer;
Jahresbericht der DMV 2005 (in German) by Timo von Oertzen.
Additional teaching material is available through my
parallel algorithms course page:
PDF files of my lectures,
which closely follow the book; their sources
in LaTeX. This allows teachers (and students)
to adapt my material and replace
my jokes by better ones.
The material is now complete and covers all sections of the book
(January 24, 2007).
What's new?

Reports by science writer Anouck Vrouwe of the Study Week Mathematics with Industry 2015
organised in Utrecht, January 2630, 2015.

Efficient matching for column intersection graphs by
B. O. Fagginger Auer and R. H. Bisseling,
ACM Journal of Experimental Algorithmics, 19 (2014), Article 1.3.
Improves the coarsening of a multilevel sparse matrix partitioning
by exploiting better graph matching methods for the graph corresponding to A^TA.

Big graphs for big data: parallel matching and
clustering on billionvertex graphs
by Rob Bisseling, talk at AMLaGAP 2014 workshop, Orleans, France,
May 19, 2014.
Shorter version
presented during study trip to Asia with student union
AEskwadraat, July 2014.

Nieuw wiskundig record zelfmijdende wandelingen
Press release (in Dutch) July 6, 2011.

Exact enumeration of selfavoiding walks by R. D. Schram, G. T. Barkema,
and R. H. Bisseling. Journal of Statistical Mechanics: Theory and Experiment
(2011) p06019.
(Final preprint.) Publisher's final version.
Presents a new method for counting
selfavoiding walks based on the inclusionexclusion principle from combinatorics.
This lengthdoubling counts walks of length 2N by combining pairs of walks of length N.
The method is used to move the current record in 3D on the simple cubic lattice from N=30 to N=36.
 March 8, 2011.
MulticoreBSP released. An objectoriented version of BSPlib
in Java aimed at multicore architectures, developed by AlbertJan Yzelman and
Rob Bisseling.
Paper: An Objectoriented BSP Library for Multicore Programming
by AlbertJan Yzelman and Rob Bisseling,
Concurrency and Computation: Practice & Experience, 2011.
doi:10.1002/cpe.1843

Geometric Approach to Matrix Ordering
by B. O. Fagginger Auer and Rob H. Bisseling,
Technical Report. Submitted to arXiv:1105.4490v1" May 23, 2011.
Presents a recursive way to partition hypergraphs which creates and exploits
hypergraph geometry and is suitable for manycore parallel architectures. Such partitionings are then
used to bring sparse matrices in a recursive Bordered Block Diagonal form (for processoroblivious
parallel LU decomposition) or recursive Separated Block Diagonal form (for cacheoblivious sparse
matrixâ€“vector multiplication). The partitioning is based on a geometric
representation in d dimensions, with d=4 a good choice for implementation on a GPU.

A cacheoblivious sparse matrixvector multiplication scheme based on the Hilbe
rt curve
by AlbertJan N. Yzelman and Rob H. Bisseling,
submitted, October 15, 2010. To appear in Proceedings
European Conference on Mathematics for Industry 2010.
Uses the Hilbert curve in 2D to achieve a cacheoblivious SpMV
and proposes the Bidirectional Incremental Compressed Row Storage (BICRS)
data structure. Speedups of up to a factor two are attained for the SpMV multiplication y = Ax on sufficiently large, unstructured matrices.

Twodimensional cacheoblivious sparse matrixvector multiplication
by AlbertJan N. Yzelman and Rob H. Bisseling,
Parallel Computing, 2011.
doi:10.1016/j.parco.2011.08.004
Extends our previous 1D cacheoblivious method for SpMV to 2D.
Introduces the Doubly Separated Block Diagonal (DSBD) sparse matrix form,
and also a family of recursive sparse blocking schemes for
matrices in DSBD form. The new method obtains
speedups of up to a factor of 3 compared
to the natural ordering with the CRS datastructure.

Parallel Greedy Graph Matching using an Edge Partitioning Approach"
by Md.~Mostofa Ali Patwary, Rob H. Bisseling, and Fredrik Manne.
Proceedings of the Fourth ACM SIGPLAN Workshop on Highlevel Parallel Programming and Applications (HLPP 2010), pp. 4554, September, 2010.

Sparse matrix partitioning, ordering, and visualisation by Mondriaan 3.0
by Rob Bisseling, AlbertJan Yzelman, Bas Fagginger Auer.
Slides of lecture presented at the Workshop Scheduling in Aussois, France,
June 4, 2010.

Combinatorial problems in HighPerformance Computing
by Rob Bisseling.
Slides of lecture presented on March 24, 2010 at the EIDMA seminar Combinatorial Theory,
Eindhoven University of Technology, the Netherlands.

Teaching parallelism in an interdisciplinary scientific computing programme
by Rob Bisseling.
Slides of lecture presented on February 24, 2010 at the SIAM Conference
on Parallel Processing for Scientific Computing in Seattle, USA.

A. N. Yzelman and Rob H. Bisseling
Cacheoblivious sparse matrixvector multiplication by using sparse matrix partitioning methods by AlbertJan N. Yzelman and Rob H. Bisseling,
SIAM Journal on Scientific Computing,
31, No. 4 (2009) pp. 31283154.
Original version of August 20, 2008.
Describes a cacheoblivious method for sparse matrixvector multiplication,
which attempts to permute the rows and columns of the input
matrix using a hypergraphbased sparse matrix partitioning scheme
so that the resulting matrix induces cachefriendly behaviour during sparse matrixvector multiplication.
In the numerical experiments, an adapted version of
the Mondriaan sparse matrix partitioner is used.

"Increasing Detection Performance of Surveillance Sensor Networks"
by
Nelly Litvak,
Muhammad Umer Altaf,
Alina Barbu,
Sudhir Jain,
Denis Miretskiy,
Leila Mohammadi,
Ertan Onur,
Jos in 't panhuis,
Julius Harry Sumihar,
Michel Vellekoop,
Sandra van Wijk, and
Rob Bisseling,
in Proceedings Study Group Mathematics with Industry 2008, University of Twente,
pp. 95115. Published December 2008.

A Parallel Approximation Algorithm for the Weighted Maximum
Matching Problem, by Fredrik Manne and Rob H. Bisseling.
In proceedings of The Seventh International Conference on Parallel Processing
and Applied Mathematics (PPAM 2007), Springer LNCS, Vol. 4967 (2008)
pp. 708717.
Final
preprint version. Picture right: authors at Dagstuhl Castle, Germany,
participating in the workshop on Combinatorial Scientific Computing, February 2009.

Computational eScience: Studying complex systems in silico. A National Coordinated Initiative. White paper by P. M. A. Sloot, D. Frenkel, H. A. van der Vorst,
A. van Kampen, H. E. Bal, P. Klint, R. M. M. Mattheij, J. van Wijk, J. Schaye,
H.J. Langevelde, R. H. Bisseling, B. Smit, E. Valenteyn, H. Sips,
J. B. T. M. Roerdink, and K. G. Langedoen (February 2007).
Presents the vision of the Dutch national initiative
'Computational eScience', which is to advance innovative,
interdisciplinary research where complex multiscale, multidomain problems
in science and engineering are solved on distributed systems,
integrating sophisticated numerical methods,
computation, data, networks, and novel devices.

Mondriaan
sparse matrix partitioning for attacking cryptosystems
by a parallel block Lanczos algorithm  a case study,
by Rob H. Bisseling and Ildiko Flesch,
Parallel Computing
32 Nr. 7/8 (2006) pp. 551567.
Final preprint version.

Brainstormen voor bruikbare wiskunde,
by
Rob Bisseling, Alistair Vardy,
Mark Peletier, and Natacha Severens
(corresponding authors)
Nieuw Archief voor Wiskunde
Vol. 5/7, Nr. 1 (March 2006), pp. 44  51.
Presents three problems from the
Study Group Mathematics and Industry 2005.
Includes shorter Dutch version of
Partitioning a Call Graph.

Computing Approximate Weighted Matchings in Parallel by Fredrik Manne,
Rob Bisseling, and Alicia Permell.
Lecture at
SIAM Conference on Parallel Processing for Scientific Computing
San Francisco. February 2224, 2006.
(13 transparancies, 64kB, PDF format)

Parallel Hypergraph Partitioning
for Scientific Computing
by K. D. Devine, E. G. Boman, R.T. Heaphy, R. H. Bisseling, and U. V. Catalyurek,
in Proceedings IEEE International Parallel & Distributed Processing Symposium 2006, IEEE Press.

Communication
balancing in parallel sparse matrixvector multiplication
by Rob H. Bisseling and Wouter Meesen,
Electronic Transactions on Numerical Analysis
21 (2005) pp. 4765
(special issue on Combinatorial Scientific Computing).
Describes improved algorithms for vector partitioning in sparse matrixvector
multiplication, which will be included in Mondriaan version 2.

Symposium
Parallel Scientific Computation, April 1, 2004, Utrecht University.
On the occasion of the publication of my book.
Gerard Tel took
pictures
at the symposium. Watch the special pie!

BSPedupack and MPIedupack version 1.01
. Official release v1.0: January 30, 2004.
Latest release v1.01: August 30, 2012. Software packages with all program texts
from the book Parallel
Scientific Computation: A Structured Approach using BSP and MPI,
together with test programs. Released under the GNU General Public License.
Available in BSPedupack: dense LU decomposition; onedimensional FFT;
a simple how to get started bulk synchronous parallel program
that shows 12 of the 20 BSPlib
primitives in action computing an inner product of two vectors;
a sparse matrixvector multiplication program that
shows the 5 bulk synchronous message passing
primitives in action;
and a BSP benchmark program that measures
the computation, communication, and synchronisation performance
of your parallel computer.
Available in MPIedupack: MPI versions of all BSPedupack programs.
Demonstrates the use of the collective communications from MPI1 and
the onesided communications from MPI2.

Opgave en
Oplossing parallel rekenen Kaleidoscoop (10 maart 2003) en Voorlichtingsdag
20 maart 2004
(in Dutch).

"Partitioning 3D space for parallel manyparticle simulations" by
M. A. Stijnman, R. H. Bisseling, and G. T. Barkema,
Computer Physics Communications
149, No. 3 (2003) pp. 121134.
Final preprint version.
Partitioning 3D space based on the BCC, FCC, and HCP
sphere packings
reduces communication by up to 16 percent,
compared to simplecubic partitioning.
Particles in space are assigned to the nearest sphere centre,
which represents a processor.
The new partitioning approach can be used for
a wide range of numbers of processors, and is particularly
advantageous for powers of two.
Your greengrocer knows how to stack oranges,
and this paper tells you how to use this in molecular dynamics
and other manyparticle simulations.
Research
My research interests are
 parallel algorithms
 sparse matrix computations
 bioinformatics
 computational science
Courses in 2017/2018
Courses in 2016/2017

Parallel Algorithms (WISM 459).
Fall semester 2016. Teacher: Rob Bisseling. Teaching assistant: Abe Wits.

Topic Combinatorial Scientific Computing, part of
Orientation on Mathematical Research ,
Group 2. November 21  December 5, 2016.
We will study "Combinatorial Problems in Solving Linear Systems"
by Iain Duff and Bora Ucar,
Chapter 2 of
Combinatorial Scientific Computing,
CRC Press, Taylor & Francis Group, Boca Raton, FL, 2012,
pages 2168.
Online openaccess version.

Mathematical Modelling: Networks (UCSCIMAT22) at University College Utrecht,
Spring semester 2017.
Teachers: Anton van de Ven and Rob Bisseling.

Mathematics for Industry (WISM101), February 10, 2017  April 7, 2017.
Teachers: Fieker Dekkers (RIVM) and Rob Bisseling.
Some of my work

The final version of the BSPlib report has appeared in
Parallel Computing
24 (1998) pp. 19471980.
This paper is the
definitive description of the BSP programming library
and includes a handy quick reference chart.
An older version (without the chart) is online available:
BSPlib: the BSP Programming Library, by Jonathan Hill, Bill McColl,
Dan Stefanescu, Mark Goudreau, Kevin Lang,
Satish Rao, Torsten Suel, Thanasis Tsantilas,
and Rob Bisseling,
version with C examples or with
Fortran 77 examples.

Een parallel buffet (in Dutch).
Parallel rekenen uitgelegd aan de hand van gebeurtenissen
bij een lopend buffet.
A story explaining parallel computing
in BSP style through events at a dinner party.
Published in the student magazine Vakidioot, Utrecht University, March 1998.
Interesting links
Meet me at

Deltares, Delft, lunch seminar, November 8, 2010.
Partitioning for applications:
using Mondriaan in meshbased computations,
by Rob Bisseling,
AlbertJan Yzelman and Bas Fagginger Auer.

CERFACS, Toulouse, visit MayJuly 2010.
Partitioning for applications,
CERFACS Seminar, July 13, 2010 by Rob Bisseling,
AlbertJan Yzelman and Bas Fagginger Auer.

SIAM Conference on Parallel Processing for Scientific Computing,
Seattle, USA, February 2426, 2010.

Teaching parallelism in an interdisciplinary scientific computing programme
Slides of lecture presented at the SIAM Conference.

Fast Fourier Transform: de wiskunde van MP3 en CTscan
(In Dutch) Masterclass voor 5VWO en 6 VWO leerlingen,
24 en 25 oktober 2008, op de Universiteit Utrecht.

Study Group Mathematics with Industry 2007,
Universiteit Utrecht,
January 29  February 2, 2007

Computing by the Numbers: Algorithms, Precision, and Complexity,
Workshop in honor of the 60th birthday of Richard Brent,
Berlin 2021 July, 2006.
My lecture: Mondriaan
partitioning for faster parallel integer factorisation
by Rob Bisseling and Ildikó Flesch
(42 transparancies, 2MB, PDF format )

IBM Israel Research Seminar,
PageRank Computation Using the Bulk Synchronous Parallel Model,
Haifa, May 8, 2006.

SIAM Conference on Parallel Processing for Scientific Computing,
San Francisco, February 2224, 2006.
My lecture:
A hybrid 2D method for sparse matrix partitioning
by Rob Bisseling,
Tristan van Leeuwen,
and Umit Catalyurek
(29 transparancies, 612kB, PDF format )
Last update of this page: December 20, 2018