Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

December 28, 2015

A Compositional Framework for Passive Linear Networks

Posted by John Baez

My main interest these days is ‘network theory’. This means slightly different things to different people, but for me it’s the application of category theory to complex systems made from interacting parts, which can often be drawn using diagrams that look like graphs with extra labels. My dream is to set up a new kind of mathematics, applicable to living systems from cells to ecosystems. But I’ve been starting with more humble networks, like electrical circuits.

Brendan Fong, at Oxford and U. Penn, has been really crucial in developing this approach to network theory. Here’s our first paper:

• John Baez and Brendan Fong, A compositional framework for passive linear networks.

While my paper with Jason Erbele studied signal flow diagrams, this one focuses on circuit diagrams. The two are different, but closely related.

Instead of trying to explain the connection, let me just talk about this paper with Brendan. There’s a lot in here, so I’ll only explain the main result. It’s all about ‘black boxing’: hiding the details of a circuit and only remembering its behavior as seen from outside. But it involves fun stuff about symplectic geometry, and cospans, and Dirichlet forms, and other things.

In late 1940s, just as Feynman was developing his diagrams for processes in particle physics, Eilenberg and Mac Lane initiated their work on category theory. Over the subsequent decades, and especially in the work of Joyal and Street in the 1980s, it became clear that these developments were profoundly linked: monoidal categories have a precise graphical representation in terms of string diagrams, and conversely monoidal categories provide an algebraic foundation for the intuitions behind Feynman diagrams. The key insight is the use of categories where morphisms describe physical processes, rather than structure-preserving maps between mathematical objects.

In work on fundamental physics, the cutting edge has moved from categories to higher categories. But the same techniques have filtered into more immediate applications, particularly in computation and quantum computation. Our paper is part of a new program of applying string diagrams to engineering, with the aim of giving diverse diagram languages a unified foundation based on category theory.

Indeed, even before physicists began using Feynman diagrams, various branches of engineering were using diagrams that in retrospect are closely related. Foremost among these are the ubiquitous electrical circuit diagrams. Although less well-known, similar diagrams are used to describe networks consisting of mechanical, hydraulic, thermodynamic and chemical systems. Further work, pioneered in particular by Forrester and Odum, applies similar diagrammatic methods to biology, ecology, and economics.

As discussed in detail by Olsen, Paynter and others, there are mathematically precise analogies between these different systems. In each case, the system’s state is described by variables that come in pairs, with one variable in each pair playing the role of ‘displacement’ and the other playing the role of ‘momentum’. In engineering, the time derivatives of these variables are sometimes called ‘flow’ and ‘effort’.

displacement:    qq flow:      q˙\dot q momentum:      pp effort:           p˙\dot p
Mechanics: translation position velocity momentum force
Mechanics: rotation angle angular velocity angular momentum torque
Electronics charge current flux linkage voltage
Hydraulics volume flow pressure momentum pressure
Thermal Physics entropy entropy flow temperature momentum temperature
Chemistry moles molar flow chemical momentum chemical potential

In classical mechanics, this pairing of variables is well understood using symplectic geometry. Thus, any mathematical formulation of the diagrams used to describe networks in engineering needs to take symplectic geometry as well as category theory into account.

While diagrams of networks have been independently introduced in many disciplines, we do not expect formalizing these diagrams to immediately help the practitioners of these disciplines. At first the flow of information will mainly go in the other direction: by translating ideas from these disciplines into the language of modern mathematics, we can provide mathematicians with food for thought and interesting new problems to solve. We hope that in the long run mathematicians can return the favor by bringing new insights to the table.

Although we keep the broad applicability of network diagrams in the back of our minds, our paper talks in terms of electrical circuits, for the sake of familiarity. We also consider a somewhat limited class of circuits. We only study circuits built from ‘passive’ components: that is, those that do not produce energy. Thus, we exclude batteries and current sources. We only consider components that respond linearly to an applied voltage. Thus, we exclude components such as nonlinear resistors or diodes. Finally, we only consider components with one input and one output, so that a circuit can be described as a graph with edges labeled by components. Thus, we also exclude transformers. The most familiar components our framework covers are linear resistors, capacitors and inductors.

While we want to expand our scope in future work, the class of circuits made from these components has appealing mathematical properties, and is worthy of deep study. Indeed, these circuits has been studied intensively for many decades by electrical engineers. Even circuits made exclusively of resistors have inspired work by mathematicians of the caliber of Weyl and Smale!

Our work relies on this research. All we are adding is an emphasis on symplectic geometry and an explicitly ‘compositional’ framework, which clarifies the way a larger circuit can be built from smaller pieces. This is where monoidal categories become important: the main operations for building circuits from pieces are composition and tensoring. Our strategy is most easily illustrated for circuits made of linear resistors. Such a resistor dissipates power, turning useful energy into heat at a rate determined by the voltage across the resistor. However, a remarkable fact is that a circuit made of these resistors always acts to minimize the power dissipated this way. This ‘principle of minimum power’ can be seen as the reason symplectic geometry becomes important in understanding circuits made of resistors, just as the principle of least action leads to the role of symplectic geometry in classical mechanics.

Here is a circuit made of linear resistors:

The wiggly lines are resistors, and their resistances are written beside them: for example, 3Ω3\Omega means 3 ohms, an ‘ohm’ being a unit of resistance. To formalize this, define a circuit of linear resistors to consist of:

  • a set NN of nodes,
  • a set EE of edges,
  • maps s,t:ENs,t : E \to N sending each edge to its source and target node,
  • a map r:E(0,)r: E \to (0,\infty) specifying the resistance of the resistor labelling each edge,
  • maps i:XN,i : X \to N, o:YNo : Y \to N specifying the inputs and outputs of the circuit.

When we run electric current through such a circuit, each node nNn \in N gets a potential ϕ(n).\phi(n). The voltage across an edge eEe \in E is defined as the change in potential as we move from to the source of ee to its target, ϕ(t(e))ϕ(s(e)).\phi(t(e)) - \phi(s(e)). The power dissipated by the resistor on this edge is then

1r(e)(ϕ(t(e))ϕ(s(e))) 2 \displaystyle{ \frac{1}{r(e)}\big(\phi(t(e))-\phi(s(e))\big)^2 }

The total power dissipated by the circuit is therefore twice

P(ϕ)=12 eE1r(e)(ϕ(t(e))ϕ(s(e))) 2 \displaystyle{ P(\phi) = \frac{1}{2}\sum_{e \in E} \frac{1}{r(e)}\big(\phi(t(e))-\phi(s(e))\big)^2 }

The factor of 12\frac{1}{2} is convenient in some later calculations.

Note that PP is a nonnegative quadratic form on the vector space N.\mathbb{R}^N. However, not every nonnegative definite quadratic form on N\mathbb{R}^N arises in this way from some circuit of linear resistors with NN as its set of nodes. The quadratic forms that do arise are called Dirichlet forms. They have been extensively investigated, and they play a major role in our work.

We write

N=i(X)o(Y)\partial N = i(X) \cup o(Y)

for the set of terminals: that is, nodes corresponding to inputs or outputs. The principle of minimum power says that if we fix the potential at the terminals, the circuit will choose the potential at other nodes to minimize the total power dissipated. An element ψ\psi of the vector space N\mathbb{R}^{\partial N} assigns a potential to each terminal. Thus, if we fix ψ,\psi, the total power dissipated will be twice

Q(ψ)=min ϕ N ϕ| N=ψP(ϕ) Q(\psi) = \min_{\substack{ \phi \in \mathbb{R}^N \\ \phi\vert_{\partial N} = \psi}} \; P(\phi)

The function Q: NQ : \mathbb{R}^{\partial N} \to \mathbb{R} is again a Dirichlet form. We call it the power functional of the circuit.

Now, suppose we are unable to see the internal workings of a circuit, and can only observe its ‘external behavior’: that is, the potentials at its terminals and the currents flowing into or out of these terminals. Remarkably, this behavior is completely determined by the power functional Q.Q. The reason is that the current at any terminal can be obtained by differentiating QQ with respect to the potential at this terminal, and relations of this form are all the relations that hold between potentials and currents at the terminals.

The Laplace transform allows us to generalize this immediately to circuits that can also contain linear inductors and capacitors, simply by changing the field we work over, replacing \mathbb{R} by the field (s)\mathbb{R}(s) of rational functions of a single real variable, and talking of impedance where we previously talked of resistance. We obtain a category Circ{Circ} where an object is a finite set, a morphism f:XYf : X \to Y is a circuit with input set XX and output set Y,Y, and composition is given by identifying the outputs of one circuit with the inputs of the next, and taking the resulting union of labelled graphs. Each such circuit gives rise to a Dirichlet form, now defined over (s),\mathbb{R}(s), and this Dirichlet form completely describes the externally observable behavior of the circuit.

We can take equivalence classes of circuits, where two circuits count as the same if they have the same Dirichlet form. We wish for these equivalence classes of circuits to form a category. Although there is a notion of composition for Dirichlet forms, we find that it lacks identity morphisms or, equivalently, it lacks morphisms representing ideal wires of zero impedance. To address this we turn to Lagrangian subspaces of symplectic vector spaces. These generalize quadratic forms via the map

(Q:𝔽 N𝔽)\Big(Q: \mathbb{F}^{\partial N} \to \mathbb{F}\Big) \mapsto

Graph(dQ)={(ψ,dQ ψ)ψ𝔽 N}𝔽 N(𝔽 N) *{Graph}(d Q) = \{(\psi, d Q_\psi) \mid \psi \in \mathbb{F}^{\partial N} \} \; \subseteq \; \mathbb{F}^{\partial N} \oplus (\mathbb{F}^{\partial N})^\ast

taking a quadratic form QQ on the vector space 𝔽 N\mathbb{F}^{\partial N} over the field 𝔽\mathbb{F} to the graph of its differential dQ.d Q. Here we think of the symplectic vector space 𝔽 N(𝔽 N) *\mathbb{F}^{\partial N} \oplus (\mathbb{F}^{\partial N})^\ast as the state space of the circuit, and the subspace Graph(dQ){Graph}(d Q) as the subspace of attainable states, with ψ𝔽 N\psi \in \mathbb{F}^{\partial N} describing the potentials at the terminals, and dQ ψ(𝔽 N) *d Q_\psi \in (\mathbb{F}^{\partial N})^\ast the currents.

This construction is well-known in classical mechanics, where the principle of least action plays a role analogous to that of the principle of minimum power here. The set of Lagrangian subspaces is actually an algebraic variety, the Lagrangian Grassmannian, which serves as a compactification of the space of quadratic forms. The Lagrangian Grassmannian has already played a role in Sabot’s work on circuits made of resistors. For us, its importance it that we can find identity morphisms for the composition of Dirichlet forms by taking circuits made of parallel resistors and letting their resistances tend to zero: the limit is not a Dirichlet form, but it exists in the Lagrangian Grassmannian.

Indeed, there exists a category LagrRel{LagrRel} with finite dimensional symplectic vector spaces as objects and Lagrangian relations as morphisms: that is, linear relations from VV to WW that are given by Lagrangian subspaces of V¯W,\overline{V} \oplus W, where V¯\overline{V} is the symplectic vector space conjugate to VV—that is, with the sign of the symplectic structure switched.

To move from the Lagrangian subspace defined by the graph of the differential of the power functional to a morphism in the category LagrRel{LagrRel} — that is, to a Lagrangian relation — we must treat seriously the input and output functions of the circuit. These express the circuit as built upon a cospan:

Applicable far more broadly than for our formalization of circuits, cospans model systems with two ‘ends’, an input and output end, albeit without any connotation of directionality: we might just as well exchange the role of the inputs and outputs by taking the mirror image of the above diagram. The role of the input and output functions, as we have discussed, is to mark the terminals we may glue onto the terminals of another circuit, and the pushout of cospans gives formal precision to this gluing construction.

One upshot of this cospan framework is that we may consider circuits with elements of NN that are both inputs and outputs, such as this one:

This corresponds to the identity morphism on the finite set with two elements. Another is that some points may be considered an input or output multiple times, like here:

This lets to connect two distinct outputs to the above double input.

Given a set XX of inputs or outputs, we understand the electrical behavior on this set by considering the symplectic vector space 𝔽 X(𝔽 X) *,\mathbb{F}^X \oplus {(\mathbb{F}^X)}^\ast, the direct sum of the space 𝔽 X\mathbb{F}^X of potentials and the space (𝔽 X) *{(\mathbb{F}^X)}^\ast of currents at these points. A Lagrangian relation specifies which states of the output space 𝔽 Y(𝔽 Y) *\mathbb{F}^Y \oplus {(\mathbb{F}^Y)}^\ast are allowed for each state of the input space 𝔽 X(𝔽 X) *.\mathbb{F}^X \oplus {(\mathbb{F}^X)}^\ast. Turning the Lagrangian subspace Graph(dQ){Graph}(d Q) of a circuit into this information requires that we understand the ‘symplectification’

Sf:𝔽 B(𝔽 B) *𝔽 A(𝔽 A) *S f: \mathbb{F}^B \oplus {(\mathbb{F}^B)}^\ast \to \mathbb{F}^A \oplus {(\mathbb{F}^A)}^\ast and ‘twisted symplectification’

S tf:𝔽 B(𝔽 B) *𝔽 A(𝔽 A) *¯S^t f: \mathbb{F}^B \oplus {(\mathbb{F}^B)}^\ast \to \overline{\mathbb{F}^A \oplus {(\mathbb{F}^A)}^\ast}

of a function f:ABf: A \to B between finite sets.

Symplectification and twisted symplectification are contravariant functors from FinsetFinset to LagrRelLagrRel. We need to understand how these apply to the input and output functions with codomain restricted to N\partial N; abusing notation, we write these as i:XNi: X \to \partial N and o:YN.o: Y \to \partial N.

The symplectification SfS f is a Lagrangian relation, and the catch phrase is that it ‘copies voltages’ and ‘splits currents’. More precisely, for any given potential-current pair (ψ,ι)(\psi,\iota) in 𝔽 B(𝔽 B) *,\mathbb{F}^B \oplus {(\mathbb{F}^B)}^\ast, its image under SfS f consists of all elements of (ψ,ι)(\psi', \iota') in 𝔽 A(𝔽 A) *\mathbb{F}^A \oplus {(\mathbb{F}^A)}^\ast such that the potential at aAa \in A is equal to the potential at f(a)B,f(a) \in B, and such that, for each fixed bB,b \in B, collectively the currents at the af 1(b)a \in f^{-1}(b) sum to the current at b.b. We use the symplectification SoS o of the output function to relate the state on N\partial N to that on the outputs Y.Y.

As our current framework is set up to report the current out of each node, to describe input currents we define the twisted symplectification:

S tf:𝔽 B(𝔽 B) *𝔽 A(𝔽 A) *¯S^t f: \mathbb{F}^B \oplus {(\mathbb{F}^B)}^\ast \to \overline{\mathbb{F}^A \oplus {(\mathbb{F}^A)}^\ast}

almost identically to the above, except that we flip the sign of the currents ι(𝔽 A) *.\iota' \in (\mathbb{F}^A)^\ast. This again gives a Lagrangian relation. We use the twisted symplectification S tiS^t i of the input function to relate the state on N\partial N to that on the inputs.

The Lagrangian relation corresponding to a circuit then comprises exactly a list of the potential-current pairs that are possible electrical states of the inputs and outputs of the circuit. In doing so, it identifies distinct circuits. A simple example of this is the identification of a single 2-ohm resistor:

with two 1-ohm resistors in series:

Our inability to access the internal workings of a circuit in this representation inspires us to call this process black boxing: you should imagine encasing the circuit in an opaque black box, leaving only the terminals accessible. Fortunately, this information is enough to completely characterize the external behavior of a circuit, including how it interacts when connected with other circuits!

Put more precisely, the black boxing process is functorial: we can compute the black-boxed version of a circuit made of parts by computing the black-boxed versions of the parts and then composing them. In fact we shall prove that Circ{Circ} and LagrRel{LagrRel} are dagger compact categories, and the black box functor preserves all this extra structure:

Theorem. There exists a symmetric monoidal dagger functor, the black box functor

:CircLagrRel\blacksquare: {Circ} \to {LagrRel}

mapping a finite set XX to the symplectic vector space 𝔽 X(𝔽 X) *\mathbb{F}^X \oplus (\mathbb{F}^X)^\ast it generates, and a circuit ((N,E,s,t,r),i,o)\big((N,E,s,t,r),i,o\big) to the Lagrangian relation

vGraph(dQ)S ti(v)×So(v)𝔽 X(𝔽 X) *¯𝔽 Y(𝔽 Y) *\bigcup_{v \in {Graph}(d Q)} S^t i(v) \times S o(v) \subseteq \overline{\mathbb{F}^X \oplus (\mathbb{F}^X)^\ast} \oplus \mathbb{F}^Y \oplus (\mathbb{F}^Y)^\ast

where QQ is the circuit’s power functional.

The goal of this paper is to prove and explain this result. The proof is more tricky than one might first expect, but our approach involves concepts that should be useful throughout the study of networks, such as ‘decorated cospans’ and ‘corelations’.

Give it a read, and let us know if you have questions or find mistakes!

Posted at December 28, 2015 12:02 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2860

8 Comments & 0 Trackbacks

Re: A Compositional Framework for Passive Linear Networks

It’s great to see this paper out. Did you manage to get anywhere with the question of whether the black-box functor is unique?

Posted by: Jamie Vicary on December 31, 2015 2:45 PM | Permalink | Reply to this

Re: A Compositional Framework for Passive Linear Networks

Yes, we are now able to give a different proof of the black box theorem, more along the lines you wanted, which involves proving that the category CircCirc is the “free symmetric monoidal category on [secret stuff].”

Thanks for reminding me—I’ve got a lot of grad students, and a lot of projects, and sometimes one or the other of them gets lost in the shuffle for a while. I need to match up this project with a student.

By the way, Brendan Fong and my student Brandon Coya are almost done with a nice paper proving that corelations are the “free symmetric monoidal category on [some other secret stuff].”

Posted by: John Baez on December 31, 2015 5:17 PM | Permalink | Reply to this

Re: A Compositional Framework for Passive Linear Networks

That’s great to have a more high-level understanding of Circ. So do you know, or would you guess, there to be other symmetric monoidal functors Circ\toLagRel, not equivalent to the black box functor?

Posted by: Jamie Vicary on December 31, 2015 10:49 PM | Permalink | Reply to this

Re: A Compositional Framework for Passive Linear Networks

Yes, there will be a lot of others, but we’ll be able to say pretty efficiently what makes the right one ‘right’. Basically it makes the resistors, inductors and capacitors do what they should. Pure category theory (symmetric monoidal category theory) does not know about that.

Posted by: John Baez on December 31, 2015 10:57 PM | Permalink | Reply to this

Re: A Compositional Framework for Passive Linear Networks

I am somewhat confused about the definition of a positive real function and the definition of a set of positive elements in section 3. The set of positive real functions defined as (s) +={Z(s):s(s)>0(Z(s))>0} \mathbb{R}(s)^+ = \{ Z \in \mathbb{R}(s) : \forall s \in \mathbb{C} \;\; \Re(s) \gt 0 \implies \Re(Z(s)) \gt 0 \} is not closed under multiplication. E.g. the identity function ss is in (s) +\mathbb{R}(s)^+, but clearly s*s=s 2s*s = s^2 is not.

I think you could take the set {Z(s):ss>0Z(s)>0}\{ Z \in \mathbb{R}(s) : \forall s \in \mathbb{R} \;\; s \gt 0 \implies Z(s) \gt 0 \} instead. This is a set of positive elements and is also a superset of (s) +\mathbb{R}(s)^+.

Posted by: Bernhard Reinke on January 1, 2016 2:11 PM | Permalink | Reply to this

Re: A Compositional Framework for Passive Linear Networks

Thanks for raising this issue! This is the best comment I’ve gotten about this paper either here or on Azimuth.

I’ll need to figure out what we’re doing wrong. In electrical engineering, the impedances of passive linear circuit elements are precisely the positive-real functions: rational functions of a complex variable that 1) have a positive real part and are analytic in the right halfplane of the complex plane and 2) take on real values on the real axis.

I see a number of problems now:

a) Positive-real functions are not closed under multiplication.

b) This definition doesn’t quite match what we wrote in our paper: we didn’t say anything about being analytic on the right halfplane.

c) Also, we talk about rational functions with real coefficients.

To deal with c), it would suffice to prove that a rational function of a complex variable

f(z)=a nz n++a 0b mz m++b 0 f(z) = \frac{a_n z^n + \cdots + a_0}{b_m z^m + \cdots + b_0}

that takes real values on the positive real axis can be written in such a way that all the coefficents a i,b ia_i, b_i are real. We can start by noting that ff has a Taylor series with all real coefficients. But then what?

As far as a) is concerned, I suspect that we don’t really use the closure under multiplication. I’ll have to go through the paper and check this.

And as far as b) is concerned, we should just add that condition.

Posted by: John Baez on January 1, 2016 5:03 PM | Permalink | Reply to this

Re: A Compositional Framework for Passive Linear Networks

Actually, as far as b) is concerned, we don’t need to add a condition, since a meromorphic function that takes only positive values in the right halfplane can’t have any poles in the right halfplane.

(If zz goes around a pole, f(z)f(z) traces out a loop with nonzero winding number around the origin, thanks to the residue formula.)

Posted by: John Baez on January 1, 2016 5:30 PM | Permalink | Reply to this

Re: A Compositional Framework for Passive Linear Networks

Have you heard about port-hamiltonian systems ? it is a field which studies exactly the systems you mentioned (passive, connected..) ..might be worth a look to see connections with your work

Posted by: aas on March 19, 2016 1:37 PM | Permalink | Reply to this

Post a New Comment