I would like to solve overdetermined, homogeneous linear systems of equations with multivariate polynomial coefficients, i.e., $Ap=0$
with $A$ an $m\times n$ matrix, $m\gg n$, and $a_{i,j} \in \mathbb{Z}[x_1,\ldots,x_k]$ multivariate polynomials with integer coefficients. Typically, $Ap=0$ has an infinite number of solutions; the $a_{i,j}$ are rather sparse polynomials; most of the entries of $A$ are different from zero.
Additionally, there may be further polynomial equations of the form $f_i=0$, $f_i \in Z[x_1,\ldots,x_k]$ to be satisfied together with $Ap=0$.
If possible I would like to obtain an ideal or an intersection of ideals $I \in \mathbb{Z}[x_1,\ldots,x_k,p_1,\ldots,p_n]$ as a representation of the solution.
Are there any efficient algorithms that are tailored to these kinds of problems? I've already tried syzygy computations to solve $Ap=0$ but as typically $m\approx40, n\approx10 $, running times are far from satisfactory. Subsequently, I tried to triangularize the $f_i$ and compute an echelon form of $A$ modulo the obtained regular chains using Bareiss algorithm. Unfortunately, this still required case differentiations for the pivot elements ($a_{i,i}=0, a_{i,i} \neq 0$). Obviously, there should be a way to remove the redundancy contained in the rows of $A$ before actually solving the system.
Can someone give me a hint here, please?