Simon Telen - Polynomial system solving and numerical linear algebra
1 septembre 2017 –
(Joint work with Marc Van Barel)
lk is about the problem of solving zero-dimensional systems of polynomial equations using numerical linear algebra techniques. Let k be an algebraically closed field and let p_1 = p_2 = ... = p_n = 0 define such a system in k^n: p_i \in k[x_1,...,x_n]. It is a well known fact that the variety V(I) of the ideal I = <p_1, ..., p_n> is finite if and only if the quotient ring k[x_1, ..., x_n]/I is finite dimensional as a k-vector space. Multiplication in k[x_1, ..., x_n]/I by a polynomial f is a linear operation. Choosing a basis B for k[x_1, ..., x_n]/I, this multiplication can be represented by a matrix m_f called a multiplication matrix. The eigenstructure of these multiplication matrices reveals the solutions of the system. Methods using Groebner bases to calculate the multiplication matrices make an implicit choice for the basis of the quotient ring. From a numerical point of view, this is often not a very good choice. Significant improvement can be made by using elementary numerical linear algebra techniques on a Macaulay-type matrix, which is built up by the coefficients of the p_i, to choose a basis for k[x_1, ..., x_n]/I. In this talk we will present this technique and show how the resulting method can handle challenging systems.