Solving system of polynomial equations

[blegat]

It would be nice to have an implementation independent interface for solving systems of polynomial equations. There will soon be an implementation here using the classical Groebner basis method and relying on MultivariatePolynomials to do all the work. We have already a nice interface to build an algebraic set

@set x == 1 && y == 2

Now, we need an interface to query the solutions of the equations. Here these are the points of the sets so we could just iterate through the set and in case the set was not zero dimensional then throw an error

collect(@set x^2 == 1 && y == 2) # -> [(-1, 2), (1, 2)]
collect(@set x == y) # -> error not zero dimensional

The problem with the current interface is that we currently do not specify anywhere what will be the algorithm used to find the points. The user should be able to say that he wants another library do deal with it, e.g.:

• https://github.com/wbhart/Singular.jl
• https://github.com/saschatimme/HomotopyContinuation.jl

cc @saschatimme

[blegat]

We could have a function

algebraicset(p::AbstractVector{<:AbstractPolynomialLike}, lib=defaultlibrary(p))

The macro @set would call algebraicset and if a second argument is given to it, it gives it to algebraicset.

[saschatimme]

That would be doable, but at least my stuff has a lot of configuration parameters. So the second argument would need to take keyword arguments, depending on the algorithm or maybe something like a „configuration struct“.

[blegat]

The way the second argument is constructed is not limited. You can even do

lib = HomotopyContinuationLibrary(...)
@set x == 0 lib

[blegat]

@saschatimme I have set up the necessary infrastructure. If you define HomotopyContinuationSolver <: AbstractAlgebraicSolver, you can do

solver = HomotopyContinuationSolver(...)
@set x == 0 solver

[saschatimme]

That's nice, I will add that then soon

[chriscoey]

hey @blegat, I was asking this question over at https://github.com/JuliaHomotopyContinuation/HomotopyContinuation.jl/issues/59: do you know of any methods for (or papers on) finding the critical points of a function that lie in a basic semi-algebraic set (BSS)?

say I have n variables and call the BSS S. then I could just pose it as finding the points (assume finitely many) in another BSS described by S and the n equalities defining the roots of the gradient. (if i wanted, i could add more inequalities forcing the critical points to be local minima, say.) ofc I could find all the critical points from the square system using existing methods discussed here, and then later exclude those points outside S. but this set of points could be much larger than its intersection with S, so it could be much faster to just search on the BSS, if there's some way to do that.

it's something i'm willing to work on if I can find some algorithms for it. obviously it's a very "hard" problem, but n and function degree and description of S will be small/constant.

thank you!

[chriscoey]

one possible approach is to use the obvious idea from this slide (source): that is, for each constraint that isn't an equality, to introduce an extra variable y and rewrite the constraint as an equality using y.

for my specific problem stated in the previous post, I already assumed that there are finitely many critical points of my function f(x) over R^n (the square system given by the gradient is zero-dimensional). what I care about is restricting my search for these points to S, i.e. I'm still looking for a finite number of points. unfortunately it seems that if I use this approach of converting each non-equality (!=, >, >= etc) constraint i from S to an equality with an extra variable y_i, the system can be non-zero-dimensional / underdetermined because of the extra variables y.

so i guess my question here is: is there some practical extension of your classical Groebner basis method that can restrict its search for the solutions to a zero-dimensional system (of equalities) according to some additional non-equality constraints (ie. semialgebraic not algebraic)? do you know of any implementations or papers I can look at? I will be interested to potentially contribute an implementation.

[saschatimme]

@blegat HomotopyContinuation 2.4 now supports this

[saschatimme]

And I remember that somewhere this is used to extract measures, right? This could be a nice post on JuliaHomotopyContinuation.org if you are interested :)