Homotopy techniques for solving sparse column support determinantal\n polynomial systems

Let $\\mathbf{K}$ be a field of characteristic zero with\n$\\overline{\\mathbf{K}}$ its algebraic closure. Given a sequence of polynomials\n$\\mathbf{g} = (g_1, \\ldots, g_s) \\in \\mathbf{K}[x_1, \\ldots , x_n]^s$ and a\npolynomial matrix $\\mathbf{F} = [f_{i,j}] \\in \\mathbf{K}[x_1, \\ldots, x_n]^{p\n\\times q}$, with $p \\leq q$, we are interested in determining the isolated\npoints of $V_p(\\mathbf{F},\\mathbf{g})$, the algebraic set of points in\n$\\overline{\\mathbf{K}}$ at which all polynomials in $\\mathbf{g}$ and all\n$p$-minors of $\\mathbf{F}$ vanish, under the assumption $n = q - p + s + 1$.\nSuch polynomial systems arise in a variety of applications including for\nexample polynomial optimization and computational geometry. We design a\nrandomized sparse homotopy algorithm for computing the isolated points in\n$V_p(\\mathbf{F},\\mathbf{g})$ which takes advantage of the determinantal\nstructure of the system defining $V_p(\\mathbf{F}, \\mathbf{g})$. Its complexity\nis polynomial in the maximum number of isolated solutions to such systems\nsharing the same sparsity pattern and in some combinatorial quantities attached\nto the structure of such systems. It is the first algorithm which takes\nadvantage both on the determinantal structure and sparsity of input\npolynomials. We also derive complexity bounds for the particular but important\ncase where $\\mathbf{g}$ and the columns of $\\mathbf{F}$ satisfy weighted degree\nconstraints. Such systems arise naturally in the computation of critical points\nof maps restricted to algebraic sets when both are invariant by the action of\nthe symmetric group.\n