klee669
commented
1 year ago Thanks for your interest in the package. Sorry for the late reply.
- Having a square system is necessary for RPH. However, even if you have inequality constraints, assuming that all of those are active, you may construct a square system.
- Can you point out an example that is patchworked in PolynomialTestSystems.jl? I've worked through examples in this package but it seems that none is patchworked. The current way of patchworkedness is too strict so that it barely returns true even if it is. However, you may try RPH even if it is not patchworked. For example, running
F = System(equations(chandra(3))); B = generate_binomials(F); rph_track(B,F)returns all 4 real solutions. - We haven't explored the complexity of the algorithms. The condition we need to satisfy is to check if the homotopy path constructed passes through the discriminant of the system (if so, the number of real solutions changes so that we don't know we found all real solutions). However, as I mentioned, you may try RPH even if this condition is unsatisfactory. In this case, more real solutions may not be found.
Hope it helps!
Problem background: I am now going to use a system of equations to solve a practical problem that may be large in scale. Now the form of the system of equations is a linear complementary problem. I have used the complex polyhedral homotopy algorithm, but it gets too many complex solutions, which makes the calculation very difficult. Slow, I hope to use the RPH algorithm you proposed to improve the speed of solving, because I only need real solutions, complex solutions do not make any sense to me, the package I am currently using is https://arxiv.org/pdf/2207.05323, I I have encountered some problems, and I don’t know if I can use RPH directly, I hope to get your help, thank you very much!
The following is my question:
1.I found that all polynomials must be equal to zero when the homotopy continuation method solves the equation system problem, but the standard LCP problem has two constraints greater than zero, so I use the KKT condition to convert the LCP problem into an unconstrained equation system, with Expect to use your method to solve only on the field of real numbers,But the KKT condition will make the number of equations more than the number of unknowns, which is inconsistent with n equations and n unknowns in your paper. Is this a necessary condition for RPH? <粘贴的图形-1.png>
2.I tested the RPH algorithm with the common benchmarks provided by PolynomialTestSystems.jl(https://www.juliahomotopycontinuation.org/PolynomialTestSystems.jl/v0.1.0/), but none of them can get a real solution, even if it is patchworked. These benchmarks are n equations and n unknowns, but in my test, only very simple equations can get real solutions. Is there a problem?
3.Will the complexity of the RPH algorithm grow exponentially with the size of the problem? There may be millions of systems of equations to be solved.What does the system of equations in your paper need to satisfy certain conditions mean? Is there a more specific example to refer to?