NumPI May 2021

numpi@lists.dm.unipi.it

1 participants
3 discussions

Seminar on 04/06 (Margherita Porcelli)
by Leonardo Robol 04 Jun '21

04 Jun '21

Speaker: Margherita Porcelli Affiliation: Università di Bologna Time: Friday, 04/06/2021, 16:00 Title: Relaxed Interior point methods for low-rank semidefinite programming problems In this talk we will discuss a relaxed variant of interior point methods for semidefinite programming problems (SPDs). We focus on problems in which the primal variable is expected to be low-rank at optimality. Such situations are common in relaxations of combinatorial optimization problems, for example in maximum cut problems as well as in matrix completion problems. We exploit the structure of the sought solution and relax the rigid structure of IPMs for SDP. In anticipation to converging to a low-rank primal solution, a special nearly low-rank form of all primal iterates is imposed. To accommodate such a (restrictive) structure, the first order optimality conditions have to be relaxed and are therefore approximated by solving an auxiliary least-squares problem. The relaxed interior point framework opens numerous possibilities how primal and dual approximated Newton directions can be computed. In particular, it admits the application of both the first- and the second-order methods in this context. In this talk we will focus on second-order approaches and discuss the difficulties arising in the linear algebra phase. A prototype implementation is shown as well as computational results on matrix completion problems. In particular, we will consider mildly-ill conditioned and noisy random problems as well as problems arising in diverse applications as the matrix to be recovered represents city-to- city distances, a grayscale image, game parameters in a basketball tournament. This is joint work with S. Bellavia (Unifi) and J. Gondzio (Univ. Edinburgh) https://www.dm.unipi.it/webnew/it/seminari/relaxed-interior-point-methods-l… Meeting link: https://hausdorff.dm.unipi.it/b/leo-xik-xu4

1 2

Seminar on 14/05 (Alfredo Buttari)
by Leonardo Robol 14 May '21

14 May '21

Speaker: Alfredo Buttari Affiliation: CNRS, IRIT, Toulouse Time: Friday, 14/05/2021, 16:00 Title: Reducing the complexity of linear systems solvers through the block low-rank format Direct linear system solvers are commonly regarded as robust methods for computing the solution of linear systems of equations. Nonetheless, their complexity makes the handling of very large size problems difficult or unfeasible due to excessive execution time or memory consumption. In this talk we discuss the use of low-rank approximation techniques that allow for reducing this complexity at the price of a loss in precision which can be reliably controlled. To take advantage of these low-rank approximations, we have designed a format called block low-rank (BLR) whose objective is to achieve a favorable compromise between complexity and efficiency of operations thanks to its regular structure. We will present the basic BLR format as well as more advanced variants and the associated algorithms; we will analyze their theoretical properties and discuss the issues related to their efficient implementation on parallel computers. We will specifically focus on the use of BLR for the solution of sparse linear systems. The ombination of this format with sparse direct methods, such as the multifrontal one, leads to efficient parallel solvers with scalable complexity. These can either be used as standalone direct solvers or in combination with other techniques such as iterative or multigrid methods. We will present experimental results on real-life problems obtained by integrating the BLR format within the MUMPS parallel sparse direct solver. https://www.dm.unipi.it/webnew/it/seminari/reducing-complexity-linear-syste… Meeting link: https://hausdorff.dm.unipi.it/b/leo-xik-xu4

1 1

Seminar on 07/05 (Stefano Pozza)
by Leonardo Robol 07 May '21

07 May '21

Speaker: Stefano Pozza Affiliation: Charles University, Prague Time: Friday, 07/05/2021, 16:00 Title: The Short-term Rational Lanczos Method and Applications Rational Krylov subspaces have become a reference tool in dimension reduction procedures for several application problems. When data matrices are symmetric, a short-term recurrence can be used to generate an associated orthonormal basis. In the past this procedure was abandoned because it requires twice the number of linear system solves per iteration than with the classical long-term method. We propose an implementation that allows one to obtain key rational subspace matrices without explicitly storing the whole orthonormal basis, with a moderate computational overhead associated with sparse system solves. Several applications are discussed to illustrate the advantages of the proposed procedure. https://www.dm.unipi.it/webnew/it/seminari/short-term-rational-lanczos-meth… Meeting link: https://hausdorff.dm.unipi.it/b/leo-xik-xu4

1 1

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

NumPI May 2021