I've had some difficulty using Sage/Singular to compute the decomposition of an ideal in a reasonable time, so I've developed a probabilistic algorithm to do this, and I am wondering if anybody has already done something like this.
For the particular example that I've been working with, I've got a ring over the rational number field with 21 indeterminates and an ideal generated by 30 equations of maximal degree 3. I can post Sage code to generate it if anybody really wants to see it. Using Sage (which calls Singular), I've run my laptop for over twelve hours without primary_decomposition terminating.
My idea for a probabilistic algorithm is roughly this. We pick a random vector $\overline{x} \in {\mathbb R}^{21}$ and use a numerical gradient decent technique to find an approximate solution. If our ideal's basis set is $\{g_i\}$, then the function we try to minimize is $(\sum{g_i(\overline{x})^2}) / |\overline{x}|^2$.
For simplicity, let's use ${\mathbb R}^2$ and assume that $(x^2+y^2-1)$ is one of the prime ideals in our decomposition. Our numerical technique yields an approximate solution $(\overline{x}, \overline{y})$. Now we compute the second degree coordinates $(\overline{x}^2, \overline{y}^2, \overline{x}\overline{y}, \overline{x}, \overline{y}, 1)$, and use the LLL algorithm to find an approximate integer relationship between them, specifically $\overline{x}^2 + \overline{y}^2 + 1 \approx 0$.
Hopefully, this lets us find a set of polynomials which define the irreducible component that our approximate solution lies on. Then we can modify our optimization function to drive our solution away from that component in the hopes of finding other components.
I've tried it out and it definitely finds some components in only a few seconds.
So I'm wondering if anybody else has done something like this, or (if not) if it's worth working up into a paper.
