Just to clarify properties of the polynomial kernel:
The polynomial kernel is actually only positive-semidefinite. For any kernel matrix generated by the polynomial kernel, the highest rank is degree. Once the number of data points exceeds degree, you end up with a rank-deficient and non-definite matrix. Therefore, your problem is not just numerical.