High performance selected inversion methods for sparse matrices

Staff - Faculty of Informatics

Date: 25 February 2019 / 16:30 - 18:00

USI Lugano Campus, room SI-003, Informatics building (Via G. Buffi 13)

You are cordially invited to attend the PhD Dissertation Defense of Fabio Verbosio on Monday February 25th, 2019 at 16:30 in room SI-003 (Informatics building).

The explicit evaluation of selected entries of the inverse of a given sparse matrix is an important process in various application fields and is gaining visibility in recent years. While a standard inversion process would require the computation of the whole inverse who is, in general, a dense matrix, state-of-the-art solvers perform a selected inversion process instead. Such approach allows to extract specific entries of the inverse, e.g., the diagonal, avoiding the standard inversion steps, reducing therefore time and memory requirements. Despite the complexity reduction already achieved, the natural direction for the development of the selected inversion software is the parallelization and distribution of the computation, exploiting multinode implementations of the algorithms. In this work we introduce parallel, high performance selected inversion algorithms suitable for both the computation and estimation of the diagonal of the inverse of large, sparse matrices. The first approach is built on top of a sparse factorization method and a distributed computation of the Schur-complement, and is specifically designed for the parallel treatment of large, dense matrices including a sparse block. The second is based on the stochastic estimation of the matrix diagonal using a stencil-based, matrix-free Krylov subspace iteration. We implement the two solvers and prove their excellent performance on Cray supercomputers, focusing on both the multinode scalability and the numerical accuracy. Finally, we include the solvers into two distinct frameworks designed for the solution of selected inversion problems in real-life applications. First, we present a parallel, scalable framework for the log-likelihood maximization in genomic prediction problems including marker by environment effects. Then, we apply the matrix-free estimator to the treatment of large-scale three-dimensional nanoelectronic device simulations with open boundary conditions.

Dissertation Committee:
- Prof. Olaf Schenk, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Illia Horenko, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Igor Pivkin, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Matthias Bollhöfer, Technical University Braunschweig, Germany (External Member)
- Prof. Laura Grigori, INRIA & University of Pierre and Marie Curie, France (External Member)