back
17 comments
A version of this was set to me in a university interview.

There is an easier and far more elegant way to solve this than the solution given. Consider the circuit as two superimposed elements; one with a current being injected at the first point and flowing outward to a sink at infinity, and the second with current flowing in from a source at infinity and exiting at the second point. (For the sake of argument, say the current is 1 amp).

The current flow patterns in each case are easy to calculate because of the symmetry of each problem.

Now add the two superimposed elements together, and the sources and sinks at infinity cancel out, leaving only the point source and sink.

You now know the current through the overall circuit and the currents through each resistor, and because you know the values of the resistors, you also know the voltages across each resistor. Add up the voltages along any simple path between the two points to get the voltage between the points, and since you also know the overall current, you can now calculate the equivalent resistance.

I believe the following has the symmetry based solution you mention (and more!) https://www.mathpages.com/home/kmath668/kmath668.htm
That's the one.
Indeed, sounds like an interesting approach! This was just the first thing that came to my mind and it was cool to relate a concept from thermodynamics to electronics. I'll go and see if I can find the superposition version now.
Physicists like to call it heat equation. I like to call it energy preserving Gaussian blur. I mean, it's more fundamental than just physics. To me, it seems a core mathematical function. https://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/
The classic demoscene fire effect is surprisingly simple and at the same time surprisingly physically accurate, or at least physically inspired: https://lodev.org/cgtutor/fire.html
I believe it's a kinda-sorta reformulation of the Gauss-Seidel method of solving systems of linear equations (which, obviously are fundamental in physics).
I once found an exact solution to this problem (exact in some limit) in a condensed matter physics textbook. I never managed to go back and find the textbook name (it was a library book). I was wondering if someone would recognize the textbook and tell me the name.
The only analytical solution I could find was this:

https://www.mathpages.com/home/kmath668/kmath668.htm

I admit it kinda flew over my head (as I mentioned, I'm an empiricist through and through)

Nice write-up.

Latest generation circuit simulators don't solve the whole R or RC matrix anymore but they deduce the circuit to an equivalent one between the two points of interest during netlisting. If you have only resistors like this, it only makes sense to deduce it to a single equivalent resistor. This is one of the major simulation speed-up techniques enabling us to simulate more complicated circuits.

Got a ref? I haven't seen anything like this in the DAC (Design Automation Conference) proceedings, but I could very well have missed it.
I don't think they disclosed their algorithms but both Cadence Spectre-X and Mentor AFS-XT have an "improved" RC matrix solver as they market it. I think Spectre-X was launched at DAC 2019, but I've been using it since 2018. AFS-XT is launched couple of years ago as a response. The main goal of RC reduction is post-layout simulation. With these simulators what you would see in the results is there is a primitive called RC, which doesn't exist in the netlist. You need to define an fmax of the circuit, and it will reduce RC routing parasitics to approximately create same delays within that frequency range with a much more reduced matrix. Netlisting take some time but simulation is like 10x faster due to this reduction. I'm mainly using FinFET processes, so each transistor comes with tens of parasitics annotated. For a moderately large design it's normal to have millions of R and C.

There are also tools doing this on the extracted netlist directly by the way. Cadence's tool is called Quantus Standalone Reduction (qreduce).

Thanks for the breadcrumbs. I'll follow them around.
It'd be cool to learn how one could reduce this resistances in this grid to an equivalent resistance. Perhaps you could share some insights?
Stallman's (or Sussman?) thesis back in the 70s dealt with something similar. Basically an "AI system" that solves circuits by transforming them to simpler circuits using heuristics. It even solves BJTs by assuming the state its run and then seeing if the circuit is self consistent.
It looks possible for finite circuits. I doubt there is a general method for infinite systems, because the details of the infinite network are difficult to automate.

(For example, cut all the resistance that connect (x,0) and (x+1,0) when x is a prime number. The solution posted in the comments here assume a very even network, and adding some "random" cuts would break the symmetry.

I think there are numerical solutions possible for any network. Worst case solving KVL KCL to find the equivalent resistance between two nodes is an option. In a real circuit netlist the number of nodes is finite and often you can just ignore dangling resistances.