Seminar • Symbolic Computation — Computing Critical Points for Invariant Algebraic SystemsExport this event to calendar

Friday, April 12, 2019 — 1:30 PM EDT

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.

Location 
DC - William G. Davis Computer Research Centre
2568
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2020 (188)
    1. November (1)
    2. October (7)
    3. September (21)
    4. August (28)
    5. July (14)
    6. June (18)
    7. May (16)
    8. April (20)
    9. March (16)
    10. February (25)
    11. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (217)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)