0
$\begingroup$

I am not tremendously familiar with electrical circuits (I have some memories, but too long ago) and now I have come accross a problem where I need to compute the resistance distance in a graph.

So, given a circuit of resistances (for instance a grid of resistances) I found the definition of the resistance distance in Wikipedia and here Confused on Calculating Resistance Distance Matrix But in BOTH cases, the resistances are all of 1 Ohm.

Is it possible to apply the same formula when the resistance values are different from one another? If not, what formula am I looking for?

Also, so I understand the overall concept: this would allow me to chose two points x and y in the circuit, and know what equivalent value of resitance I would need to wire directly between them to have an equivalent network, right?

In terms of scale, how well does computing this distances scale? Say I have 1million crossings/nodes. Is the matrix computation fast enough or do physicist have some trick to accelerate calculations?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ If you have an inhomogeneous network, in general you will have to use numerical methods to find the solution (Spice can do this for you for maybe up to thousands of resistors, for larger networks you will need a specialized code). It sounds more like you are asking how to scale a homogeneous network, though? Or are you looking for methods to do random networks? That's an entire mathematical discipline of its own, I believe. As far as computational complexity is concerned, you are iterating over a linear equation, so it should be $O(n^2)$ or, at most $O(n^2\ln n)$, I believe. $\endgroup$ – CuriousOne Jun 2 '16 at 23:18
  • $\begingroup$ Thanks for the comment. Well, first I would like to know, for "small" size networks (maybe few hundred nodes, or up to a few thousand) how to compute the resistance between two nodes. In all my cases (small or big) the values of the resistances are random, always. $\endgroup$ – ddeunagomez Jun 3 '16 at 0:06
  • $\begingroup$ Naively I would write a Python script that generates a Spice netlist and then run LTSpice (linear.com/designtools/software/#LTspice) on that, just to get a feeling for the system. For large, and especially for infinite systems, you will have to resort to the literature about random networks. I am nearly certain that the theory for your problem is known, so there is prbably little need for trying to be creative... go look for "random resistor network" on the internet. I can already see that there is plenty of theory. $\endgroup$ – CuriousOne Jun 3 '16 at 0:10
2
$\begingroup$

I can see why you think physicists might have some insight into such a problem, because of the way it has been presented as an electrical circuit. Unfortunately we have little to add to what the Mathematicians and Computer Scientists can tell you. We certainly have no tricks which they do not already know about.

I think this is a mathematical or programming problem, rather than a physics problem. You can find relevant efficient algorithms yourself online for solving general networks. The best we can do is to suggest, for particular networks, that you make full use of symmetry properties and break the network down into simpler chunks.

"Efficient Methods for Calculating Equivalent Resistance Between Nodes of a Highly Symmetric Resistor Network" https://www.wpi.edu/Pubs/E-project/Available/E-project-032913-185209/unrestricted/networks.pdf

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks. I found online that to compute the resistance distance between x and y can be computed using the conductance matrix (or weighted Laplacian), then removing row and column y (creating a matrix G_y) and then solving the system G_yV=I where I is a vector containing only 0's except the xth element being a 1. Then the resistance distance between x and y would be v[x] ? Does this sound reasonable at all? In that case, for the size of my application (not too big graphs), solving that system should eb enough I think. $\endgroup$ – ddeunagomez Jun 3 '16 at 5:03
  • 1
    $\begingroup$ Sorry, I am neither a mathematician nor programmer. Neither have I much experience with matrix methods. So I am not able to comment on your proposals for a general solution algorithm. If the network has many nodes but relatively few connections, such general algorithms may be far less efficient than one which exploits particular properties of the graph. But with few nodes you may not care about efficiency. $\endgroup$ – sammy gerbil Jun 4 '16 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.