Resistor combination calculator

[acolomitchi]

I mean finding the equivalent resistance between any two nodes of an arbitrarily complex resistor network. It's a kind of opposite problem compared to finding the replacement network for a missing resistor value. When finding the network, you try to find the best network for specified value. When solving, you are given a network, and now you are trying to find the equivalent resistance. This is a fascinating problem, especially if the network is large.

"Arbitrary complex resistor network"...hmmm... nerd sniping, are you?

From a pragmatical point of view, I'll say that the UI is going to take more effort that I can put in - if you volunteer to write the user interface and provide me the connectivity network (resistance between node i,j), then I'll consider.

As for the actual computation, I'd go on this path: Simplifying complex resistor networks - for pragmatical real-world network resistors (on the order of hundreds up to 1000) would be feasible even in browser.

If linear system solving is too trivial (it's only O(N³⁾ complexity... with a little bit of elbow grease maybe a O(N² log(N)), then I can think of an approach of NP-complexity that is very simple to program:
1. linearity of the system conduces to: the conductance of a resistor network between two nodes is the sum of conductances of all simple paths between the two nodes considered.
2. plug in a simple algo to enumerate all the simple (no node repetition) paths between the two nodes - problem already known as NP hard (come on, don't be a wimp, what those computers are for anyway?) - compute the conductances, invert and come back with the answer.

Speaking of nerd-sniping: have fun analyzing this one.

[acolomitchi]

The paper by Klein and Randic (http://link.springer.com/article/10.1007/BF01164627) has a good explanation

Thanks for the ref.

[Kirr]

I mean finding the equivalent resistance between any two nodes of an arbitrarily complex resistor network. It's a kind of opposite problem compared to finding the replacement network for a missing resistor value. ... This is a fascinating problem, especially if the network is large.

Yes it is. There is a known solution for computing the resistance between any two points in a given network of resistors, but you need something like MATLAB or SageMath to compute it, because it involves taking the Moore-Penrose pseudoinverse of a noninvertible matrix. If you google "resistance distance", the formula is on the wikipedia page, but it's not the best explanation. The paper by Klein and Randic (http://link.springer.com/article/10.1007/BF01164627) has a good explanation, but unfortunately there doesn't seem to be a copy of it on the web. PM me if you want a copy.

Thanks for the reply! (PM sent).

So far I've been just toying with the naive approach to solving, that is, repeatedly applying the star-mesh transform to eliminate the nodes one by one. Surprisingly it works not too bad (or, at least much better than I expected). I'm curious if matrix-based approaches are known to be much faster.

In general, I guess we can distinguish different levels of a solution (when finding the equivalent resistance):
1. Approximate solution (perhaps using numerical approaches).
2. Exact answer. This is what I'm trying to do.
3. Symbolic answer. (A formula for a given topology).

I just wonder what is the fastest (or most scalable) method for each of the three cases, for large networks. In case of symbolic answer, the formula could grow fast with network size. But the other two should scale to thousands of resistors.

[Kirr]

"Arbitrary complex resistor network"...hmmm... nerd sniping, are you?

Well may be just a little. Actually it took some self-control to stop myself from posting that same link.

From a pragmatical point of view, I'll say that the UI is going to take more effort that I can put in - if you volunteer to write the user interface and provide me the connectivity network (resistance between node i,j), then I'll consider.

I decided to just make it a text input box, thus skipping the GUI design entirely.

As for the actual computation, I'd go on this path: Simplifying complex resistor networks - for pragmatical real-world network resistors (on the order of hundreds up to 1000) would be feasible even in browser.

If linear system solving is too trivial (it's only O(N³⁾ complexity... with a little bit of elbow grease maybe a O(N² log(N)), then I can think of an approach of NP-complexity that is very simple to program:
1. linearity of the system conduces to: the conductance of a resistor network between two nodes is the sum of conductances of all simple paths between the two nodes considered.
2. plug in a simple algo to enumerate all the simple (no node repetition) paths between the two nodes - problem already known as NP hard (come on, don't be a wimp, what those computers are for anyway?) - compute the conductances, invert and come back with the answer.

Interesting. I wonder how that would perform for large networks.

Speaking of nerd-sniping: have fun analyzing this one.

Well I guess you mean the resistor mesh on the right? It's too small for a good benchmark, but may it can serve as a well known example. Good idea!

[acolomitchi]

In general, I guess we can distinguish different levels of a solution (when finding the equivalent resistance):
1. Approximate solution (perhaps using numerical approaches).
2. Exact answer. This is what I'm trying to do.
3. Symbolic answer. (A formula for a given topology).

I just wonder what is the fastest (or most scalable) method for each of the three cases, for large networks. In case of symbolic answer, the formula could grow fast with network size. But the other two should scale to thousands of resistors.

Just from curiosity, is there any practical consideration in the problem (perhaps outside EE)?
Is so, would you mind to share?

[The Electrician]

So far I've been just toying with the naive approach to solving, that is, repeatedly applying the star-mesh transform to eliminate the nodes one by one. Surprisingly it works not too bad (or, at least much better than I expected). I'm curious if matrix-based approaches are known to be much faster.

In general, I guess we can distinguish different levels of a solution (when finding the equivalent resistance):
1. Approximate solution (perhaps using numerical approaches).
2. Exact answer. This is what I'm trying to do.
3. Symbolic answer. (A formula for a given topology).

I just wonder what is the fastest (or most scalable) method for each of the three cases, for large networks. In case of symbolic answer, the formula could grow fast with network size. But the other two should scale to thousands of resistors.

The network to be solved can be represented as an admittance matrix.  The graph theory people would call this the "Laplacian matrix".  See:

https://en.wikipedia.org/wiki/Laplacian_matrix

This explanation assumes that all the resistors (conductances) in the network are all 1 ohm, but a network with any value resistors can be solved the same way.  A network being analyzed by an EE would usually have one node grounded, the reference node.  In this case, the admittance matrix (Laplacian matrix) is not singular, so the Moore-Penrose matrix need not be calculated; just a plain old ordinary inverse will do the job.  Having the inverse, the two nodes between which the resistance is wanted define a 2x2 submatrix in the inverse.  If the admittance matrix of the network under consideration is denoted Y, its inverse can be denoted Z.

If there are N nodes in the network, the the element of the Z matrix corresponding to node j will be Zjj.  If we want the resistance between nodes j and k, we need to do some arithmetic on four elements of the Z matrix.  The desired resistance is given by Req = Zii+Zjj-Zij-Zji

See: https://en.wikipedia.org/wiki/Resistance_distance

A network of the sort beloved by the graph theorists probably won't have one node grounded, so in that case the admittance matrix Y will be singular, and the Z matrix will be the Moore-Penrose pseudoinverse.  Once the pseudoinverse is calculated, we have again Req = Zii+Zjj-Zij-Zji

I can calculate the pseudoinverse on my HP50G calculator for numerical admittance matrices up to order 10 in only a few seconds.

[Kirr]

Just from curiosity, is there any practical consideration in the problem (perhaps outside EE)?
Is so, would you mind to share?

This paper talks about application for electrostatic discharge analysis: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5356296

"Large resistor networks arise during the design of very-large-scale integration chips as a result of parasitic extraction and electro static discharge analysis. Simulating these large parasitic resistor networks is of vital importance, since it gives an insight into the functional and physical performance of the chip."

For non-EE example, I saw resistor networks used in electrical impedance tomography research. Also there seems to be a large amount of research on random and diluted resistor networks, but I'm not sure how much of it is practical.

The simplest practical use is verifying resistor networks found by a network finder.

[acolomitchi]

A network of the sort beloved by the graph theorists probably won't have one node grounded, so in that case the admittance matrix Y will be singular, and the Z matrix will be the Moore-Penrose pseudoinverse.

The thing I don't get is: why the matrix is singular? A singular matrix usually denotes a "not enough constrained" system, with linearly dependent rows, leading to possibly many solutions when involved in a system of equations.

In practice, a (non-disjoint) network will always have one and only one resistance between any two nodes, why would one need to introduce the assumption of one node linked to the ground?

[The Electrician]

A network of the sort beloved by the graph theorists probably won't have one node grounded, so in that case the admittance matrix Y will be singular, and the Z matrix will be the Moore-Penrose pseudoinverse.

The thing I don't get is: why the matrix is singular? A singular matrix usually denotes a "not enough constrained" system, with linearly dependent rows, leading to possibly many solutions when involved in a system of equations.

In practice, a (non-disjoint) network will always have one and only one resistance between any two nodes, why would one need to introduce the assumption of one node linked to the ground?

Because voltage is a relative quantity.  Voltmeters have two probes for a reason.  You must measure voltages between two points.  If you had a network of resistors floating in the air, and you wanted to know the voltage at one of the nodes how would you measure it?  So without a reference the voltages at various nodes (taken one at a time) are indeterminate; you can only find voltages between nodes.  Choosing one node as a reference, and conventionally calling it "ground", adds a constraint to the system.  Then the admittance matrix is no longer singular.

PM me a good email address and I'll send you a relevant paper.

[acolomitchi]

PM me a good email address and I'll send you a relevant paper.

Done.