I'm not obvious about using the shortest path algorithms to solve the algebraic equations, than the graph connectivity itself. Because we need to find a way how to model the 'distance' parameter as well.
Although it could directly model some algebraic problems like "bellman equation" and maybe some stuff in tropical algebra, and I also heard that shortest path algorithms can be used to solve some inequalities in difference arithmetic (simultaneous inequality of x - y = c forms) so things like these could be assembled On Friday, January 20, 2023 at 3:27:38 PM UTC+2 Oscar wrote: > On Fri, 20 Jan 2023 at 06:14, Chris Smith <smi...@gmail.com> wrote: > > > > Just read about https://arxiv.org/abs/2203.03456 in Quanta artical > https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/. > > One of the algorithms used in the solution computes a low-diameter > decomposition of the graph, identifying groups of nodes which are "close" > to each other. The phrase "strongly connected components" appeared in the > discussion and that got me wondering if such graph analysis might be > applied to systems of equations to identify groups of equations that could > be partially solved in isolation of others (for a sparse matrix). > > This is something that I've thought about but haven't quite come up > with the right way to express the system of equations as a directed > graph. Currently solve will represent a system of equations as an > *undirected* graph in the following way: > > 1. The equations are the vertices of the graph > 2. An edge exists between two equations if one or more of the > unknowns appears in both. > > Then the system of equations is split into connected components. The > result is that if you have something like > > solve([x+y, x-y-1, z+w, z-w+1], [x,y,z,w]) > > then it is possible to split that into two separate system of equations: > > solve([x+y,x-y-1], [x,y]) > solve([z+w,z-w+1], [z,w]) > > then the Cartesian product of the solutions is the set of solutions to > the original system. > > In the case of ODEs dsolve can go further and define an *undirected* > graph so if you have > > x' = 1 > y' = x + z > z' = x - y > w' = z > > We can say that the variables x, y, z and w are the vertices or that > the equations are the vertices since there is a one-to-one > correspondence. There is an arc from variable v1 to variable v2 if v2 > appears on the rhs of the ODE for v1. Then the strongly connected > components give a sequence in which the system can be solved: > > 1. Solve the ODE for x and substitute into the other ODEs > 2. Solve the two middle ODEs for y and z together as a system > 3. Solve the final ODE for w (after substituting for z) > > The undirected nature of the graph here arises naturally from > distinguishing which variable is differentiated in each ODE. I don't > know how to define the same for algebraic equations though. If you had > something like this > > x = 1 > y = x + z > z = x - y > w = z > > then you could do the same: solve eq1 for x, then eq2 and eq3 for y > and z and finally eq4 for w. I don't know how to define a graph so > that this always comes out in the strongly connected components of > that graph though. Let's suppose that equations are vertices. The key > observation is that x appears in an equation on its own. Then after > eliminating x there are equations involving only y and z but not w. > I'm not sure how to express that as a directed graph with arcs though. > In terms of the variables the desired graph structure is like: > > y -> z > y -> x > z -> y > z -> x > w -> z > > It is this graph whose strongly connected components are [{x}, {y, z}, > {w}]. Or perhaps in terms of equations: > > eq2 -> eq1 > eq2 -> eq3 > eq3 -> eq2 > eq3 -> eq1 > eq4 -> eq2 > eq4 -> eq3 > > Here an arc exists from eqi to eqj if eqi depends on a variable that > is in eqj or something. How do we define the arcs so that we don't > have edges like eq1 -> eq2 though because that would ruin the strongly > connected components that we want? > > Checking for equations with only one variable is simple and should be > done. I'm not sure we need a graph for that though: > > 1. Loop through the equations > 2. If the equation has a single unknown x then consider that unknown > solved (although don't actually solve it yet). > 3. Build a list of all equations that only have x as unknown. > 4. Now that x is "known" reevaluate whether any other equation can > be considered to have a single unknown. > > I expect that it is important to distinguish how exactly an unknown > appears in an equation. For example if we have x + y**2 - 1 then it is > better to solve this for x in terms of y than vice versa. That might > lead to different levels where first any variables appearing linearly > somewhere are eliminated. Then variables that can be solved by a > simple inversion, then polynomial, etc. > > -- > Oscar > -- 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+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/bd187dad-c998-44fa-87d0-2e27c10e89ffn%40googlegroups.com.
