Summary
Title:  Algorithms and Data Structures for Very Large Sparse Matrices 
Author:  Ing. Daniel Langr, Ph.D. 
Supervisor:  prof. Ing. Pavel Tvrdík, CSc. 
Defense:  May 22, 2015 
Organization:  Faculty of Information Technology, Czech Technical University in Prague 
Downloads
Abstract
Sparse matrixvector multiplication (SpMV) is one of the most important numerical core methods in scientific and engineering computing. On today's petascale and future exascale systems, the three principal problems related to SpMV are the minimization of communication between processors in distributedmemory environments, the maximization of the efficiency of local SpMV performed by a single processor, and the implementation of efficient resiliency to system failures by either checkpointingrestart (C/R) or C/Rfree techniques. A general solution of these problems is far beyond the scope of a single scientific work. This thesis deals with several research tasks related to largescale SpMVbased computations, which include the design of a spaceefficient storage format for sparse matrices and development of accompanying algorithms, the experimental evaluation of suitability of this format for storing matrices to parallel file systems, the definition of generic criteria for evaluation of sparse storage formats, the design of parallel scalable generator of benchmark sparse matrices, the development of downsampling and visualization algorithms for large sparse matrices, and the implementation of fast parallel generator of largescale random permutations.
Awards
This work was awarded 2nd place in 2014 Joseph Fourier Prize in Computer Science. [Diploma]
Selected Relevant Publications

D. Langr, P. Tvrdík. Evaluation Criteria for Sparse Matrix Storage Formats. IEEE Transactions on Parallel and Distributed Systems, 27(2):428–440, 2016. [DOI]

D. Langr, P. Tvrdík, I. Šimeček, T. Dytrych. Downsampling Algorithms for Large Sparse Matrices. International Journal of Parallel Programming, 43(5):679–702, 2015. [DOI]

D. Langr, P. Tvrdík, T. Dytrych, J.P. Draayer. Algorithm 947: Paraperm: Parallel Generation of Random Permutations with MPI. ACM Transactions on Mathematical Software, 41(3):5:1–5:24, 2014. [DOI]

D. Langr, I. Šimeček, P. Tvrdík, T. Dytrych. LargeScale Visualization of Sparse Matrices. Scalable Computing: Practice and Experience, 15(1):21–31, 2014. [DOI]

D. Langr, I. Šimeček, P. Tvrdík, T. Dytrych. Scalable Parallel Generation of Very Large Sparse Benchmark Matrices. In Proceedings of the 10th International Conference on Parallel Processing and Applied Mathematics (PPAM 2013). Lecture Notes in Computer Science, 8384:178–187, 2014. [DOI]
 D. Langr, I. Šimeček, P. Tvrdík, T. Dytrych, J.P. Draayer. AdaptiveBlocking Hierarchical Storage Format for Sparse Matrices. In Proceedings of the Federated Conference on Computer Science and Information Systems (FedCSIS 2012), 545–551, 2012. [HTTP]
Images
Contributions of the thesis (red) in the context of today's and future problems related to largescale sparse matrixvector multiplication (blue):
Visualization of the density of nonzero elements of a large sparse matrix:
Contact
Daniel Langr
email: daniel.langr(at)fit.cvut.cz
Department of Computer Systems
Faculty of Information Technology
Czech Technical University in Prague