Question: System of linear equations with roots of unity

I have a problem that seems rather simple in theory, yet if implemented in maple there arise problems. I want to solve systems of linear equations that involve roots of unity.

This problem arises when trying to find explicit equations of multivariate polynomials of fixed degree through given points (together with conditions on the derivatives of the curve at these points). In the following case, the points are dented by P[i] and I'm looking for the explicit equation of the degree 9 polynomial through these points. Actually, I know there is a two parameter family of such polynomials, so the solution will be of dimension two.

Sorry for the rather crude implementation.

with(Groebner): with(algcurves): with(LinearAlgebra):

t := exp((1/9)*(2*Pi*I)):
s := exp((1/3)*(2*Pi*I)):
a_1 := -1*t:
a_2 := -s*t:
a_3 := -s^2*t:
P[1] := a_1, 0, 1: P[2] := a_2, 0, 1: P[3] := a_3, 0, 1:
P[4] := 1, t*a_1, 0: P[5] := 1, t*a_2, 0: P[6] := 1, t*a_3, 0:
P[7] := 0, 1, a_1: P[8] := 0, 1, a_2: P[9] := 0, 1, a_3:

G := 0: var1 := 0:
for n from 0 to 9 do
G := G+add(c[k, n-k]*x^k*y^(n-k), k = 0 .. n):
for k from 0 to n do var1 := var1, c[k, n-k]:
end do: 
end do:
F := Homogenize(G, z):
Fx := diff(F, x):
Fy := diff(F, y):
Fz := diff(F, z):
Fxx := diff(F, x, x):
Fxy := diff(F, x, y):
Fyx := Fxy:
Fyy := diff(F, y, y):
Fxz := diff(F, x, z):
Fzx := Fxz:
Fzz := diff(F, z, z):
Fyz := diff(F, y, z):
Fzy := diff(F, z, y):

f := unapply(F, [x, y, z]): fx := unapply(Fx, [x, y, z]): fy := unapply(Fy, [x, y, z]): fz := unapply(Fz, [x, y, z]): fxx := unapply(Fxx, [x, y, z]): fxy := unapply(Fxy, [x, y, z]): fyx := unapply(Fyx, [x, y, z]): fyy := unapply(Fyy, [x, y, z]): fxz := unapply(Fxz, [x, y, z]): fzx := unapply(Fzx, [x, y, z]): fzz := unapply(Fzz, [x, y, z]): fyz := unapply(Fyz, [x, y, z]): fzy := unapply(Fzy, [x, y, z]):

sys := [f(P[1]) = 0, fx(P[1]) = 0, fy(P[1]) = 0, fz(P[1]) = 0, fxy(P[1]) = 0, fxz(P[1]) = 0, fxx(P[1]) = 0, fyy(P[1]) = 0, fzz(P[1]) = 0, fyz(P[1]) = 0, f(P[2]) = 0, fx(P[2]) = 0, fy(P[2]) = 0, fz(P[2]) = 0, fxy(P[2]) = 0, fxz(P[2]) = 0, fxx(P[2]) = 0, fyy(P[2]) = 0, fzz(P[2]) = 0, fyz(P[2]) = 0, f(P[3]) = 0, fx(P[3]) = 0, fy(P[3]) = 0, fz(P[3]) = 0, fxy(P[3]) = 0, fxz(P[3]) = 0, fxx(P[3]) = 0, fyy(P[3]) = 0, fzz(P[3]) = 0, fyz(P[3]) = 0, f(P[4]) = 0, fx(P[4]) = 0, fy(P[4]) = 0, fz(P[4]) = 0, fxy(P[4]) = 0, fxz(P[4]) = 0, fxx(P[4]) = 0, fyy(P[4]) = 0, fzz(P[4]) = 0, fyz(P[4]) = 0, f(P[5]) = 0, fx(P[5]) = 0, fy(P[5]) = 0, fz(P[5]) = 0, fxy(P[5]) = 0, fxz(P[5]) = 0, fxx(P[5]) = 0, fyy(P[5]) = 0, fzz(P[5]) = 0, fyz(P[5]) = 0, f(P[6]) = 0, fx(P[6]) = 0, fy(P[6]) = 0, fz(P[6]) = 0, fxy(P[6]) = 0, fxz(P[6]) = 0, fxx(P[6]) = 0, fyy(P[6]) = 0, fzz(P[6]) = 0, fyz(P[6]) = 0, f(P[7]) = 0, fx(P[7]) = 0, fy(P[7]) = 0, fz(P[7]) = 0, fxy(P[7]) = 0, fxz(P[7]) = 0, fxx(P[7]) = 0, fyy(P[7]) = 0, fzz(P[7]) = 0, fyz(P[7]) = 0, f(P[8]) = 0, fx(P[8]) = 0, fy(P[8]) = 0, fz(P[8]) = 0, fxy(P[8]) = 0, fxz(P[8]) = 0, fxx(P[8]) = 0, fyy(P[8]) = 0, fzz(P[8]) = 0, fyz(P[8]) = 0, f(P[9]) = 0, fx(P[9]) = 0, fy(P[9]) = 0, fz(P[9]) = 0, fxy(P[9]) = 0, fxz(P[9]) = 0, fxx(P[9]) = 0, fyy(P[9]) = 0, fzz(P[9]) = 0, fyz(P[9]) = 0]:
var := [c[0, 0], c[0, 1], c[1, 0], c[0, 2], c[1, 1], c[2, 0], c[0, 3], c[1, 2], c[2, 1], c[3, 0], c[0, 4], c[1, 3], c[2, 2], c[3, 1], c[4, 0], c[0, 5], c[1, 4], c[2, 3], c[3, 2], c[4, 1], c[5, 0], c[0, 6], c[1, 5], c[2, 4], c[3, 3], c[4, 2], c[5, 1], c[6, 0], c[0, 7], c[1, 6], c[2, 5], c[3, 4], c[4, 3], c[5, 2], c[6, 1], c[7, 0], c[0, 8], c[1, 7], c[2, 6], c[3, 5], c[4, 4], c[5, 3], c[6, 2], c[7, 1], c[8, 0], c[0, 9], c[1, 8], c[2, 7], c[3, 6], c[4, 5], c[5, 4], c[6, 3], c[7, 2], c[8, 1], c[9, 0]]:
A, b := GenerateMatrix(sys, var):

Solving this with

simplify(LinearSolve(A, b))

Gives a rather nicely looking solution. But the calculation strongly depends on the form of s, t and the a_i.

For example if we instead define 

s:=t^3:

The computation takes much longer and the result doesn't take a particularly nice form. Similarly if we instead take

a_1 := -t: a_2 := -t^4: a_3 := -t^7:

the computation takes hours / days and the result looks rather ugly (huge coefficients). Yet both of these inputs are mathematically equivalent to the original one.

The thing is that I have similar systems of linear equations that I know must have solutions, but the solution vector that maple puts out has coefficients with thousands of digits (which after the above I suspect to be wrong). I know the systems are vastly overdetermined, but even removing all redundant equations does not solve the problen.

Is there a way to get the correct solutions with maple? Does anyone know whether a different program would handle this problem better?