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/CAHVvXxSEZmKuE7-9b%2B5PpO4Bv31_o2K6Q9sQKFrZZxLJOjjweA%40mail.gmail.com.
