Source author record

Thi Xuan Vu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Symbolic Computation math.RA

Catalog footprint

Research overview

5works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Computing critical points for algebraic systems defined by hyperoctahedral invariant polynomials

Let $\mathbb{K}$ be a field of characteristic zero and $\mathbb{K}[x_1, \dots, x_n]$ the corresponding multivariate polynomial ring. Given a sequence of $s$ polynomials $\mathbf{f} = (f_1, \dots, f_s)$ and a polynomial $ϕ$ , all in $\mathbb{K}[x_1, \dots, x_n]$ with $s<n$ , we consider the problem of computing the set $W(ϕ, \mathbf{f})$ of points at which $\mathbf{f}$ vanishes and the Jacobian matrix of $\mathbf{f}, ϕ$ with respect to $x_1, \dots, x_n$ does not have full rank. This problem plays an essential role in many application areas. In this paper we focus on a case where the polynomials are all invariant under the action of the signed symmetric group $B_n$ . We introduce a notion called {\em hyperoctahedral representation} to describe $B_n$ -invariant sets. We study the invariance properties of the input polynomials to split $W(ϕ, \mathbf{f})$ according to the orbits of $B_n$ and then design an algorithm whose output is a {hyperoctahedral representation} of $W(ϕ, \mathbf{f})$ . The runtime of our algorithm is polynomial in the total number of points described by the output.

preprint2022arXiv

On the complexity of invariant polynomials under the action of finite reflection groups

Let $\mathbb{K}[x_1, \dots, x_n]$ be a multivariate polynomial ring over a field $\mathbb{K}$ . Let $(u_1, \dots, u_n)$ be a sequence of $n$ algebraically independent elements in $\mathbb{K}[x_1, \dots, x_n]$ . Given a polynomial $f$ in $\mathbb{K}[u_1, \dots, u_n]$ , a subring of $\mathbb{K}[x_1, \dots, x_n]$ generated by the $u_i$ 's, we are interested infinding the unique polynomial $f_{\rm new}$ in $\mathbb{K}[e_1,\dots, e_n]$ , where $e_1, \dots, e_n$ are new variables, such that $f_{\mathrm{new}}(u_1, \dots, u_n) = f(x_1, \dots, x_n)$ . We provide an algorithm and analyze its arithmetic complexity to compute $f_{\mathrm{new}}$ knowing $f$ and $(u_1, \dots, u_n)$ .

preprint2022arXiv

Rank-Sensitive Computation of the Rank Profile of a Polynomial Matrix

Consider a matrix $\mathbf{F} \in \mathbb{K}[x]^{m \times n}$ of univariate polynomials over a field $\mathbb{K}$ . We study the problem of computing the column rank profile of $\mathbf{F}$ . To this end we first give an algorithm which improves the minimal kernel basis algorithm of Zhou, Labahn, and Storjohann (Proceedings ISSAC 2012). We then provide a second algorithm which computes the column rank profile of $\mathbf{F}$ with a rank-sensitive complexity of $O\tilde{~}(r^{ω-2} n (m+D))$ operations in $\mathbb{K}$ . Here, $D$ is the sum of row degrees of $\mathbf{F}$ , $ω$ is the exponent of matrix multiplication, and $O\tilde{~}(\cdot)$ hides logarithmic factors.

preprint2020arXiv

Computing critical points for invariant algebraic systems

Let $\mathbf{K}$ be a field and $ϕ$ , $\mathbf{f} = (f_1, \ldots, f_s)$ in $\mathbf{K}[x_1, \dots, x_n]$ be multivariate polynomials (with $s < n$ ) invariant under the action of $\mathcal{S}_n$ , the group of permutations of $\{1, \dots, n\}$ . We consider the problem of computing the points at which $\mathbf{f}$ vanish and the Jacobian matrix associated to $\mathbf{f}, ϕ$ is rank deficient provided that this set is finite. We exploit the invariance properties of the input to split the solution space according to the orbits of $\mathcal{S}_n$ . This allows us to design an algorithm which gives a triangular description of the solution space and which runs in time polynomial in $d^s$ , ${{n+d}\choose{d}}$ and $\binom{n}{s+1}$ where $d$ is the maximum degree of the input polynomials. When $d,s$ are fixed, this is polynomial in $n$ while when $s$ is fixed and $d \simeq n$ this yields an exponential speed-up with respect to the usual polynomial system solving algorithms.

preprint2020arXiv

Homotopy techniques for solving sparse column support determinantal polynomial systems

Let $\mathbf{K}$ be a field of characteristic zero with $\overline{\mathbf{K}}$ its algebraic closure. Given a sequence of polynomials $\mathbf{g} = (g_1, \ldots, g_s) \in \mathbf{K}[x_1, \ldots , x_n]^s$ and a polynomial matrix $\mathbf{F} = [f_{i,j}] \in \mathbf{K}[x_1, \ldots, x_n]^{p \times q}$ , with $p \leq q$ , we are interested in determining the isolated points of $V_p(\mathbf{F},\mathbf{g})$ , the algebraic set of points in $\overline{\mathbf{K}}$ at which all polynomials in $\mathbf{g}$ and all $p$ -minors of $\mathbf{F}$ vanish, under the assumption $n = q - p + s + 1$ . Such polynomial systems arise in a variety of applications including for example polynomial optimization and computational geometry. We design a randomized sparse homotopy algorithm for computing the isolated points in $V_p(\mathbf{F},\mathbf{g})$ which takes advantage of the determinantal structure of the system defining $V_p(\mathbf{F}, \mathbf{g})$ . Its complexity is polynomial in the maximum number of isolated solutions to such systems sharing the same sparsity pattern and in some combinatorial quantities attached to the structure of such systems. It is the first algorithm which takes advantage both on the determinantal structure and sparsity of input polynomials. We also derive complexity bounds for the particular but important case where $\mathbf{g}$ and the columns of $\mathbf{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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Thi Xuan Vu

Research overview

Is this your work?

5 publications

Computing critical points for algebraic systems defined by hyperoctahedral invariant polynomials

On the complexity of invariant polynomials under the action of finite reflection groups

Rank-Sensitive Computation of the Rank Profile of a Polynomial Matrix

Computing critical points for invariant algebraic systems

Homotopy techniques for solving sparse column support determinantal polynomial systems

See the researcher in context

Building this map preview