On Fri, Sep 3, 2021 at 12:10 PM Chris Smith <[email protected]> wrote: > > Backstory: > > When `solve` is given freedom to select the variables for which to solve n > equations it currently does so naively without consideration of how difficult > a particular n-length subsets of available variables. In PR #22016 I give 3 > equations in 5 variables, one of which should only be attempted if all others > have failed, i.e., it should be the last to enter the subsets of length 3. > > Oscar Benjamin recently modified solve to consider a complexity signature and > the same could perhaps be used for selecting a subset of variables. I was > thinking of giving each variable a value that depends on the number of > equations in which it appears non-linearly as a starter (though weighting for > the type of non-linearity might be a refinement, too). > > Question: > > So given a list of values, what is the algorithm other than brute force > (though maybe for the size of problems we anticipate being able to solve, > that will be sufficient) that will give the subsets in increasing order > according to sum of the complexity of each selected variable. > > Say the variables have assigned weight 1, 1, 2, 3, 3, 4, 5. The following > gives the different total weights possible: > > for i in sorted([(sum(i),i) for i in > multiset_combinations((1,1,2,3,3,4,5),3)]):i > ... > (4, [1, 1, 2]) > (5, [1, 1, 3]) > (6, [1, 1, 4]) > (6, [1, 2, 3]) > (7, [1, 1, 5]) > (7, [1, 2, 4]) > (7, [1, 3, 3]) > (8, [1, 2, 5]) > (8, [1, 3, 4]) > (8, [2, 3, 3]) > (9, [1, 3, 5]) > (9, [2, 3, 4]) > (10, [1, 4, 5]) > (10, [2, 3, 5]) > (10, [3, 3, 4]) > (11, [2, 4, 5]) > (11, [3, 3, 5]) > (12, [3, 4, 5]) > > (I know how to enumerate the ways to take each of these weights.) > > This is *almost* like the knapsack or making change problem, but not quite. > Any ideas or discussion about this would be appreciated, here or on #22016.
This sounds more to me like a problem that can be solved with dynamic programming. > > Introspection: > > I also realize that there is an aspect to solving systems of non-linear > equations that I have not fully appreciated. I would normally think of > working manually through a system by solving for one variable, substituting > it into all the other equations and then repeating the process until all > equations have been solved. If the system is non-linear you may miss > solutions depending on how you are solving the equations. Consider > > x*y -x = 0 and x + y - 2 > > If you solve the first for y you get 1 and substitution into the second gives > x = 1. The problem is you are dividing by x when solving for 1, which deletes that solution from the system. Dividing both sides of an equation by something can delete solutions in general, just as multiplying both sides can add spurious solutions. > If you solve the second for y you get 2-x and substitution into the first > give x*(1-x) which has solutions of 0 and 1 so there are two ways to make > these equations 0: x,y = (0,2) or (1,1). If the 2 is replaced with 2/y then > there are 3 possible solutions. > > It's easy to track for this simple case though (I am surprised to admit) that > I am less sensitive to recognizing this nuance than I should be. When there > are more equations, what is the most efficient way to solve the set of > equations and know that you have captured all solutions? (And if there are > more variables than the number of equations, how do you pick an easy subset > of symbols for which to solve?) Those are the questions that are driving the > question at the outset. For polynomials, the correct way to do this is using Groebner bases, which rewrite the polynomials into an equivalent triangular system, which means the "correct order" of variables is trivial. Is there a reason we don't always use them? Aaron Meurer > > /c > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/sympy/5fa892ee-3b16-43ce-9d49-a23347ba9616n%40googlegroups.com. -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6JfzfA99HFRUMy2RDqOArWk%2BkCGVA1f_ax-9pbdGz0q-w%40mail.gmail.com.
