Please note: This PhD seminar will be given online.
Thi
Xuan
Vu, PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
Supervisors: Professors Éric Schost and George Labahn
Let $K[x_1, \dots, x_n]$ be a polynomial ring in n variables with $K$ a field of characteristic zero and $KK$ its algebraic closure. Consider a sequence of polynomials $G = (g_1, \dots, g_s)$ in $K[x_1, \dots, x_n]$ and a matrix $F = [f_{i, j}] \in K[x_1, \dots, x_n]^{p \times q}$ such that $p \leq q$ and $n=q-p+s+1$. We are interested in the algebraic set $V_p(F, G)$ of points in $KK$ at which all polynomials in $G$ and all $p$-minors of $F$ vanish. Such polynomial systems arise in a variety of applications including for example polynomial optimization and computational geometry.
We investigate the column structures of $F$ to provide bounds on the number of isolated points in $V_p(F, G)$ depending on the degrees in columns of $\F$ or the mixed volumes of column supports of $F$ when all polynomials $g_i$'s and $f_{i, j}$'s are either in classical polynomial domains or sparse polynomials. In addition, we design homotopy algorithms for computing those points with our algorithms running in time that is polynomial in the bound on the number of isolated points. We also derive complexity bounds for the particular but important case where $G$ and the columns of $F$ satisfy weighted degree constraints. Such systems arise naturally in the computation of critical points of maps restricted to algebraic sets when both are invariant by the action of the symmetric group.
To join this PhD seminar on Zoom, please go to https://us02web.zoom.us/j/87317792190?pwd=NWxEMWErczg5ZEhvUjVTQ1ZKREhxQT09.