JuliaHomotopyContinuation / HomotopyContinuation.jl

A Julia package for solving systems of polynomials via homotopy continuation.
https://www.JuliaHomotopyContinuation.org
MIT License
175 stars 30 forks source link

Strange behaviour of numerical irreducible decomposition #545

Closed simon-pepin closed 7 months ago

simon-pepin commented 1 year ago

Hi,

I am trying to use your nice library to compute the irreducible components of certain jet schemes of surface singularities. However I often get empty witness sets. A simple example of this behaviour is

using HomotopyContinuation @var a1 a2 a3

J = System([ a1^2 - a2 , a3]) N = nid(J)

J2 = System([ a1^2-a2 , a3^2]) N2 = nid(J2)

The first example works fine and finds two 1-dimensional components, but the second returns an empty decomposition.

I don't know if this is related, but I also get a very unstable number of irreducible components in more "realistic" examples, for instance

nid(System([a1b1 , a2b1 + a1b2 , -c1^4 + a3b1 + a2b2 + a1b3 ]))

which corresponds to the space of 4-jets starting from the A_3 surface singularity xy=z^4. The correct answer is 3 irreducible components, but I get a number varying between 0 and 10.

PBrdng commented 1 year ago

Hi, first of all: thank you for trying out our software. Let me reply to your issues.

In general, polynomial homotopy continuation can only find regular zeros of polynomial systems. In your system J2 the one-dimensional component is a double component, which can't be detected with these methods (at least not without some more effort, there is a strategy called deflation for handling components of higher multiplicity, but this is currently not implemented in our software).

About your second example: should this be a1b1 or a1*b1? (i.e., is a1b1 one variable or a product of two?). What dimension should these components have?

It should be said that nid is still a bit experimental compared to other components of the software. We are still missing a good subroutine to detect singularities, which makes the method a bit unreliable.

simon-pepin commented 1 year ago

I was not aware of this limitation of polynomial homotopy continuation, thanks for pointing it out and for mentioning this deflation strategy.

In the second example, Markdown ate my stars, it should be

nid(System([a1*b1 , a2*b1 + a1*b2 , -c1^4 + a3*b1 + a2*b2 + a1*b3 ]))

The three irreducible components should all have dimension 4 and be given by V(a1,b1), V(a1,a2) and V(b1,b2).

Do you know other libraries which can perform nid (or, more modestly, compute the total dimension)? What about libraries to compute the real dimension for real algebraic sets? I had a quick look but yours was definitely the easiest to install and get started with right away.

PBrdng commented 1 year ago

In this example, are you viewing your variety in a weighted projective space or in affine space? I'm asking because the equations are weighted homogeneous. In any case, nid is only implemented for affine systems at this point (I want to come back to this later this year, but you know... not enough time :)).

When I solve two attempts, one with c1=1 and one with c1=0, I get reliably two components of degree 2 and two components of degree 1. Also, the linear space a1=b1=0 intersects your variety with multiplicity two, which gives you the same problem as we have discussed before.

The only other software that can do NID is Bertini as far as I know. We implemented a Julia interface (https://github.com/PBrdng/Bertini.jl) which should be kind of straight forward to use. Using polynomial homotopy continuation for the dimension of real varieties does not exist and is an open problem. There are methods from computational algebra like CAD, but they have doubly exponential complexity.

simon-pepin commented 1 year ago

This last example was affine. Thank you for your answers.

I am trying Bertini.jl right now but I have a small issue which I will write about on the appropriate "Issues" page.