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.[-]

Algebraic combinatorics studies combinatorial objects with an algebraic point of view, and conversely. As such, it is also a very fertile ground for experimental mathematics, involving both classical and new algorithms. I will discuss two topics: finite partially ordered sets and their invariants, and tree-indexed polynomials and power series. Finite partially ordered sets are discrete objects, that can be seen as directed graphs, but also possess an interesting representation theory. This leads to many difficult questions about a subtle equivalence relation, namely posets having equivalent derived categories. The theme of tree-indexed series, which can be traced back to Cayley, plays a role in the study of vector fields and ordinary differential equations. It is nowadays better understood in the framework of operads and can be considered as a nonassociative version of the study of alphabets, words and languages. Surprisingly maybe, rooted trees also appear in the study of iterated integrals, stemming out of the usual "integration-by-part" rule. I will describe the corresponding notions of algebras, without diving too much into the theory of operads. On the way, I will discuss some of the involved algorithms and their implementations.[-]

I will start from reviewing Gröbner bases and their connection to polynomial system solving. The problem of solving a polynomial system of equations over a finite field has relevant applications to cryptography and coding theory. For many of these applications, being able to estimate the complexity of computing a Gröbner basis is crucial. With these applications in mind, I will review linear-algebra based algorithms, which are currently the most efficient algorithms available to compute Gröbner bases. I will define and compare several invariants, that were introduced with the goal of providing an estimate on the complexity of computing a Gröbner basis, including the solving degree, the degree of regularity, and the last fall degree. Concrete examples will complement the theoretical discussion.[-]

Robotic design involves modeling the behavior of a robot mechanism when it moves along potential paths set by the users. In this lecture, we will first give an overview of different approaches to design a set of kinematic equations associated with a robot mechanism. In particular, these equations can be used to solve the forward and the backward kinematics problems associated with a robot mechanism or to model its singularity locus. Then we will review methods to solve those equations, and notably methods to draw with guarantees the real solutions of an under-constrained system of equations modeling the singularities of a robot.[-]

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.[-]

Algebraic combinatorics studies combinatorial objects with an algebraic point of view, and conversely. As such, it is also a very fertile ground for experimental mathematics, involving both classical and new algorithms. I will discuss two topics: finite partially ordered sets and their invariants, and tree-indexed polynomials and power series. Finite partially ordered sets are discrete objects, that can be seen as directed graphs, but also possess an interesting representation theory. This leads to many difficult questions about a subtle equivalence relation, namely posets having equivalent derived categories. The theme of tree-indexed series, which can be traced back to Cayley, plays a role in the study of vector fields and ordinary differential equations. It is nowadays better understood in the framework of operads and can be considered as a nonassociative version of the study of alphabets, words and languages. Surprisingly maybe, rooted trees also appear in the study of iterated integrals, stemming out of the usual "integration-by-part" rule. I will describe the corresponding notions of algebras, without diving too much into the theory of operads. On the way, I will discuss some of the involved algorithms and their implementations.[-]

Robotic design involves modeling the behavior of a robot mechanism when it moves along potential paths set by the users. In this lecture, we will first give an overview of different approaches to design a set of kinematic equations associated with a robot mechanism. In particular, these equations can be used to solve the forward and the backward kinematics problems associated with a robot mechanism or to model its singularity locus. Then we will review methods to solve those equations, and notably methods to draw with guarantees the real solutions of an under-constrained system of equations modeling the singularities of a robot.[-]

I will start from reviewing Gröbner bases and their connection to polynomial system solving. The problem of solving a polynomial system of equations over a finite field has relevant applications to cryptography and coding theory. For many of these applications, being able to estimate the complexity of computing a Gröbner basis is crucial. With these applications in mind, I will review linear-algebra based algorithms, which are currently the most efficient algorithms available to compute Gröbner bases. I will define and compare several invariants, that were introduced with the goal of providing an estimate on the complexity of computing a Gröbner basis, including the solving degree, the degree of regularity, and the last fall degree. Concrete examples will complement the theoretical discussion.[-]