Matias Bender (LIP6 - Sorbonne Universités, Inria, CNRS)
Determinantal formulas for the resultant of some mixed multilinear systems
A fundamental problem in computational algebraic geometry is the computation of the resultant. A central question is when and how to compute it as the determinant of a matrix whose elements are the coefficients of the input polynomials up-to sign. This problem is well understood for unmixed multihomogeneous systems, that is for systems consisting of multihomogeneous polynomials with the same support. However, little is known for mixed systems, that is for systems consisting of polynomials with different supports. We consider the computation of the multihomogeneous resultant of special classes of mixed multilinear systems. We present a constructive approach that expresses the resultant as the exact determinant of a Koszul resultant matrix, that is a matrix constructed from maps in the Koszul complex. We exploit the resultant matrix to propose an algorithm to solve such systems. In the process we extend the classical eigenvalues and eigenvectors criterion to a more general setting. Our extension of the eigenvalues criterion applies to a general class of matrices, including the Sylvester-type and the Koszul-type ones.
Claude-Pierre Jeannerod (Inria, ENS Lyon)
Multiplication and inversion algorithms for matrices with displacement structure.
The notion of displacement rank provides a uniform way to deal with various classical matrix structures (such as Toeplitz, Hankel, Vandermonde, Cauchy) and allows for various generalizations. In this talk, we will review some recent progress in the design of asymptotically fast algorithms for multiplying and inverting such matrices. In particular, for n by n matrices of displacement rank α, we will see that the arithmetic cost of such operations can be reduced from about α2n (up to log factors) down to αω-1n, where ω < 2.373 is the exponent of (dense, unstructured) matrix multiplication.
Ana C. Matos (Laboratoire Paul Painlevé, Université des Sciences et Technologies de Lille)
Working with rational functions in a numeric environment - some contributions
Rational functions like for instance Padé approximants play an important role in signal processing, sparse interpolation and exponential analysis. They have good theoretical properties in approximation and modeling. However, for a successful modeling with help of rational functions we want to make sure that there is no ”similar” rational function being degenerate, i.e., having strictly smaller degree of both degrees of numerator and denominator. In particular, we prefer having rational functions without Froissart doublets (i.e., roots close to a pole) because their presence induce numerical instabilities: small variations in the argument of the function give rise to large variations in the function values.
In a numerical setting, we will bring out some quantities to control conditioning and stability of the computed rational functions. These quantities are based on the condition number of some matrices, numerical co-primeness of polynomials and spherical derivatives. They are reliable indicators of the good numerical properties of the functions and we can use them to choose the good class of functions or to construct new approximations.
Jean-Claude Yakoubsohn (IMT, Université Paul Sabatier, Toulouse)
Vers des méthodes d'ordre élevé pour l'approximation de la SVD
Tout est dans le titre. Je parlerai d'un travail récent qui propose une classe de méthodes pour approcher la décomposition en valeurs singulière d'une matrice dans le cas général.
Fatmanur Yildirim (INRIA Sophia Antipolis)
Orthogonal projection onto rational surfaces.
I will present a new algebraic approach for computing the orthogonal projection of a point onto a rational algebraic surface embedded in the three dimensional projective space, which is a joint work with Nicolás Botbol, Laurent Busé and Marc Chardin. Our approach amounts to turn this problem into the computation of the finite fibers of a generically finite trivariate rational map whose source space is either bi-graded or tri-graded and which has one dimensional base locus: the congruence of normal lines to the rational surface. This latter problem is solved by using certain syzygies associated to this rational map for building matrices that depend linearly in the variables of the three dimensional ambient space. In fact, these matrices have the property that their cokernels at a given point p in three dimensional space are related to the pre-images of the p via the rational map. Thus, they are also related to the orthogonal projections of p onto the rational surface. Then, the orthogonal projections of a point are approximately computed by means of eigenvalues and eigenvectors numerical computations.