I am trying to solve a system of polynomial equations with a divide-and-conquer approach. Essentially, I want to split a system of polynomials into subsystems, compute their witness sets and then start intersecting witness sets until I arrive at the final intersection which represents the solution to the original system. We had a brief email exchange about this a year ago, where you showed me your paper (http://homepages.math.uic.edu/~jan/par_solver.pdf) which is what I now also aim to do (without the parallelization necessarily). I believe, however, that there is a problem with the witness set that is returned by the diagonal solver in phcpy, or I am misunderstanding something and should do something differently.
Consider the following piece of code. The system is actually generated by my algorithm, so these are the types of problems I need to be able to solve.
Compute the solutions to the overall system first, just for checking purposes.
Solve the three subsystems.
Intersect subsystem 1 and 2.
Reformat the witness set that was output in step 3. Here I use the reformat_solutions function, which I made to add the zero slack variables back to the solutions. If this is wrong and creating the problem, that would also be nice to know. I will add the code for that to the bottom of this issue.
Intersect subsystem 3 with the witness set from the previous intersection.
The output from this code is one of four things. Sometimes it raises the following error:
NaN******
^
SyntaxError: invalid syntax
Otherwise, it returns either no solutions, one of the two correct solutions and very rarely both correct solutions. The fact that it does sometimes return (part of) the solution leads me to believe that there is a subtle bug involved here.
It is interesting to note that when not calling my reformat_solutions function, but solving the embedded system again from scratch, the final intersection does work. However, this defeats the purpose of using the diagonal solver in the first place and is therefore not what I want.
My implementation for reformat_solutions.
def reformat_solutions(sols, dim):
from phcpy.solutions import endmultiplicity, diagnostics, coordinates, make_solution
new_sols = []
for sol in sols:
names, values = coordinates(sol)
err, rco, res = diagnostics(sol)
t, m = endmultiplicity(sol)
for slack_var_idx in range(dim):
names.append(f'zz{slack_var_idx + 1}')
values.append(complex(0., 0.))
updated_sol = make_solution(names, values, err=err, rco=rco, res=res, tval=t, multiplicity=m)
new_sols.append(updated_sol)
return new_sols
I have been working on and off on my algorithm for a year now, and this problem is a huge roadblock that I just cannot seem to solve. If you need any additional information, I would be very happy to share it!
I am trying to solve a system of polynomial equations with a divide-and-conquer approach. Essentially, I want to split a system of polynomials into subsystems, compute their witness sets and then start intersecting witness sets until I arrive at the final intersection which represents the solution to the original system. We had a brief email exchange about this a year ago, where you showed me your paper (http://homepages.math.uic.edu/~jan/par_solver.pdf) which is what I now also aim to do (without the parallelization necessarily). I believe, however, that there is a problem with the witness set that is returned by the diagonal solver in phcpy, or I am misunderstanding something and should do something differently.
Consider the following piece of code. The system is actually generated by my algorithm, so these are the types of problems I need to be able to solve.
What this code does is:
reformat_solutions
function, which I made to add the zero slack variables back to the solutions. If this is wrong and creating the problem, that would also be nice to know. I will add the code for that to the bottom of this issue.The output from this code is one of four things. Sometimes it raises the following error:
Otherwise, it returns either no solutions, one of the two correct solutions and very rarely both correct solutions. The fact that it does sometimes return (part of) the solution leads me to believe that there is a subtle bug involved here.
It is interesting to note that when not calling my
reformat_solutions
function, but solving the embedded system again from scratch, the final intersection does work. However, this defeats the purpose of using the diagonal solver in the first place and is therefore not what I want.My implementation for
reformat_solutions
.I have been working on and off on my algorithm for a year now, and this problem is a huge roadblock that I just cannot seem to solve. If you need any additional information, I would be very happy to share it!