Rob Bisseling

Name          : Rob Bisseling
Function      : Professor in Scientific Computing
                Program leader of Master 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

New: release of SAWdoubler version 1.0 (August 15, 2012)

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!

The paper accompanying the SAWdoubler software, explaining the algorithm and its implementation, and also presenting timing experiments and discussing memory use is SAWdoubler: a program for counting self-avoiding walks by Raoul D. Schram, Gerard T. Barkema, and Rob H. Bisseling Computer Physics Communications, 184 (2013) pp. 891-898.

Latest release of Mondriaan version 3.11 (December 15, 2010)

• The Extended Matrix-Market (EMM) output format enables the storage of many matrix-like objects in a single file. In the case of Mondriaan, this potentially decreases the number of output files from 5 or more for partitioning a single matrix, to a single file. (By no means is the EMM format tied to Mondriaan: the format can easily and portably be used to share more complex matrix/vector-formulated problems.) Since it remains close to the original Matrix-Market format, existing parsers are envisioned to be adapted with minimal effort.
• The hierarchy of the separator blocks is now included in the output, for all permutation strategies, i.e. Separated Block Diagonal (SBD) and (reverse) Bordered Block Diagonal (BBD). This enables building a full binary tree out of the SBD and BBD structures.
• Mondriaan can now force symmetric permutations, that is, generate PAP^T for general A. In particular, Mondriaan is now able to retain the symmetry of symmetric input matrices.
• The symmetric finegrain splitting strategy. This represents a symmetric sparse matrix A using half the number of vertices and hyperedges, compared to the regular finegrain method. This significantly improves partitioning time for symmetric input matrices, albeit at the cost of some loss in quality, when compared to finegrain.
• The Matlab interface now makes more Mondriaan output available to the users. This enables easy direct application, e.g. to reduce the fill-in in LU-type methods and to accelerate cache-sensitive computations. See also the revised User's guide for Mondriaan's Matlab interface.

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
• office hours

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 7-tesla 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 978-0-19-852939-2. 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 message-passing interface (MPI) discusses how to program in BSP style using the MPI communication library. MPI equivalents of all the programs are also presented.

What's new?

• 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 2011/2012

• Parallel Algorithms (WISM 459)
• Introductie Scientific Computing (WISB356), in Dutch, Teachers: Gerard Sleijpen and Rob Bisseling.
• Discrete Modellen (WISB136), in Dutch. Starts February 6, 2012.
  We will use the book Graph Theory by Adrian Bondy and U.S.R. Murty, Series: Graduate Texts in Mathematics , Vol. 244 3rd Corrected Printing., 2008. We will NOT use lecture notes (dictaat).

Courses in 2010/2011

• Parallel Algorithms (WISM 459)
• Introductie Scientific Computing.
• Infinitesimaalrekening C (WISB234) Start 29 april 2011, 09.00 uur, zaal Aardwetenschappen Groot.

Courses in 2009/2010

• Parallel Algorithms (WISM 459)
• Wiskunde voor eerstejaars scheikunde studenten Periode 1 (SK-BWIS1A)
• Wiskunde voor eerstejaars scheikunde studenten Periodes 2 en 3 (SK-BWIS1B)

Courses in 2008/2009

• Parallel Algorithms (WISM 459)
• Wiskunde voor eerstejaars scheikunde studenten 1 (SK-BWIS1)
• Wiskunde voor eerstejaars scheikunde studenten 2 (SK-BWINA2)

Courses in 2007/2008

• Parallel Algorithms (WISM 459)
• Wiskunde voor eerstejaars scheikunde studenten 1 (SK-BWINA1)
• Wiskunde voor eerstejaars scheikunde studenten 2 (SK-BWINA2)

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

• Computing at Scale Weblog by Bill McColl, founder of the company Parallel Machines.
• BSP Worldwide organisation
• BSP toolset (implementation of BSPlib)
• BSPonMPI (BSPlib version on top of MPI, makes BSPlib portable to almost every parallel computer)
• Industriele en Toegepaste Wiskunde
• 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 )