Re: Graphs and reducibility(or something like that)

On Jul 22, 1:14 am, "Jon Slaughter" <Jon_Slaugh...@xxxxxxxxxxx> wrote:
"Proginoskes" <CCHeck...@xxxxxxxxx> wrote in message
news:1185082922.031088.289140@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

On Jul 21, 12:36 am, "Jon Slaughter" <Jon_Slaugh...@xxxxxxxxxxx>
wrote:
"Proginoskes" <CCHeck...@xxxxxxxxx> wrote in message
news:1184985789.069875.300990@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

On Jul 20, 6:49 pm, "Jon Slaughter" <Jon_Slaugh...@xxxxxxxxxxx> wrote:
I'm trying to simplify a network of electrical components and I'm curious if
theres any way to do this.

The network is equivalent to a graph but each edge consists has a "weight"
to it that is a function. Every edge has a similar function that "looks" the
same. Some nodes are known values while others are not.

The function is actually a linear differential equation with constant coefficients.

For example, I might have something like

+
/\
Z2 Z3
/ \
+--Z1--+

Where Z1, Z2, Z3 are differential equations.

In reality the graph is equivalent to a system of differential equations and
there are unknowns that exist which each branch and/or at some nodes.

I can convert the differential equations into algebraic equations by taking
the laplacian as one method but it still involves solving a large system.

I'm more interested in using the fact that each edge/branch is identical to
every other one except for some basic constants.

In essence I think I can treat each branch with a weight as a vector where
the elements of the vector are the coefficients of the DE.

so for example, I might have as a function L(t;....) = c*dV1/dt + a*V2 - b*V3

and so I could treat that as a vector like (a,-b,c). Every branch will just
have different coefficients in the function L but all of the same "form". I
feel that I could somehow use this to my advantage at simplifying the
graph/system. (Although I think the size of the vector grows exponentially
based on the size of the graph)

Is there anything I can do to simplify my problem? Maybe there are some
results in graph theory(I think this is where the problem comes from) that
can help? I'm actually wondering if there is some recursive way to simplify
the elements. Most of the "vectors" will only have non-zero elements for
those that represent coefficients around its branch.

In any case just looking for some ideas,

But where are you using the fact that you have a graph? How does the
edge uv related to the vertex u, for instance? And what kind of
structure do you have? For instance, do the differential equations
along a cycle satisfy some law like Kirchoff's?

I don't have a graph?

http://en.wikipedia.org/wiki/Glossary_of_graph_theory

A graph is just a set of verticies and edges which some relation that maps
pairs of verticies to edges? If thats the case then I definitely have a graph.

Oh, I see now. You are given an electrical network, which gives you
the graph.

Yes.

In any case, when I have all these weights there is an operation to combine
them in a specific way.

Suppose

W(Ni,Nj) is the "weight" of the edge NiNj which, for this problem, is
generally some linear differential equation.

Then we know that

sum(I(W(Ni,Nj)),j \in Q) = 0

This is kirchoffs current law which just says that the sum of the currents
entering a node is 0.

There is another law which states that the sum of the current around a
loop must add up to 0.

Well, the voltage drops...

I was going from (possibly faulty) memory here.

I is a "function" that maps the weight into its
equivilent current and Q is the set of indecies for nodes that are adjacient
to Ni.

We also would have something like

V(Ni) - sum(V(Nj),j \in Q) = 0

where V maps a node to a voltage and Q is an ordered closed list of
adjacient nodes. This would be kirchoffs voltage low.

(I'm kinda making up those equations as I go so they might not be totally
right)

I think I can see at least the general direction you're heading.

Whatever the laws are, they give you a system of equations. Kirchoff's
two laws will state that these equations are related to each other,
and so your system will be redundant. The redundancies, along the
edges, will be determined by the cycle-space of your graph G (a cycle
is basically a loop; you don't repeat vertices or edges until you're
done with walking around a cycle).

Right. And theres a lot of redundancy. Although this happens with or
without the branches all being "functionally" the same.

You can find the cycle space by setting up a particular matrix and
looking for a basis for its null space.

That might work. Although I have to figure out how to generate the matrix
easily. I guess each entry would represent an edge? (so each entry in the
matrix could represent the current, which is actually represented as a
solution to a differential equation)

Actually, I think you want to set up a matrix A whose rows represent
vertices of G and whose columns represent its edges. Orient the edges
of G arbitrarily, then construct A as follows: If the k-th edge is uv,
u is the i-th vertex, and v is the j-th vertex, you put a +1 in entry
(i,k) of A and a -1 entry in (j,k), and 0's elsewhere. This is
sometimes called the "incidence" matrix, and a minimal set of columns
which add up to the zero vector will give you a cycle of G. (Well, if
you orient some edges "backwards", you'll end up subtracting some of
the columns.)

But I think the main point here is that what I ultimately have is just
weights that are differential equations and inside those equations I have
all the info about the electronic aspect of the graph but abstractly its
just a graph with weights and I should be able to simplify it.

Whats really going on is that I have the weight function W(Ni,Nj) =
(V(t,Ni) - V(t,Nj))/Z_NiNj(t,N1,...,Nn;a1..am)

And you can think of this as ohms law. It essentially defines a current on
the edge NiNj. Then of course I must have sum(W(Ni,Nj)) = 0 for all Nj with
common vertext Ni. This is kirchoffs current law.

Maybe I'm starting not to make sense though. The idea is simply to
generalize the case for resistors.

Basically: "If you put other gadgets into the circuit (capacitors,
relays, whatever), you have other rules which determine how the
current flows through them", which are given by the differential
equations? And you're trying to simplify your system.

Yes.

I think essentially if A_ij is the ijth element of a matrix, then A_ij is
the current along the branch bound by the ith and jth nodes.

But the currents are solutions to differential equations involving other
currents and the "functional form" of the branch itself.

if I have some graph of resistors then what I really have is a linear
algebraic system of equation. Each edge creates an equation. The system
is
related to the graph. Change the graph and change the system.

Infact what we have is V(Ni) - V(Nj) - RNiNj*INiNj = 0 for each edge and
sum(NiNj) = 0 for each node Ni where the sum is over adjacient nodes to
Ni.

It seems I end up having to have an extra structure though that exists on
the graph. Maybe I need to think it out a little more.

Well, hopefully I've thrown out some useful ideas here, or failing
that, the sort of questions to ask. 8-)

Yes, it helps a little(just because it gets me thinking about it). I think
maybe I can mess around with the matrix idea and see what happens. I think
the problem is going to be that the elements of the matrix are not real or
complex numbers but vectors or differential equations. This is going to make
it harder to deal with but maybe the process is easier.

If, say, I have

V2
+
/\
Z2 Z3
/ \
V1 +--Z1--+ V3

and the the current I_i is the current through the branch B_i which is
equivilent to Z_i

The V_i's are voltages but also alias them as the nodes N_i.

So the "current matrix" would be 3x3 and look like

0 (V2-V1)/Z2 (V3-V1)/Z1
(V1-V2)/Z2 0 (V3-V2)/Z3
(V1-V3)/Z1 (V2-V3)/Z3 0

As you can see, in this case its symmetric which helps. That is not a
property of the "functional form" of the Z's though.

Also each element is really an expression involving unknowns. In this case I
would have to specify two of the 3 V's to get a solution.

In this case, sum(row) = 0 because of conservation of charge. I believe that
should hold in general.

(because row i is the ith node and sum of currents going into that
node(which are given by the columns) must be 0)

I'll need to think about it some more but it does seem like it actually
might work out.

Any more ideas? ;)

Not right off.

--- Christopher Heckman

.

Relevant Pages

  • Graphs and reducibility(or something like that)
    ... The network is equivalent to a graph but each edge consists has a "weight" ... Where Z1, Z2, Z3 are differential equations. ... the elements of the vector are the coefficients of the DE. ... Is there anything I can do to simplify my problem? ...
    (sci.math)
  • Re: Graphs and reducibility(or something like that)
    ... results in graph theory ... Wis the "weight" of the edge NiNj which, for this problem, is ... This is kirchoffs current law which just says that the sum of the ... weights that are differential equations and inside those equations I have ...
    (sci.math)
  • Re: Graphs and reducibility(or something like that)
    ... Where Z1, Z2, Z3 are differential equations. ... In reality the graph is equivalent to a system of differential equations ... In essence I think I can treat each branch with a weight as a vector ... This is kirchoffs current law which just says that the sum of the currents ...
    (sci.math)
  • Re: Graphs and reducibility(or something like that)
    ... The network is equivalent to a graph but each edge consists has a "weight" ... Where Z1, Z2, Z3 are differential equations. ... the elements of the vector are the coefficients of the DE. ...
    (sci.math)
  • Re: Graphs and reducibility(or something like that)
    ... The network is equivalent to a graph but each edge consists has a "weight" ... Where Z1, Z2, Z3 are differential equations. ... the elements of the vector are the coefficients of the DE. ...
    (sci.math)