I have a large set of data points which have 18 dimensions to them. I know that these data points must follow a strict polynomial formula with no possible variance. Given that I have enough data (I assure you I have), how do I go about building a regression model to find the general formula of the lowest polynomials for the equation which gives these data points?
The input dimension being 18 is a little problematic, so I have a few suggestions. I'm putting the statistical approach first due to your choice of tags and terminology..
Linear regression can be made to fit polynomials by simply explicitly creating all the monomial terms; ie for an input with two dimensions $x= (x_1,x_2)$, for a quadratic you'd instead use $x' = (1,x_1,x_2,x_1x_2,x_1^2,x_2^2)$. Notice that this means, to add all $d$th order terms, you would create $O(18^d)$ dimensions! Notice furthermore that your regression model has equivalently many parameters! Therefore, it may be beneficial to try to simplify the model a little with some regularization, maybe use lasso (l1-regularization). Note that, as specified, the degree of the polynomial is not being minimized. The regularization I mentioned only minimizes the l1 length, and even putting a sparsity constraint on the weights alone (which is simpler than minimizing degree) is nonconvex. To find the degree, you could binary search; ie try degrees $1,2,4,8,\ldots$ until you get zero error, and then binary search within the last interval to find the exact order.
Another approach is to directly use polynomial interpolation. Simply grow $d$, building an interpolating polynomial at each iteration, and stopping when the one built on the provided points fits all other points. For univariate data, the Lagrange Polynomial is the way to go. I don't know your case offhand but just noticed wikipedia has a "polynomial interpolation" page which should be helpful.
anything you try will be slow due to the dimension, your stipulation that you necessarily find the absolute smallest degree, and the vast number of parameters in any such polynomial.
If there is no possible variation then this isn't really a regression question. It's straight up linear algebra. You have alot of equations of the form. y= ax_1+b x_2+..+q x_18 + aa x_1^2+ab x_1x_2... (all terms taken 2 at a time),+ (stuff taken 3 at a time)+..
Now either you have an idea of where to end this and need to solve a giant matrix, or you aren't sure where to end this and don't really have enough data. By not enough data I mean that you can fit infintely many polynomials if you allow the degree to be unbounded. Just as you can fit infintely many polynomials to a finite set of points in R^2.