Minimally generating ideals of points in polynomial time using linear algebra (Q1576994)

Given \(s\) distinct points in the \(n\)-dimensional projective space, the author presents an algorithm for computing a minimal set of generators of the ideal \(I\) of the given points. The complexity of the algorithm shown is polynomial in the number of points \(s\) and the dimension of the projective space \(n\). First, generators of \(I\) are computed by an interpolating method based on linear functionals. By means of some matrix computations, a Gröbner basis \(S\) for \(I\) is obtained and, afterwards, a particular subset of \(S\) is reduced to a minimal set of generators of the ideal \(I\). This is done essentially by iterated Gaussian eliminations.