Structure is a fundamental concept in linear algebra: matrices arising from applications often inherit a special form from the original problem, and this special form can be analysed and exploited to design efficient algorithms. In this short course we will present some examples of matrix structure and related applications. Here we are interested in data-sparse structure, that is, structure that allows us to represent an n × n matrix using only O(n) parameters. One notable example is provided by quasi separable matrices, a class of (generally dense) rank-structured matrices where off-diagonal blocks have low rank.
We will give an overview of the properties of these structured classes and present a few examples of how algorithms that perform basic tasks – e.g., solving linear systems, computing eigenvalues, approximating matrix functions – can be tailored to specific structures.[-]

Structure is a fundamental concept in linear algebra: matrices arising from applications often inherit a special form from the original problem, and this special form can be analysed and exploited to design efficient algorithms. In this short course we will present some examples of matrix structure and related applications. Here we are interested in data-sparse structure, that is, structure that allows us to represent an n × n matrix using only O(n) parameters. One notable example is provided by quasi separable matrices, a class of (generally dense) rank-structured matrices where off-diagonal blocks have low rank.
We will give an overview of the properties of these structured classes and present a few examples of how algorithms that perform basic tasks - e.g., solving linear systems, computing eigenvalues, approximating matrix functions - can be tailored to specific structures.[-]

Polynomial optimization methods often encompass many major scalability issues on the practical side. Fortunately, for many real-world problems, we can look at them in the eyes and exploit the inherent data structure arising from the input cost and constraints. The first part of my lecture will focus on the notion of 'correlative sparsity', occurring when there are few correlations between the variables of the input problem. The second part will present a complementary framework, where we show how to exploit a distinct notion of sparsity, called 'term sparsity', occurring when there are a small number of terms involved in the input problem by comparison with the fully dense case. At last but not least, I will present a very recently developed type of sparsity that we call 'ideal-sparsity', which exploits the presence of equality constraints. Several illustrations will be provided on important applications arising from various fields, including computer arithmetic, robustness of deep networks, quantum entanglement, optimal power-flow, and matrix factorization ranks.[-]

Asymmetric cryptographic constructions used today could be attacked given a powerful enough quantum computer. Even if such a computer does not exist yet, it is important to anticipate its possible construction and to prepare a transition to cryptographic tools having a security resistant against attacks from quantum computers. I will introduce lattice-based cryptography, which is the most promising candidate to build post-quantum cryptographic constructions, and in particular, how we build efficient constructions based on structured lattice problems.[-]

Polynomial optimization methods often encompass many major scalability issues on the practical side. Fortunately, for many real-world problems, we can look at them in the eyes and exploit the inherent data structure arising from the input cost and constraints. The first part of my lecture will focus on the notion of 'correlative sparsity', occurring when there are few correlations between the variables of the input problem. The second part will present a complementary framework, where we show how to exploit a distinct notion of sparsity, called 'term sparsity', occurring when there are a small number of terms involved in the input problem by comparison with the fully dense case. At last but not least, I will present a very recently developed type of sparsity that we call 'ideal-sparsity', which exploits the presence of equality constraints. Several illustrations will be provided on important applications arising from various fields, including computer arithmetic, robustness of deep networks, quantum entanglement, optimal power-flow, and matrix factorization ranks.[-]

Asymmetric cryptographic constructions used today could be attacked given a powerful enough quantum computer. Even if such a computer does not exist yet, it is important to anticipate its possible construction and to prepare a transition to cryptographic tools having a security resistant against attacks from quantum computers. I will introduce lattice-based cryptography, which is the most promising candidate to build post-quantum cryptographic constructions, and in particular, how we build efficient constructions based on structured lattice problems.[-]

In various fields, ranging from aerospace engineering or robotics to computer-assisted mathematical proofs, fast and precise computations are essential. Validated (sometimes called rigorous as well) computing is a relatively recent field, developed in the last 20 years, which uses numerical computations, yet is able to provide rigorous mathematical statements about the obtained result, such as guaranteed and reasonably tight error bounds. This area of research deals with problems that cannot or are difficult and costly in time to be solved by traditional mathematical methods, like problems that have a large search space, problems for which closed forms given by symbolic computations are not available or too difficult to obtain, or problems in nonlinear analysis.
In this course, we provide an introduction to several computing methods and algorithms developed based on the theory of set-valued analysis (in specific function spaces) as well as by combining symbolic and numerical computations. These techniques are illustrated with some applications related to the efficient finite precision evaluation of numerical functions (some of which appear in practical space mission analysis and design).[-]

Proteins are flexible molecules involved in all biological functions. Understanding these functions actually requires delving into protein structure, thermodynamics, and kinetics. This talk will be devoted to two problems in this area. The first one is the (uniform) generation of conformations of a protein backbone in the so-called rigid geometry model. We will present a method based on algebraic solutions of the so-called tripeptide loop closure. The second one deals with the calculation of the volume of high dimensional polytope, a questions closely related to the computation of density of states in statistical physics.[-]