3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

I think it's fair to say that people have done something like this, though I'm not aware of anyone using the exact sequence of steps you've described.

There is an active community of people (full disclosure--including me) using numerical methods to study algebraic varieties. These are most effective for questions over the complex numbers, though in some cases interesting questions over the reals can be answered as well. The catch-all term for this body of work is "numerical algebraic geometry" (N.A.G.) -- you can find a basic description in [1], among several other sources.

The main numerical method used is homotopy continuation (an incarnation of predictor/corrector methods.) Local methods like gradient descent sometimes make an appearance as well --- the application I'm most aware of is to real enumerative geometry (cf. [2].)

There are numerical algorithms for computing what is known as a numerical irreducible decomposition of a complex algebraic variety (described in [1]) -- essentially, every irreducible component is represented by its intersection with a general linear space of complementary codimension. As the term "general linear space" suggests, these are inherently randomized algorithms. An upside is that you obtain an effective representation of all irreducible components. A potential downside for someone interested in real questions would be a case where there are several components with no real points.

Another major difference from what you propose is that many N.A.G. methods don't produce intermediate symbolic (exact or inexact) results such as the equations you find from LLL. One could try to get this info from the output of a numerical irreducible decomposition routine --- this is essentially the exactness recovery framework described in [3].

It is a much more subtle matter to expose embedded components and determine multiplicities. [4] This may be relevant since you don't define "decomposition."

N.A.G. algorithms are implemented in several software packages: Bertini, HOM4PS, HomotopyContinuation.jl, NAG4M2, and PHCPack are all actively maintained as of the time of writing. It's difficult to say whether or not your problem is amenable to computation --- the complexity of some procedures is influenced by factors other than the number of variables and total degrees. As someone who works on this sort of thing, you can feel free to send me your equations. (:

[1] Hauenstein, J and Sommese, A. "What is Numerical Algebraic Geometry." https://www3.nd.edu/~jhauenst/preprints/hsWhatIsNAG.pdf

[2] Griffin ,Z and Hauenstein, J. "Real solutions to systems of polynomial equations and parameter continuation" https://www3.nd.edu/~jhauenst/preprints/ghRealSolving.pdf

[3] Bates, D, Hauenstein, J, McCoy, T, Peterson, C, and Sommese, A. "Recovering exact results from inexact data in numerical algebraic geometry." https://pdfs.semanticscholar.org/a913/2adb8c63ab8cde55d2d527ad435475353f8c.pdf

[4] Leykin, A "Numerical primary decomposition" https://arxiv.org/pdf/0801.3105.pdf

New contributor
tim is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • $\begingroup$ Thanks for the great references! I've only skimmed them, but [3] looks very similar to what I came up with. I was not aware of N.A.G. in general, so your answer is very informative and is just what I was looking for. $\endgroup$ – Brent Baccala Aug 12 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.