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

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

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 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?

• Mondriaan software. Minor update, version 2.01, released June 9, 2009. Bug-fixes suggested by Alexander Gusak.
• 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.
• Mondriaan software. Major update, version 2.0, released July 14, 2008. Features: new vector partitioning algorithms, improved partitioning quality, inclusion of finegrain and hybrid method, hypergraph partitioning capability, can also handle non-powers of two for the number of processors, full documentation and unit tests, GNU Lesser General Public License.

  Mondriaan is a sequential program written in C that can be used to partition a rectangular sparse matrix, an input vector, and an output vector for parallel sparse matrix-vector multiplication. The program is based on a recursive bipartitioning algorithm that cuts the matrix horizontally and vertically, in a manner resembling some of the famous Mondriaan paintings. The algorithm is multilevel, hypergraph-based, and two-dimensional. It reduces the amount of communication and it spreads both computation and communication evenly over the processors. Paper on original algorithm and software: Brendan Vastenhouw and Rob H. Bisseling, A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication, SIAM Review, Vol. 47, No. 1, pp. 67-95 (2005).
  

• 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.
• A hybrid 2D method for sparse matrix partitioning by Rob Bisseling, Tristan van Leeuwen, and Umit Catalyurek. Lecture at SIAM Conference on Parallel Processing for Scientific Computing San Francisco, February 22-24, 2006. (29 transparancies, 612kB, PDF format)
• 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.
• Partitioning a Call Graph, by Rob H. Bisseling, Jaroslaw Byrka, Selin Cerav-Erbas, Nebojsa Gvozdenovic, Mathias Lorenz, Rudi Pendavingh, Colin Reeves, Matthias Roeger, and Arie Verhoeven. Proceedings Study Group Mathematics with Industry 2005, Amsterdam. Partitions the call graph of a legacy software system in Cobol or Java provided by the Software Improvement Group into modules by two different methods: integer linear programming using CPLEX and hypergraph partitioning using Mondriaan, thus comparing an optimal but slower method with a very fast heuristic. Revised version June 15, 2005.
• 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!
• Lecture Communication balancing in Mondriaan sparse matrix partitioning at SIAM Conference on Parallel Processing for Scientific Computing, San Francisco, CA, February 25-28, 2004. (27 transparancies, 587kB, PDF format, generated using Prosper.)
• BSPedupack and MPIedupack version 1.0 . Official release: January 30, 2004. 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.
• "DNA electrophoresis studied with the cage model" by A. van Heukelum, G. T. Barkema and R. H. Bisseling, Journal of Computational Physics 180, No. 1 (2002) pp. 313-326. Final preprint version. Parallel computation of steady state configuration of DNA strand moving in a gel under the influence of an electric field. Huge state space is brought down by exploiting symmetries. Parallel sparse matrix-vector multiplication is the workhorse subroutine. The special sparsity structure is exploited to reduce communication. Results are obtained using BSPlib on a Cray T3E. Large test matrices are available (some are huge) through the University of Florida Sparse Matrix Collection maintained by Tim Davis.
• Device-size atomistic models of amorphous silicon by R. L. C. Vink, G. T. Barkema, M. A. Stijnman, and R. H. Bisseling, Physical Review B, Vol. 64, 245214 (2001). Description of sequential and parallel algorithms for generating large networks of amorphous silicon. Includes results for 10,000-atom and 20,000-atom networks.

Research

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

Courses in 2009/2010

• Parallel Algorithms (WISM 459) The new course in 2009/2010 has started start on wednesday Sept. 9, 2009 at 10.15 hour in room Minnaert 207. It will be every wednesday 10.15-13.00 hour, with the last lecture on wednesday Dec. 16. You can register for the course through the national website Mastermath (not through Osiris).
• 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) The new course in 2008/2009 has started on friday Sept. 12, 2008 at 11.00 hour in room Ruppert 102. It will be every friday 11.00-13.00 hour, with the last lecture on friday Dec. 19.
• 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.
• Parallel package for multiple sequence alignment of three DNA sequences, using BSPlib. Written by ten third year students computational science under my remote supervision. This package consists of a clever sequential program with extensive capabilities for pruning of the search space, and a scalable brute-force parallel program which gives significant speedups when run on large problems. Released: June 22, 1998.
• 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

• SIAM Conference on Parallel Processing for Scientific Computing, Seattle, USA, February 24-26, 2010.
• 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 )
• BRICKS Scientific Computing Meeting, Shell Global Solutions, Amsterdam, February 16, 2006.
• Paderborn Institute for Scientific Computation Seminar, Paderborn, Germany, December 19, 2005.
• Delft Centre for Computational Science and Engineering Seminar September 23, 2005.
• Parallel Computing 2005, September 13-16, 2005, Malaga, Spain.
• Third International Workshop on High-level Parallel Programming and Applications (HLPP 2005), July 4-5, 2005, Warwick University, Coventry, United Kingdom.
• Second International Workshop on Combinatorial Scientific Computing (CSC05), June 21-23th, 2005 at CERFACS, Toulouse, France.
• Study Group Mathematics with Industry 2005, Vrije Universiteit Amsterdam, January 31 - February 4, 2005
• Computer Science Colloquium, Technion, Haifa, Israel, December 28, 2004.
• Symposium on Software Environments for Numerical Problems, Ghent University, Belgium, November 17 - 18, 2004 My lecture: Improving the quality and speed of the Mondriaan software package for sparse matrix partitioning (39 transparancies, 1800kB, PDF format, generated using Prosper)
• Seminar Dept. Computer Science, Old Dominion University, Norfolk, VA, July 2, 2004.
• Talk on Mondriaan, Talk on BSP, Dept. of Computer and Information Sciences, University of Alabama at Birmingham, US, July 1, 2004.
• Seminar Electrical & Computer Engineering Dept., University of New Mexico, Albuquerque, May 7, 2004.
• SIAM Conference on Parallel Processing for Scientific Computing and SIAM Workshop on Combinatorial Scientific Computing, San Francisco, CA, February 25-28, 2004. My lecture: Communication balancing in Mondriaan sparse matrix partitioning (27 transparancies, 587kB, PDF format, generated using Prosper)
• UvA Numerica Seminar, University of Amsterdam, Sept. 29, 2003.
• HLPP2003: Second international workshop on high-level parallel programming and applications, June 15-17, 2003, Paris/Creteil, France.
• PhD Thesis Defense by Assefaw Gebremedhin, March 25, 2003, Informatik Institut, University of Bergen, Norway.
• Najaarssymposium Wiskundig Genootschap (announcement in pdf format), Katholieke Universiteit Nijmegen", November 22, 2002.
• Seminar Computing Science Department, Warwick University, UK. October 25, 2002.
• Seminar Oxford University Computing Laboratory, Oxford, UK, October 22, 2002.
• Open Source Software for Microscopic Calculations, CECAM Workshop, June 19-21, 2002, Lyon, France. My lecture: Mondriaan, partitioning software for sparse matrix computations (24 transparancies, 719kB, PDF format, generated using Prosper)