> dynamic programming e.g. https://www.geeksforgeeks.org/dynamic-programming/
/c On Friday, September 3, 2021 at 3:48:30 PM UTC-5 [email protected] wrote: > 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/aaa03ff1-c97f-4888-bece-a6bf7612ceean%40googlegroups.com.
