Is there a general algorithm for solving resistive circuits?

Consider a 2Nx2N lattice with 1 Ohm resistors on edges and a 1V battery on the diagonal of the center square. What is the current through the network? (equivalently, what is R_eq)

For N=1 case this is 1A (series and parallel resistors). For N=2 there are some clever tricks using symmetry, since you can join nodes of equipotential without changing the current flow and “fold” along the axis of symmetry, like folding a napkin in half. N=3 requires us to have a few more tricks up our sleeve, and can’t be resolved easily without Wye-Delta transforms. However,

There is no general closed form formula for current through a resistor lattice.1

The difficult part is that order matters, and some operations aren’t reversible. Once you contract a node you break symmetry. You have to be smart about which ones to contract, replace, etc. so it’s the right shape. Topology matters.

There are many methods to approaching this, one is to represent circuits as graphs and an algorithm to apply the right operations in the right order2. A more general method is to do tree search over possible actions on the graph. Some may formulate as random walk along nxn cartesian grid (since electrons are just random walking!)3

A circuit is just a graph with a set of simple linear constraints. Ohm’s law and KVL/KCL are all you really need to describe flow in a circuit. Yet from this problem we see that they are capable of expressing complex non-linear functions. It’s surprising how we often think of generality in NN but this is also paralleled in hardware. Circuits run our computer chips, power GPU clusters, control the electrical grid, and command the world’s electrons (and can also prove the AM-GM inequality4).

circuits: linear rules (Ohm’s law, KCL/KVL). It’s amazing to be surrounded by machines of such generality power.

nn: linear maps (matmul) + non-linear activations

Both circuits and NNs can be viewed as universal computational systems. Circuits are Turing complete digital simulators, NNs are universal function approximators. It’s amazing to be surrounded by machines of such generality.

  1. for the infinite case this is the XKCD Nerd sniping problem, here and here ↩

  2. https://github.com/ellenjxu/circuits ↩

  3. “The equivalent resistance between a pair of nodes in an infinite lattice is directly related to the transition probability between these nodes under a suitably biased random walk” ↩

  4. https://knzhou.github.io/handouts/E3Sol.pdf (thanks to Daniel :)) ↩