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 30-2531481
Fax           : +31 30-2518394

The fastest Fourier transform in Utrecht

And probably elsewhere as well. Our paper on the multidimensional parallel Fast Fourier transform and its implementation FFTU has appeared on December 8, 2023: Thomas Koopman and Rob H. Bisseling, Minimizing communication in the multidimensional FFT, SIAM Journal on Scientific Computing 45, No. 6 (2023) pp. C330-C347. Postprint version.

The paper is accompanied by two videos, Parallel 3D Fast Fourier Transform which explains the basic idea, and Proof of Parallel 3D Fast Fourier Transform, which presents the underlying proof (for the diehards). The software is available at FFTU.

Parallel Scientific Computation: A Structured Approach using BSP (Second edition)

• My personal book page with supplementary matrial (slides, software)
• Book page at Oxford University Press
• Book page at Amazon US
• Book page at Bol.com NL

Invited lecture at SIAM Conference on Parallel Processing for Scientific Computation / SIAM Workshop on Combinatorial Scientific Computation, Seattle, USA, February 12, 2020

Bug fix release of Mondriaan 4.2.1 (August 8, 2019)

Download the latest version of the Mondriaan software, version 4.2.1 (tar gzipped).

Bulk: a Modern C++ Interface for Bulk-Synchronous Parallel Programs (August 20, 2018)

Release of Mondriaan 4.2 (September 17, 2017)

Version 4.2 contains several improvements compared to version 4.1. These are:

• A zero-volume 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.

New: release of SAWdoubler version 2.0 (March 28, 2017)

The aim of the package is to enable counting self-avoiding 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 length-doubling method computes Z_(N+M) for every pair of integers N, M >= 1.
• The squared end-to-end distance P_N is also computed, defined as the sum of the squared Euclidean distances of the endpoints of all the self-avoiding walks.
• New lattices have been added to the simple cubic (SC) lattice: Body-Centred Cubic (BCC), Face-Centred 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 self-avoiding walks on BCC and FCC lattices by Raoul D. Schram, Gerard T. Barkema, Rob H. Bisseling, and Nathan Clisby", arXiv:1703.09340 [cond-mat.stat-mech] 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

New: Hot Topic in ACM Computing Reviews (June 2016)

Oratie (Inaugural lecture)

• Abstract
• Volledige tekst (PDF, 8 Mbyte). Een gedrukt oratieboekje is beschikbaar en wordt op verzoek toegezonden aan belangstellenden, uiteraard zolang de voorraad strekt. (Het verzoek kan per email aan mij, zie bovenstaand adres.)
• Oratiefilmpje gemaakt met MondriaanMovie van Bas Fagginger Auer
• Bewerkte versie verschenen in het Nieuw Archief voor Wiskunde, Vol. 5/11, Nr. 2, pp. 100-107.

Information

• biography
• list of all my publications
• available software
• Theses under my supervision, temporarily removed, to comply with European privacy laws. Will be back in different format. Try to search the keyword "Bisseling" on Igitur, the thesis repository of Utrecht University

What's new?

• Reports by science writer Anouck Vrouwe of the Study Week Mathematics with Industry 2015 organised in Utrecht, January 26-30, 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 billion-vertex 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 A-Eskwadraat, July 2014.
• Nieuw wiskundig record zelfmijdende wandelingen Press release (in Dutch) July 6, 2011.
• Exact enumeration of self-avoiding 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 self-avoiding walks based on the inclusion-exclusion principle from combinatorics. This length-doubling 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 object-oriented version of BSPlib in Java aimed at multicore architectures, developed by Albert-Jan Yzelman and Rob Bisseling. Paper: An Object-oriented BSP Library for Multicore Programming by Albert-Jan 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 many-core parallel architectures. Such partitionings are then used to bring sparse matrices in a recursive Bordered Block Diagonal form (for processor-oblivious parallel LU decomposition) or recursive Separated Block Diagonal form (for cache-oblivious 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 cache-oblivious sparse matrix--vector multiplication scheme based on the Hilbe rt curve by Albert-Jan 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 cache-oblivious SpMV and proposes the Bi-directional 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.
• Two-dimensional cache-oblivious sparse matrix-vector multiplication by Albert-Jan N. Yzelman and Rob H. Bisseling, Parallel Computing, 2011. doi:10.1016/j.parco.2011.08.004 Extends our previous 1D cache-oblivious 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 High-level Parallel Programming and Applications (HLPP 2010), pp. 45-54, September, 2010.
• Sparse matrix partitioning, ordering, and visualisation by Mondriaan 3.0 by Rob Bisseling, Albert-Jan Yzelman, Bas Fagginger Auer. Slides of lecture presented at the Workshop Scheduling in Aussois, France, June 4, 2010.
• Combinatorial problems in High-Performance 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 Cache-oblivious sparse matrix-vector multiplication by using sparse matrix partitioning methods by Albert-Jan N. Yzelman and Rob H. Bisseling, SIAM Journal on Scientific Computing, 31, No. 4 (2009) pp. 3128-3154. Original version of August 20, 2008. Describes a cache-oblivious method for sparse matrix-vector multiplication, which attempts to permute the rows and columns of the input matrix using a hypergraph-based sparse matrix partitioning scheme so that the resulting matrix induces cache-friendly behaviour during sparse matrix-vector 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. 95-115. 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. 708-717. Final preprint version. Picture right: authors at Dagstuhl Castle, Germany, participating in the workshop on Combinatorial Scientific Computing, February 2009.
• Computational e-Science: 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 e-Science', which is to advance innovative, interdisciplinary research where complex multi-scale, multi-domain 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. 551-567. 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 22-24, 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 matrix-vector multiplication by Rob H. Bisseling and Wouter Meesen, Electronic Transactions on Numerical Analysis 21 (2005) pp. 47-65 (special issue on Combinatorial Scientific Computing). Describes improved algorithms for vector partitioning in sparse matrix-vector 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; one-dimensional 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 matrix-vector 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 MPI-1 and the one-sided communications from MPI-2.

• Opgave en Oplossing parallel rekenen Kaleidoscoop (10 maart 2003) en Voorlichtingsdag 20 maart 2004 (in Dutch).
• "Partitioning 3D space for parallel many-particle simulations" by M. A. Stijnman, R. H. Bisseling, and G. T. Barkema, Computer Physics Communications 149, No. 3 (2003) pp. 121-134. Final preprint version. Partitioning 3D space based on the BCC, FCC, and HCP sphere packings reduces communication by up to 16 percent, compared to simple-cubic 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 many-particle simulations.

Research

• parallel algorithms
• sparse matrix computations
• bioinformatics
• computational science

Courses in 2020/2021

• Parallel Algorithms (WISM 459). Fall semester 2020. Teacher: Rob Bisseling. Teaching assistant: Katharina Klein
• Introduction Scientific Computing (WISB356) February-April 2021. Teachers: Rob Bisseling and Alessandro Sbrizzi. Teaching assistant: Lotte Muller
• Programmeren voor Wiskunde (WISB152) April - June 2021.

Some of my work

• The final version of the BSPlib report has appeared in Parallel Computing 24 (1998) pp. 1947-1980. 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

• BSP Worldwide organisation
• BSP toolset (implementation of BSPlib)
• BSPonMPI (BSPlib version on top of MPI, makes BSPlib portable to almost every parallel computer)
• Werkgemeenschap Scientific Computing

Meet me at

• Deltares, Delft, lunch seminar, November 8, 2010. Partitioning for applications: using Mondriaan in mesh-based computations, by Rob Bisseling, Albert-Jan Yzelman and Bas Fagginger Auer.
• CERFACS, Toulouse, visit May-July 2010. Partitioning for applications, CERFACS Seminar, July 13, 2010 by Rob Bisseling, Albert-Jan Yzelman and Bas Fagginger Auer.
• SIAM Conference on Parallel Processing for Scientific Computing, Seattle, USA, February 24-26, 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 CT-scan (In Dutch) Masterclass voor 5-VWO 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 20-21 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 22-24, 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 )