Invited Talk
Parallel Tomographic Reconstruction – Where Combinatorics Meets Geometry
Rob Bisseling, Utrecht University, The Netherlands
Slides (46 MB in PDF format, contains a movie in mp4 format)
Video recording at https://www.youtube.com/watch?v=nqQKPldd_FU
Today, high-resolution tomographic reconstruction of 3D objects is within reach, but the associated data sets are huge and calling for parallel computation. A typical 3D reconstruction with 4k resolution already produces an image of 64 Gbytes. Tomographic reconstruction is often done using iterative algorithms that involve repeated sparse matrix-vector multiplication (SpMV). The matrix, however, may be too large to store, requiring Tbytes of memory, and hence each matrix row is recomputed upon use. In this talk, we present data partitioning methods for tomography matrices of increasing size. For small matrices, we can compute an optimal bipartitioning by an exact combinatorial method, as implemented in the packages MondriaanOpt and MP. This allows us to gauge the quality of medium-grain partitioning (default in the Mondriaan package), which is a heuristic combinatorial method that can handle larger problems. Medium-grain results in turn justified choosing row partitioning for the tomographic matrix-free SpMV. For this row partitioning, we developed a geometric recursive coordinate bisection algorithm with nearly the same output quality as combinatorial partitioning that can handle huge, matrix-free problems and is also faster. We conclude with showing an actual reconstruction that was written using Bulk, a modern C++ library for easy development of parallel programs in bulk-synchronous parallel style.