Computing a Basis of Polynomials (As a Vector Space)

edit

One way to do this in Sage is to compute an echolonization of the coefficient matrix of the polynomials:

sage: R.<x1,x2,y1,y2> = QQ[]
sage: s = Sequence([x1^2, x2^2, x1^2+x1*x2+x2^2, x1^2-x1*x2, x1*y1+x1^3, y1^2+y1*y2+y2^2])
sage: C, m = s.coefficient_matrix(); C, m
(
                           [ x1^3]
                           [ x1^2]
[ 0  1  0  0  0  0  0  0]  [x1*x2]
[ 0  0  0  1  0  0  0  0]  [ x2^2]
[ 0  1  1  1  0  0  0  0]  [x1*y1]
[ 0  1 -1  0  0  0  0  0]  [ y1^2]
[ 1  0  0  0  1  0  0  0]  [y1*y2]
[ 0  0  0  0  0  1  1  1], [ y2^2]
)
sage: B = C.row_space().basis_matrix(); B
[1 0 0 0 1 0 0 0]
[0 1 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 1 0 0 0 0]
[0 0 0 0 0 1 1 1]
sage: (B * m).list()
[x1^3 + x1*y1, x1^2, x1*x2, x2^2, y1^2 + y1*y2 + y2^2]

This does convert everything to a large vector space however, but it is only as large as necessary to encode all the monomials that occur in the sequence of polynomials.

Note that this assumes you are working over an exact field such as QQ. Over an inexact field such as ℂ, this problem is more delicate. In that case, I would start by looking at the singular value decomposition of C, but the quality of the result largly depends on the input polynomials:

U, D, V = matrix(CDF, C, sparse=False).SVD()