Thi
Xuan
Vu,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
and
University
of
Sorbonne
Computing critical points of a polynomial map φ ∈ Q[x1,...,xn] restricted to an algebraic set V ⊂ Cn defined by f1,...,fs ∈ Q[x1,...,xn] is important in many applications in optimization, real algebraic geometry, e.g., deciding the emptiness of an algebraic set over a real field.
Let Sn denote the group of permutations of {1, . . . , n}. A polynomial g ∈ Q[x1, . . . , xn] is Sn-invariant if σ(g) = g for any σ ∈ Sn. A family F of polynomials in Q[x1, . . . , xn] is said to be Sn-invariant if σ(f) = f for all σ ∈ Sn and f ∈ F. It is a longstanding challenge to obtain algorithms that, given a polynomial map φ and set F of polynomials which are all Sn-invariant, exploit the advantage of the symmetric structure to compute the critical points of φ restricted to V (F ).
To do it, we split our system into subsystems according to Sn group orbits. Then, we provide the bounds c of the sum of the degrees of the algebraic ideals vanishing on the critical points in all Sn group orbits as c = deg(f1 )··· deg(fs)(n+d-1 choose n) where d = max1≤i≤s(deg(fi)). Next, we design an algorithm for computing the critical points of φ restricted to V (F ) whose run-time is a polynomial of degree 6 in c. This reduces significantly the best-known complexity bound for this problem which requires d^O(n)operations in Q.
Bio: Thi Xuan Vu is a PhD student doing her studies under a cotutelle agreement between Computer Science at Waterloo and the University of Sorbonne in Paris. Her supervisors are Eric Schost and George Labahn here and Mohab El Din Safey in Paris.