increasing weight of n-size subsets algorithm

[Chris Smith]

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.

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.

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.

/c

[Aaron Meurer]

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 sympy+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/5fa892ee-3b16-43ce-9d49-a23347ba9616n%40googlegroups.com.

[Oscar Benjamin]

Groebner bases are used but solve_poly_system only handles the
zero-dimensional case so underdetermined cases fall back to the more
general (and less rigorous) algorithm. Using Groebner bases does not
make the correct order of variables trivial because the Groebner basis
itself depends on some order of the variables and more importantly on
the associated monomial ordering.

--
Oscar

[Chris Smith]

> dynamic programming

e.g. https://www.geeksforgeeks.org/dynamic-programming/

/c