betaFeedback

WorksEngineering

Simulating Nonlinear Resistive Networks using a Behavioral Splitting

Abstract

An operator splitting method is developed for computing operating points of nonlinear resistive networks. Our behavioral formulation separates the device laws from Kirchhoff's laws and casts simulation as a zero-finding problem. Branch port resistances then provide a diagonal preconditioner for the relaxed Peaceman-Rachford iteration in scattering variables. Each iteration requires solving independent scalar equations and a linear system with a fixed weighted Laplacian matrix. Convergence is established for maximal monotone device laws when an operating point exists. Contractive branch reflections also yield a linear convergence bound independent of network topology. Numerical experiments on crossbar arrays illustrate the computational advantages.

Introduction

Analog computing has attracted renewed interest as a route to faster and more energy-efficient artificial intelligence [1, 2, 3, 4]. Resistive crossbar arrays, for example, implement matrix-vector multiplication through Ohm’s law and Kirchhoff’s current law, computing where the data are stored and thereby reducing data movement [2], [3], [5]. Related circuit architectures also support analog learning [6], [7] and neuromorphic control [8, 9, 10]. However, device variability, line resistances, and unwanted current paths limit the accuracy of analog computation [11]. Accurate simulation of large-scale nonlinear resistive networks is therefore essential for circuit design.

General-purpose circuit simulators, such as SPICE [12], compute operating points by damped Newton iteration on the modified nodal analysis equations [13], [14]. The device characteristics are linearized at the current iterate, and the resulting sparse Jacobian is factorized anew at each iteration. For large circuits, these repeated factorizations account for a substantial part of the computational cost [15], even though the topology is fixed and nonlinearities are local to each device. This motivates an algorithm that reuses interconnection computations while updating the nonlinear devices independently.

The paper develops a zero-finding formulation for computing operating points of nonlinear resistive networks and establishes its equivalence to a partial inverse problem [16]. The formulation starts from the behavioral approach to systems theory [17], separating device laws from the constraints imposed by Kirchhoff’s laws. The device laws define a possibly nonlinear, but separable product of branch behaviors, while Kirchhoff’s laws define a linear subspace determined by the circuit topology. Their intersection is the circuit behavior, whose elements are the operating points. This separation allows a splitting method to exploit both the local nature of the nonlinearities and the fixed linear structure of the interconnection.

The main contribution is a circuit simulation algorithm obtained by leveraging the relaxed Peaceman–Rachford iteration [18]. The iteration is expressed in scattering variables, with branch port resistances providing a diagonal preconditioner. Each iteration requires solving independent scalar equations and a linear system with a fixed weighted Laplacian matrix, whose factorization can be reused. Suitable choices of the relaxation parameter recover the Peaceman–Rachford and Douglas–Rachford iterations [19], [20]. The latter also coincides with a preconditioned form of Spingarn’s method of partial inverses [16], [21]. This identification uses the orthogonality of admissible branch voltage and current spaces offered by Tellegen’s theorem [22], [23]. Convergence to an operating point, whenever one exists, is established for maximal monotone device laws using standard monotone operator theory [18], [20], [24]. A linear convergence bound independent of network topology is also derived under the assumption that every branch reflected resolvent is contractive.

Related work. The problem of computing operating points of nonlinear resistive networks dates back to [25], and its formulation in terms of monotone relations is developed in [26]. More recent operator approaches include maximal monotone one-ports [8], a monotone plus skew formulation solved by primal-dual splitting, with a skew interconnection and step sizes constrained by the incidence matrix norm [27], operator classes beyond monotonicity [28], and fixed and variable metric splittings for neuromorphic circuits [9], [10]. A fast simulation method for nonlinear resistive networks in analog learning is proposed in [6]. Operator splitting over system behaviors for control is studied in [29] and for dynamic optimization in [30]. The contraction factor and optimal metric for the reflected resolvent of a strongly monotone and Lipschitz map are derived in [31]. The variables and the interconnection step of Section IV coincide with the scattering variables and adaptor of wave digital filter theory [32], [33], whose fixed point iterations with several nonlinearities have been recently studied in [34].

Paper organization. The paper is organized as follows. Section II reviews monotone maps and the relaxed Peaceman–Rachford iteration. Section III models resistive circuits in behavioral terms and defines the circuit simulation problem. Section IV derives the circuit simulation algorithm and analyzes its convergence. § 3 presents a simulation case study of a crossbar array. Section VI concludes the paper.

Preliminaries

We assume familiarity with monotone operator theory [24].

The notation largely follows [35], with the standard identification between set-valued maps and their graphs. Given an inner product ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle on Rn\mathbb{R}^{n}, with corresponding induced norm ∥⋅∥\lVert\cdot\rVert, a (set-valued) map T:Rn⇉RnT:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n} is monotone if

⟨u−u′,y−y′⟩≥0for all (u,y),(u′,y′)∈graph⁡T,\langle u-u^{\prime},y-y^{\prime}\rangle\geq0\quad\text{for all }(u,y),(u^{\prime},y^{\prime})\in\operatorname{graph}T,

and maximal monotone if graph TT is not properly contained in the graph of a monotone map [24, 35]. A continuous, single-valued, monotone map TT on Rn\mathbb{R}^{n} is maximal monotone [24]. The resolvent and the reflected resolvent of a map TT are

JT=(I+T)−1,CT=2JT−I,J_{T}=(I+T)^{-1},\qquad C_{T}=2J_{T}-I,

where II is the identity map. By Minty’s theorem [24], a monotone map TT is maximal monotone if and only if dom⁡JT=Rn\operatorname{dom}J_{T}=\mathbb{R}^{n}, in which case JTJ_{T} is both single-valued and firmly nonexpansive, and CTC_{T} is nonexpansive [24, 35]. For a nonempty, closed, convex set C⊆RnC\subseteq\mathbb{R}^{n}, the projection onto CC is the map PC:Rn→CP_{C}:\mathbb{R}^{n}\to C defined by u↦arg⁡min⁡y∈C ∥u−y∥u\mapsto\underset{y\in C}{\arg\min}\,\lVert u-y\rVert, and the normal cone of CC is the map NC:Rn⇉RnN_{C}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n} defined by

NC(u)={{y∣⟨y,z−u⟩≤0 for all z∈C},u∈C,∅,u∉C.N_{C}(u)=\begin{cases}\{y\mid\langle y,z-u\rangle\leq0\text{ for all }z\in C\},&u\in C,\\ \varnothing,&u\notin C.\end{cases}

The map NCN_{C} is maximal monotone and JNC=PCJ_{N_{C}}=P_{C} [24]. If VV is a subspace of Rn\mathbb{R}^{n}, then NV(u)=V⊥N_{V}(u)=V^{\perp} for every u∈Vu\in V, PVP_{V} is the orthogonal projection onto VV, and CNV=2PV−IC_{N_{V}}=2P_{V}-I is the reflection across VV. A product T1×⋯×TmT_{1}\times\cdots\times T_{m} of maps with nonempty graphs is maximal monotone if and only if T1,…,TmT_{1},\ldots,T_{m} are maximal monotone [24].

Consider maximal monotone maps F,GF,G on Rn\mathbb{R}^{n} and the zero-finding problem of determining u⋆∈zer⁡(F+G)u^{\star}\in\operatorname{zer}(F+G), that is, a solution of the inclusion

0∈F(u)+G(u).(1)0\in F(u)+G(u). \tag*{(1)}

A widely used algorithm to solve (1) is the relaxed Peaceman–Rachford (PR) iteration [18]

ak+1=(1−α)ak+αCF(CG(ak)),k∈Z+,(2)a^{k+1}=(1-\alpha)a^{k}+\alpha C_{F}(C_{G}(a^{k})),\qquad k\in\mathbb{Z}_{+}, \tag*{(2)}

with α∈(0,1]\alpha\in(0,1] the relaxation parameter and a0∈Rna^{0}\in\mathbb{R}^{n} the initial condition. For α=12\alpha=\frac{1}{2}, (2) is the Douglas–Rachford (DR) iteration, and for α=1\alpha=1, it is the PR iteration [19]. The zeros of F+GF+G and the fixed points of CFCGC_{F}C_{G} are related by [24]

zer⁡(F+G)=JG(fix⁡CFCG).(3)\operatorname{zer}(F+G)=J_{G}(\operatorname{fix}C_{F}C_{G}). \tag*{(3)}

The following convergence result is classical [18, 20, 24].

Theorem 1 (Convergence of the relaxed PR iteration). Consider maximal monotone maps F,GF,G on Rn\mathbb{R}^{n}, α∈(0,1)\alpha\in(0,1) and a0∈Rna^{0}\in\mathbb{R}^{n}. Assume zer⁡(F+G)≠∅\operatorname{zer}(F+G)\neq\varnothing. Then the sequence {ak}k∈Z+\{a^{k}\}_{k\in\mathbb{Z}_{+}} generated by (2) converges to a point a⋆∈fix⁡CFCGa^{\star}\in\operatorname{fix}C_{F}C_{G}, and {JG(ak)}k∈Z+\{J_{G}(a^{k})\}_{k\in\mathbb{Z}_{+}} converges to JG(a⋆)∈zer⁡(F+G)J_{G}(a^{\star})\in\operatorname{zer}(F+G).

For α=1\alpha=1, the iteration need not converge [24]. However, for every α∈(0,1]\alpha\in(0,1], (2) converges linearly whenever CFC_{F} is nonexpansive and CGC_{G} is a contraction, by Banach’s fixed point theorem [24], since (1−α)I+αCFCG(1-\alpha)I+\alpha C_{F}C_{G} is then a contraction.

Problem formulation

Circuit topology and interconnection constraints

The topology of a resistive network is naturally described by a connected, directed multigraph G=(V0,E)\mathbb{G}=(\mathbb{V}_{0},\mathbb{E}), with node (or vertex) set V0={0,1,…,n}\mathbb{V}_{0}=\{0,1,\ldots,n\} and branch (or edge) set E={1,…,m}\mathbb{E}=\{1,\ldots,m\}, in which parallel edges are allowed [36, 37]. Every two-terminal device of the circuit, including every source, is associated with a branch e∈Ee\in\mathbb{E} and the ground node is taken to be 0∈V00\in\mathbb{V}_{0}, so that V={1,…,n}\mathbb{V}=\{1,\ldots,n\} is the set of remaining nodes. An orientation of the branches is fixed a priori. Each branch e∈Ee\in\mathbb{E} is associated with a voltage ve∈Rv_{e}\in\mathbb{R} and a current ie∈Ri_{e}\in\mathbb{R}, with reference polarity and reference direction in accordance with the orientation of the branch [38]. The vectors v,i∈Rmv,i\in\mathbb{R}^{m} collect all branch voltages and the branch currents. Grounding the reference node and deleting the corresponding row of the incidence matrix of G\mathbb{G} yields the reduced incidence matrix A∈Rn×mA\in\mathbb{R}^{n\times m}, with entries Ake=1A_{ke}=1 if branch ee is oriented away from node kk, Ake=−1A_{ke}=-1 if branch ee is oriented towards node kk, and Ake=0A_{ke}=0 otherwise, for all k∈Vk\in\mathbb{V} and e∈Ee\in\mathbb{E}. The matrix AA has full row rank because G\mathbb{G} is connected [36 Ch. 2], [37], [38, Ch. 4]. Denoting by ϕ∈Rn\phi\in\mathbb{R}^{n} the vector of potentials of the nodes in V\mathbb{V}, Kirchhoff’s voltage law and Kirchhoff’s current law read [38 Ch. 4]

v=ATϕ,Ai=0.v=A^{\mathsf{T}}\phi,\qquad Ai=0.

Admissible voltages and currents thus define the subspaces

V=ran⁡AT,I=ker⁡A,(4)\mathbb{V}=\operatorname{ran}A^{\mathsf{T}},\qquad\mathbb{I}=\ker A, \tag*{(4)}

which, in the language of graph theory, are the cut space and the cycle space of G\mathbb{G} [36 Ch. 2]. Note that I=V⊥\mathbb{I}=\mathbb{V}^{\perp}, since ker⁡A\ker A is the orthogonal complement of ran⁡AT\operatorname{ran}A^{\mathsf{T}}. Equivalently, vTi=0v^{\mathsf{T}}i=0 for all v∈Vv\in\mathbb{V} and i∈Ii\in\mathbb{I}, a fact known as Tellegen’s theorem [22], [23, Ch. 2]. Since AA has full row rank, the node potentials are recovered from v∈Vv\in\mathbb{V} as ϕ=(AAT)−1Av\phi=(AA^{\mathsf{T}})^{-1}Av.

Circuit behavior and constitutive relations

The circuit is modeled using the behavioral approach [17], with each device described by its set of admissible voltage-current pairs. The behavior of branch e∈Ee\in\mathbb{E} is a nonempty, closed set Be⊆R2B_{e}\subseteq\mathbb{R}^{2} of admissible voltage-current pairs (ve,ie)(v_{e},i_{e}), and the branch relation of branch ee is the set-valued map Te:R⇉RT_{e}:\mathbb{R}\rightrightarrows\mathbb{R} with graph BeB_{e}, that is,

ie∈Te(ve)if and only if(ve,ie)∈Be.(5)i_{e}\in T_{e}(v_{e})\quad\text{if and only if}\quad(v_{e},i_{e})\in B_{e}. \tag*{(5)}

By convention, current is taken as the dependent variable in (5). The devices considered in this paper are possibly nonlinear resistive elements, as well as constant voltage and current sources. Table 1 lists representative devices, the corresponding symbols used in circuit diagrams, their parameters, and their behaviors, each given as the set of admissible voltage-current pairs (ve,ie)(v_{e},i_{e}) that satisfy the listed relation.

Behavioral systems theory models interconnection through variable sharing [17]. The device behavior of the circuit is B=B1×⋯×BmB=B_{1}\times\cdots\times B_{m}, the set of pairs (v,i)∈Rm×Rm(v,i)\in\mathbb{R}^{m}\times\mathbb{R}^{m} with (ve,ie)∈Be(v_{e},i_{e})\in B_{e} for every e∈Ee\in\mathbb{E}, and the *branch relation of the circuit is T=T1×⋯×TmT = T_1 \times\cdots\times T_m, so that i∈T(v)i \in T(v) if and only if (v,i)∈B(v,i) \in B. The branches share their voltages and their currents through Kirchhoff’s laws (4), so that the circuit behavior is

C=B∩(V×I).(6)C = B \cap(V \times I). \tag*{(6)}

The elements of CC are the operating points of the circuit. The description (6) of the operating points is a behavioral counterpart of the sparse tableau formulation of circuit analysis [39], [38 Ch. 5], in which the device laws and Kirchhoff’s laws are kept as separate sets of equations.

Circuit simulation

The circuit simulation problem is to find an operating point (v,i)∈C(v,i) \in C. Such a point need not exist or be unique. For example, two ideal voltage sources connected in parallel have no operating point if their voltages differ and infinitely many if they agree. Classical conditions for existence and uniqueness in monotone resistive networks are given in [25].

The circuit model (6) does not require monotone branch relations. Section IV develops an algorithm for computing an operating point. The resulting iteration is well defined for arbitrary initialization when each branch resolvent is single-valued and everywhere defined. Maximal monotonicity of the branch relations guarantees such properties and, with suitable parameters, convergence to an operating point when one exists.

Example 1 (Positive shunt diode clipper). Consider the positive shunt diode clipper illustrated in Figure 1, in which a voltage source vˉ\bar{v} drives the load R2>0R_2 > 0 through a current-limiting resistor R1>0R_1 > 0. An ideal diode D connected in parallel with the load “clips” positive output voltages at zero. The circuit has n=2n = 2 nodes besides the ground node and m=4m = 4 branches, and its reduced incidence matrix is

Figure 1. Positive shunt diode clipper.

A=[11000−111],A = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 1 \end{bmatrix},

so that the subspaces (4) are

V={v∈R4∣v1=v2+v3, v3=v4},(7)V = \{v \in\mathbb{R}^{4} \mid v_1 = v_2 + v_3,\ v_3 = v_4\}, \tag*{(7)}
I={i∈R4∣i1+i2=0, i2=i3+i4},(8)I = \{i \in\mathbb{R}^{4} \mid i_1 + i_2 = 0,\ i_2 = i_3 + i_4\}, \tag*{(8)}

which express Kirchhoff’s voltage law around the two loops and Kirchhoff’s current law at the two nodes. By Table I, the device behavior BB is the set of pairs (v,i)∈R4×R4(v,i) \in\mathbb{R}^{4} \times\mathbb{R}^{4} with

DeviceSymbolParametersBehavior
resistorR\mathrm{R}R>0R > 0ve=Riev_e = Ri_e
voltage sourcevˉ\bar{v}vˉ∈R\bar{v} \in\mathbb{R}ve=vˉv_e = \bar{v}
current sourceıˉ\bar{\imath}ıˉ∈R\bar{\imath} \in\mathbb{R}ie=ıˉi_e = \bar{\imath}
ideal diodeve≤0≤ie, veie=0v_e \le0 \le i_e,\ v_ei_e = 0
Shockley diodeIs,VT>0I_s, V_T > 0ie=Is(eve/VT−1)i_e = I_s(e^{v_e/V_T} - 1)
nonlinear resistorg:R→Rg : \mathbb{R} \to\mathbb{R}ie=g(ve)i_e = g(v_e)

Table I. Device symbols, parameters and behaviors.

v1=vˉ,v2=R1i2,v3≤0≤i3,v3i3=0,v4=R2i4,(9)v_1 = \bar{v},\quad v_2 = R_1i_2,\quad v_3 \le0 \le i_3,\quad v_3i_3 = 0,\quad v_4 = R_2i_4, \tag*{(9)}

and the circuit behavior (6) is the set of pairs (v,i)(v,i) that satisfy (7) and (8). For vˉ≤0\bar{v} \le0, the diode does not conduct and the resistors form a voltage divider. For vˉ>0\bar{v} > 0, the diode conducts, so that v3=v4=0v_3 = v_4 = 0 and i3=vˉR1i_3 = \frac{\bar{v}}{R_1}. For every vˉ∈R\bar{v} \in\mathbb{R}, the circuit behavior is therefore a singleton. The output voltage across the load R2R_2 is

v3=v4=min⁡{R2R1+R2vˉ,0},(10)v_3 = v_4 = \min\left\{\frac{R_2}{R_1 + R_2}\bar{v}, 0\right\}, \tag*{(10)}

and v2=vˉ−v3v_2 = \bar{v} - v_3, i2=−i1=v2R1i_2 = -i_1 = \frac{v_2}{R_1}, i4=v3R2i_4 = \frac{v_3}{R_2}, i3=i2−i4i_3 = i_2 - i_4.

Main results

Circuit simulation as a zero-finding problem

Our modeling assumptions provide a natural separation between the device laws and the interconnection constraints. Circuit simulation thus amounts to finding a zero of the sum of the branch relation TT and the normal cone NVN_V, that is,

0∈NV(v)+T(v).(11)0 \in N_V(v) + T(v). \tag*{(11)}

The following result proves this equivalence and characterizes the operating points of the circuit in terms of solutions of (10).

Proposition 2 (Operating points as zeros). Consider the circuit behavior (6) and let TT be its branch relation. Then

zer⁡(NV+T)=dom⁡C,(12)\operatorname{zer}(N_V + T) = \operatorname{dom} C, \tag*{(12)}

where CC is regarded as a set-valued map with the current as the dependent variable, as in (5). Moreover, (v,i)∈C(v,i) \in C if and only if v∈zer⁡(NV+T)v \in\operatorname{zer}(N_V + T) and i∈T(v)∩Ii \in T(v) \cap I.

Proof. By (4), V⊥=IV^\perp= I, so NV(v)=IN_V(v) = I on VV and NV(v)=∅N_V(v) = \varnothing elsewhere. Since II is a subspace, (10) holds if and only if v∈Vv \in V and T(v)∩I≠∅T(v) \cap I \ne\varnothing. By definition of TT and CC, this is equivalent to v∈dom⁡Cv \in\operatorname{dom} C, proving (11). For v∈dom⁡Cv \in\operatorname{dom} C, (v,i)∈C(v,i) \in C if and only if i∈T(v)∩Ii \in T(v) \cap I, which proves the remaining claim. □

Proposition 2 shows that circuit simulation amounts to finding v∈Vv \in V and i∈V⊥i \in V^\perp such that i∈T(v)i \in T(v), which is Spingarn’s classical partial inverse problem for the pair (T,V)(T,V) [16]. The inclusion (10) has the form (1), with F=NVF = N_V and G=TG = T representing the interconnection structure and the branch laws, respectively. Our circuit simulation algorithm is obtained by applying the relaxed PR iteration (2) to a preconditioned inclusion equivalent to (11), as discussed next.

Preconditioning by port resistances

We introduce branch port resistances to precondition (11) and tune the corresponding convergence rate. Let γe>0\gamma_e > 0 be the port resistance assigned to branch e∈Ee \in\mathbb{E}, and let Γ=diag⁡(γ1,…,γm)\Gamma= \operatorname{diag}(\gamma_1,\ldots,\gamma_m). The associated inner product and induced norm on Rm\mathbb{R}^m are

⟨x,y⟩Γ=xTΓ−1y,∥x∥Γ=xTΓ−1x.(13)\langle x,y\rangle_{\Gamma}=x^{\mathsf{T}}\Gamma^{-1}y,\qquad\lVert x\rVert_{\Gamma}=\sqrt{x^{\mathsf{T}}\Gamma^{-1}x}. \tag*{(13)}

By Tellegen’s theorem, ΓI\Gamma\mathcal{I} is the orthogonal complement of V\mathcal{V} in the inner product (13). Thus every a∈Rma \in\mathbb{R}^m decomposes uniquely as a=v+Γia=v+\Gamma i, with v∈Vv\in\mathcal{V} and i∈Ii\in\mathcal{I}. Moreover, since Γ\Gamma is invertible, (11) is equivalent to the inclusion

0∈NΓ(v)+TΓ(v).(14)0 \in N_{\Gamma}(v)+T_{\Gamma}(v). \tag*{(14)}

where NΓ=ΓNVN_{\Gamma}=\Gamma N_{\mathcal{V}} and TΓ=ΓTT_{\Gamma}=\Gamma T.

Our circuit simulation algorithm is obtained by applying the relaxed PR iteration (2) to the scaled inclusion (14), giving

bk=CTΓ(ak),(15)b^k=C_{T_{\Gamma}}(a^k), \tag*{(15)}
ak+1=(1−α)ak+αCNΓ(bk),(16)a^{k+1}=(1-\alpha)a^k+\alpha C_{N_{\Gamma}}(b^k), \tag*{(16)}

with k∈Z+k\in\mathbb{Z}_+ and a0∈Rma^0\in\mathbb{R}^m. The voltages and the currents are determined by aka^k and bkb^k as

vk=12(ak+bk),(17)v^k=\frac{1}{2}(a^k+b^k), \tag*{(17)}
ik=12Γ−1(ak−bk),(18)i^k=\frac{1}{2}\Gamma^{-1}(a^k-b^k), \tag*{(18)}

so that vk=JTΓ(ak)v^k=J_{T_{\Gamma}}(a^k), ik=Γ−1(ak−vk)∈T(vk)i^k=\Gamma^{-1}(a^k-v^k)\in T(v^k) and (vk,ik)∈B(v^k,i^k)\in\mathcal{B} for every k∈Z+k\in\mathbb{Z}_+. The iteration acts on aka^k and bkb^k rather than on (vk,ik)(v^k,i^k), since JTΓJ_{T_{\Gamma}} is single-valued even when the branch relations are not (e.g., for sources and ideal diodes).

Remark 1 (Scattering and passivity interpretation). The variables a=v+Γia=v+\Gamma i and b=v−Γib=v-\Gamma i have a classical interpretation in terms of scattering [32], [40] and passivity theory [41], [42]. They represent the incident and the reflected waves at the ports of the interconnection, with γe\gamma_e the reference resistance of port ee, and the Lipschitz constant of the map ae↦bea_e\mapsto b_e is the reflection coefficient of branch ee. The identity ae2−be2=4γeveiea_e^2-b_e^2=4\gamma_e v_ei_e relates the wave amplitudes to the power absorbed by branch e∈Ee\in\mathbb{E}. In the norm (13), the corresponding identity is

∥a∥Γ2−∥b∥Γ2=4vTi.\lVert a\rVert_{\Gamma}^2-\lVert b\rVert_{\Gamma}^2=4v^{\mathsf{T}}i.

This identity is the scattering form of passivity [41], [42], so that a branch absorbs power if and only if the amplitude of its reflected wave is not larger than that of its incident wave.

Resolvents of the scaled maps

Evaluating the scaled resolvents requires computing a weighted projection for the interconnection and solving independent scalar equations for the devices. Let

PV=AT(AΓ−1AT)−1AΓ−1(19)P_{\mathcal{V}}=A^{\mathsf{T}}(A\Gamma^{-1}A^{\mathsf{T}})^{-1}A\Gamma^{-1} \tag*{(19)}

denote the orthogonal projection onto V=ran⁡AT\mathcal{V}=\operatorname{ran}A^{\mathsf{T}} in the inner product (13) [43]. The following lemma characterizes the resolvents and maximal monotonicity properties of the scaled maps NΓN_{\Gamma} and TΓT_{\Gamma}.

Lemma 3 (Resolvents of NΓN_{\Gamma} and TΓT_{\Gamma}). Consider the circuit behavior (6) and port resistances γe>0\gamma_e>0, with e∈Ee\in\mathbb{E}, and equip Rm\mathbb{R}^m with the inner product and the induced norm (13). Then the following statements hold.

(i) NΓN_{\Gamma} coincides with the normal cone map of V\mathcal{V}. Hence, NΓN_{\Gamma} is maximal monotone, JNΓ=PVJ_{N_{\Gamma}}=P_{\mathcal{V}} and CNΓ=2PV−IC_{N_{\Gamma}}=2P_{\mathcal{V}}-I.

(ii) TΓT_{\Gamma} is maximal monotone if and only if TT is maximal monotone, and its resolvent is

JTΓ(a)=(Jγ1T1(a1),…,JγmTm(am)),(20)J_{T_{\Gamma}}(a)=\left(J_{\gamma_1T_1}(a_1),\ldots,J_{\gamma_mT_m}(a_m)\right), \tag*{(20)}

where JγeTe=(I+γeTe)−1J_{\gamma_eT_e}=(I+\gamma_eT_e)^{-1} is the resolvent of γeTe\gamma_eT_e.

Proof. (i) Since ⟨z,v⟩Γ=(Γ−1z)Tv\langle z,v\rangle_{\Gamma}=(\Gamma^{-1}z)^{\mathsf{T}}v, the orthogonal complement of V\mathcal{V} in (13) is I\mathcal{I}. Thus NΓN_{\Gamma} is the normal cone of V\mathcal{V} in this inner product. The remaining claims follow from Section II and (19).

(ii) The identity ⟨u−u′,Γ(y−y′)⟩Γ=(u−u′)T(y−y′)\langle u-u',\Gamma(y-y')\rangle_{\Gamma}=(u-u')^{\mathsf{T}}(y-y') shows that the bijection (u,y)↦(u,Γy)(u,y)\mapsto(u,\Gamma y) preserves monotonicity in the respective inner products and graph inclusions, hence maximal monotonicity. Finally, TΓ=(γ1T1)×⋯×(γmTm)T_{\Gamma}=(\gamma_1T_1)\times\cdots\times(\gamma_mT_m), so (20) follows from the definition of the resolvent.

Lemma 3 establishes that the scaled maps NΓN_{\Gamma} and TΓT_{\Gamma} satisfy the maximal monotonicity assumptions of the relaxed PR iteration whenever the branch relations are maximal monotone. The resolvent formulas then suggest a circuit implementation of the iteration, with independent scalar branch solves for the devices and a weighted projection for the interconnection.

Remark 2 (Isometry of CNΓC_{N_{\Gamma}}). The interconnection reflection CNΓC_{N_{\Gamma}} has a useful property for convergence analysis. The projection PVP_{\mathcal{V}} is self-adjoint and idempotent in the inner product (13), so CNΓ=2PV−IC_{N_{\Gamma}}=2P_{\mathcal{V}}-I is self-adjoint with CNΓ2=IC_{N_{\Gamma}}^2=I. Hence

∥CNΓx∥Γ2=⟨x,CNΓ2x⟩Γ=∥x∥Γ2\lVert C_{N_{\Gamma}}x\rVert_{\Gamma}^2=\langle x,C_{N_{\Gamma}}^2x\rangle_{\Gamma}=\lVert x\rVert_{\Gamma}^2

for every x∈Rmx\in\mathbb{R}^m. Thus CNΓC_{N_{\Gamma}} is an isometry and, in particular, nonexpansive. Composition with CNΓC_{N_{\Gamma}} preserves any nonexpansiveness or contraction bound for CTΓC_{T_{\Gamma}}, allowing convergence analysis to use bounds derived from the individual branch relations. For example, a maximal monotone map TΓT_{\Gamma} has a contractive reflected resolvent CTΓC_{T_{\Gamma}} if and only if both TΓT_{\Gamma} and TΓ−1T_{\Gamma}^{-1} are strongly monotone [44 Cor. 4.7], in which case (14) converges globally and linearly for every α∈(0,1]\alpha\in(0,1].

Circuit simulation algorithm

The resolvent formulas yield an efficient implementation of (14). By Lemma 3, the auxiliary variable bkb^k may be computed one branch at a time, as bek=2JγeTe(aek)−aekb_e^k=2J_{\gamma_eT_e}(a_e^k)-a_e^k. By (19), (16) requires PV(bk)=ATϕkP_{\mathcal{V}}(b^k)=A^{\mathsf{T}}\phi^k, where ϕk∈Rn\phi^k\in\mathbb{R}^n solves the linear system

AΓ−1ATϕk=AΓ−1bk.(21)A\Gamma^{-1}A^{\mathsf{T}}\phi^k=A\Gamma^{-1}b^k. \tag*{(21)}

The resulting procedure is summarized in Algorithm 1.

Algorithm 1 Behavioral circuit simulation

Input: reduced incidence matrix A∈Rn×mA \in\mathbb{R}^{n \times m}, branch relations Te:R⇒RT_e : \mathbb{R} \Rightarrow\mathbb{R} and port resistances γe>0\gamma_e > 0 for e∈Ee \in\mathbb{E}, relaxation parameter α∈(0,1]\alpha\in(0,1], initial condition a0∈Rma^0 \in\mathbb{R}^m.

  1. for k=0,1,…k = 0,1,\ldots do

  2. bek=2JγeTe(aek)−aekb_e^k = 2J_{\gamma_e T_e}(a_e^k)-a_e^k for every e∈Ee \in\mathbb{E}

  3. solve AΓ−1A⊤ϕk=AΓ−1bkA\Gamma^{-1}A^\top\phi^k = A\Gamma^{-1}b^k for ϕk∈Rn\phi^k \in\mathbb{R}^n

  4. ak+1=(1−α)ak+α(2A⊤ϕk−bk)a^{k+1} = (1-\alpha)a^k+\alpha(2A^\top\phi^k-b^k)

  5. end for

Output: sequences {ak}k∈Z+\{a^k\}_{k\in\mathbb{Z}_+} and {bk}k∈Z+\{b^k\}_{k\in\mathbb{Z}_+}.

Algorithm 1 is the relaxed PR iteration (2) for the pair (NΓ,TΓ)(N_\Gamma,T_\Gamma) in the inner product (12). For α=12\alpha=\frac{1}{2} and γe=1\gamma_e=1 for every e∈Ee\in\mathbb{E}, it reduces to Spingarn’s method of partial inverses for the pair (T,V)(T,V) [16], an identification due to [20 §5], and for general port resistances it is a scaled version of the method studied in [21]. By (3) and Proposition 2, JTΓJ_{T_\Gamma} maps fixed points of CNΓCTΓC_{N_\Gamma}C_{T_\Gamma} onto voltages of operating points. The voltages and currents vkv^k and iki^k are recovered from aka^k and bkb^k using (15).

Remark 3 (Computational aspects). The matrix L=AΓ−1A⊤L=A\Gamma^{-1}A^\top in (18) is the Laplacian matrix of G\mathcal{G} weighted by the port conductances {γe−1}e∈E\{\gamma_e^{-1}\}_{e\in\mathbb{E}} [37], with the row and column of the ground node removed. It is symmetric and positive definite, since G\mathcal{G} is connected and AA has full row rank. A sparse Cholesky factorization L=KK⊤L=KK^\top with a fill-reducing ordering can be computed once, before the iterations [43 Ch. 11], so each network solve reduces to two sparse triangular solves. For large graphs, approximate Cholesky factorizations yield solvers for (18) with nearly linear expected running time in mm for a fixed relative accuracy [45]. The factorization depends only on the topology and the port resistances, so it is reused across iterations and across simulations of the same network with different source values. Since every iterate satisfies the branch relations, the iteration is stopped when the residuals ∥Aik∥\lVert Ai^k\rVert and ∥vk−PVvk∥\lVert v^k-P_Vv^k\rVert of Kirchhoff’s laws fall below a given tolerance. Finally, the evaluation of (14a) through (17), the update (14b) once ϕk\phi^k is known, and the readouts (15) are embarrassingly parallel over the branches [35 Ch. 4].

Convergence analysis

The convergence of Algorithm 1 follows from Theorem 1 applied to the pair (NΓ,TΓ)(N_\Gamma,T_\Gamma), with rates determined by the branches alone. For every branch e∈Ee\in\mathbb{E} with maximal monotone branch relation TeT_e, let ρe≥0\rho_e\geq0 be the Lipschitz constant of CγeTeC_{\gamma_eT_e}, which is at most one by Section II and is referred to as the reflection coefficient of branch ee, and let ρˉ=max⁡e∈Eρe\bar{\rho}=\max_{e\in\mathbb{E}}\rho_e.

Theorem 4 (Convergence of Algorithm 1). Consider the circuit behavior (6), port resistances γe>0\gamma_e>0 for e∈Ee\in\mathbb{E}, and the sequences generated by Algorithm 1 from a0∈Rma^0\in\mathbb{R}^m. Assume that TeT_e is maximal monotone for every e∈Ee\in\mathbb{E}. Then all sequences are well defined, and the following statements hold.

(i) If C≠∅C\neq\varnothing and α∈(0,1)\alpha\in(0,1), then {ak}k∈Z+\{a^k\}_{k\in\mathbb{Z}_+} converges to a point a∗∈fix⁡CNΓCTΓa^*\in\operatorname{fix}C_{N_\Gamma}C_{T_\Gamma}, and {(vk,ik)}k∈Z+\{(v^k,i^k)\}_{k\in\mathbb{Z}_+} converges to an operating point (v∗,i∗)∈C(v^*,i^*)\in C, with a∗=v∗+Γi∗a^*=v^*+\Gamma i^*.

(ii) If ρˉ<1\bar{\rho}<1, then CC is a singleton {(v∗,i∗)}\{(v^*,i^*)\}, the point a∗=v∗+Γi∗a^*=v^*+\Gamma i^* is the unique fixed point of CNΓCTΓC_{N_\Gamma}C_{T_\Gamma}, and for every α∈(0,1]\alpha\in(0,1] and k∈Z+k\in\mathbb{Z}_+,

∥ak+1−a∗∥Γ≤(1−α+αρˉ)∥ak−a∗∥Γ,(22)\lVert a^{k+1}-a^*\rVert_\Gamma\leq(1-\alpha+\alpha\bar{\rho})\lVert a^k-a^*\rVert_\Gamma, \tag*{(22)}
∥vk−v∗∥Γ≤∥ak−a∗∥Γ,(23)\lVert v^k-v^*\rVert_\Gamma\leq\lVert a^k-a^*\rVert_\Gamma, \tag*{(23)}
∥Γ(ik−i∗)∥Γ≤∥ak−a∗∥Γ.(24)\lVert\Gamma(i^k-i^*)\rVert_\Gamma\leq\lVert a^k-a^*\rVert_\Gamma. \tag*{(24)}

Proof. By Lemma 3 and Minty’s theorem, all sequences are well defined. Define the map S:Rm→Rm×RmS:\mathbb{R}^m\to\mathbb{R}^m\times\mathbb{R}^m by

S(a)=(JTΓ(a),Γ−1(a−JTΓ(a))).S(a)=\left(J_{T_\Gamma}(a),\Gamma^{-1}\left(a-J_{T_\Gamma}(a)\right)\right).

For (v,i)=S(a)(v,i)=S(a), we have i∈T(v)i\in T(v) and

CNΓCTΓ(a)=a⟺PV(v−Γi)=vC_{N_\Gamma}C_{T_\Gamma}(a)=a \Longleftrightarrow P_V(v-\Gamma i)=v
⟺v∈V,i∈I.\Longleftrightarrow v\in V,\quad i\in I.

Thus SS restricts to a bijection from fix⁡CNΓCTΓ\operatorname{fix}C_{N_\Gamma}C_{T_\Gamma} onto CC, with inverse (v,i)↦v+Γi(v,i)\mapsto v+\Gamma i.

(i) Since zer⁡(NΓ+TΓ)=zer⁡(NV+T)=dom⁡C≠∅\operatorname{zer}(N_\Gamma+T_\Gamma)=\operatorname{zer}(N_V+T)=\operatorname{dom}C\neq\varnothing by Proposition 2, Theorem 1 gives ak→a∗∈fix⁡CNΓCTΓa^k\to a^*\in\operatorname{fix}C_{N_\Gamma}C_{T_\Gamma}. By continuity of SS, (vk,ik)=S(ak)→S(a∗)∈C(v^k,i^k)=S(a^k)\to S(a^*)\in C.

(ii) By (17) and the diagonal form of Γ\Gamma, CTΓC_{T_\Gamma} is ρˉ\bar{\rho}-Lipschitz in ∥⋅∥Γ\lVert\cdot\rVert_\Gamma. Since CNΓC_{N_\Gamma} is an isometry by Remark 2, CNΓCTΓC_{N_\Gamma}C_{T_\Gamma} has the same bound, and (1−α)I+αCNΓCTΓ(1-\alpha)I+\alpha C_{N_\Gamma}C_{T_\Gamma} is a contraction with constant 1−α+αρˉ<11-\alpha+\alpha\bar{\rho}<1. Banach’s fixed point theorem gives a unique fixed point a∗a^* and (19a). The bijection defined by SS then gives a unique operating point. Finally, JTΓJ_{T_\Gamma} and I−JTΓ=JTΓ−1I-J_{T_\Gamma}=J_{T_\Gamma}^{-1} are nonexpansive [24], which yields (19b) and (19c). □\square

Theorem 4 establishes convergence to an operating point whenever one exists and guarantees existence, uniqueness and linear convergence when every branch reflection is contractive. Part (i) covers every circuit with maximal monotone branches that has an operating point, including circuits with ideal sources and ideal diodes, and the residual ∥ak+1−ak∥Γ\lVert a^{k+1}-a^k\rVert_\Gamma then vanishes as o(1/k)o(1/\sqrt{k}) [18]. The restriction α<1\alpha<1 in (i) cannot be removed. A voltage source in parallel with a current source illustrates this limitation. The map CNΓCTΓC_{N_\Gamma}C_{T_\Gamma} acts as a nontrivial rotation about its unique fixed point a∗a^* in the inner product (12). Algorithm 1 with α=1\alpha=1 therefore preserves the distance to a∗a^* and fails to converge from any a0≠a∗a^0\neq a^*. Part (ii) requires every reflection coefficient to be smaller than one. It then gives existence and uniqueness of the operating point, and a rate that does not depend on the graph. The bound (19a) is smallest for α=1\alpha=1, where it equals ρˉ\bar{\rho}, so the PR iteration is the choice of reference when ρˉ<1\bar{\rho}<1, whereas α<1\alpha<1 is required when ρˉ=1\bar{\rho}=1. A theoretical characterization of how port resistances affect convergence if ρˉ=1\bar{\rho}=1 and α<1\alpha<1 is left for future work.

Computing reflection coefficients and branch resolvents

Algorithm 1 requires solving, for every branch e∈Ee\in\mathbb{E}, the scalar equation ae=ve+γeiea_e=v_e+\gamma_e i_e, with (ve,ie)∈Be(v_e,i_e)\in B_e, whose solution ve=JγeTe(ae)v_e=J_{\gamma_eT_e}(a_e) is unique by Minty’s theorem if TeT_e is maximal monotone. Table 2 reports the resolvents and the reflection coefficients of the devices of Table I. Each resolvent may be derived by checking that (ve,ie)∈Be(v_e,i_e)\in B_e, with ie=ae−veγei_e=\frac{a_e-v_e}{\gamma_e}, and each reflection coefficient follows from the resolvent by direct computation. For example, a resistor R>0R>0 has resolvent JγeTe(ae)=RaeR+γeJ_{\gamma_eT_e}(a_e)=\frac{Ra_e}{R+\gamma_e} and reflection coefficient ∣R−γe∣R+γe\frac{\lvert R-\gamma_e\rvert}{R+\gamma_e}. A resistor RR in series with a voltage source vˉ\bar{v}, with behavior ve=Rie+vˉv_e=Ri_e+\bar{v}, has resolvent JγeTe(ae)=Rae+γevˉR+γeJ_{\gamma_eT_e}(a_e)=\frac{Ra_e+\gamma_e\bar{v}}{R+\gamma_e} and the same reflection coefficient, since CγeTeC_{\gamma_eT_e} is affine with slope R−γeR+γe\frac{R-\gamma_e}{R+\gamma_e}. Choosing γe=R\gamma_e=R makes this coefficient zero and corresponds to impedance matching [32].

DeviceJγeTe(ae)J_{\gamma_e T_e}(a_e)ρe\rho_e
resistorRaeR+γe\frac{R a_e}{R+\gamma_e}∣R−γe∣R+γe\frac{\lvert R-\gamma_e\rvert}{R+\gamma_e}
voltage sourcevˉ\bar{v}11
current sourceae−γeıˉa_e-\gamma_e\bar{\imath}11
ideal diodemin⁡{ae,0}\min\{a_e,0\}11
Shockley diodehe−1(ae)h_e^{-1}(a_e), gg in (21)11
nonlinear resistorhe−1(ae)h_e^{-1}(a_e), heh_e in (20)(22)

Table 2. Device resolvents and reflection coefficients.

The ideal diode admits the explicit, nonexpansive resolvent JγeTe(ae)=min⁡{ae,0}J_{\gamma_eT_e}(a_e)=\min\{a_e,0\}, so its set-valued branch relation can be used directly in the iteration. By contrast, Newton’s method on the nodal equations requires a differentiable characteristic, and circuit simulators resort to damping and continuation [14].

For a nonlinear resistor, with g:R→Rg:\mathbb{R}\to\mathbb{R} continuously differentiable and increasing, let

he:R→R,he(ve)=ve+γeg(ve).(25)h_e:\mathbb{R}\to\mathbb{R},\qquad h_e(v_e)=v_e+\gamma_e g(v_e). \tag*{(25)}

Since he′(ve)=1+γeg′(ve)≥1h_e'(v_e)=1+\gamma_e g'(v_e)\ge1 for every ve∈Rv_e\in\mathbb{R}, the function heh_e is strictly increasing and onto R\mathbb{R}, so JγeTe=he−1J_{\gamma_eT_e}=h_e^{-1}, and ve=he−1(ae)v_e=h_e^{-1}(a_e) may be computed by Newton’s method [14], vectorized over all such branches. For example, a diode may be modeled by the Shockley equation

ie=g(ve)=Is(exp⁡(veVT)−1),(26)i_e=g(v_e)=I_s\left(\exp\left(\frac{v_e}{V_T}\right)-1\right), \tag*{(26)}

with Is,VT>0I_s,V_T>0. Its resolvent is JγeTe(ae)=he−1(ae)J_{\gamma_eT_e}(a_e)=h_e^{-1}(a_e), with heh_e defined by (20) for this choice of gg. An explicit resolvent calculation is given in [7].

For a nonlinear resistor satisfying g′∈[Rmax⁡−1,Rmin⁡−1]g'\in[R_{\max}^{-1},R_{\min}^{-1}] for some 0<Rmin⁡≤Rmax⁡0<R_{\min}\le R_{\max}, the derivative

CγeTe′(ae)=1−γes1+γesC'_{\gamma_eT_e}(a_e)=\frac{1-\gamma_e s}{1+\gamma_e s}

decreases with s=g′(ve)s=g'(v_e). Hence,

ρe≤max⁡{∣Rmax⁡−γe∣Rmax⁡+γe,∣Rmin⁡−γe∣Rmin⁡+γe}.(27)\rho_e\le\max\left\{\frac{\lvert R_{\max}-\gamma_e\rvert}{R_{\max}+\gamma_e},\frac{\lvert R_{\min}-\gamma_e\rvert}{R_{\min}+\gamma_e}\right\}. \tag*{(27)}

The right-hand side is minimized by γe=Rmin⁡Rmax⁡\gamma_e=\sqrt{R_{\min}R_{\max}}, with minimum value κ−1κ+1\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}, where κ=Rmax⁡/Rmin⁡\kappa=R_{\max}/R_{\min}.

Case Study: A Resistive Crossbar Array

Memristive crossbar arrays have attracted considerable attention as the substrate of analog in-memory computing and neuromorphic hardware, since they store a matrix in the conductances of their devices and compute a matrix-vector product by applying voltages to their word lines and reading the currents of their bit lines [2, 3]. However, line resistances and sneak paths through unselected devices make the result differ from the ideal product, so that assessing an array requires its operating point at every input [11]. This section illustrates the performance of Algorithm 1 on the problem of simulating a resistive crossbar array in comparison with ngspice [46], an open-source SPICE-based circuit simulator.

Circuit modeling and port resistances

Consider the N×NN\times N crossbar array of Figure 2, with NN word and NN bit lines. Word line rr is associated with the nodes wr,1,…,wr,Nw_{r,1},\ldots,w_{r,N}, joined by line resistances RℓR_\ell, and bit line cc is associated with the nodes β1,c,…,βN,c\beta_{1,c},\ldots,\beta_{N,c}, joined by the same line resistances. Each word line is driven at its head by a voltage source Vˉr\bar{V}_r with series resistance RsR_s, and each bit line is terminated at its foot by a load RLR_L. The source and its series resistance form one branch, whose resolvent and reflection coefficient are given in Table II. Several cross-point configurations have been studied for resistive crossbar arrays, including one-resistor (1R) and one-diode–one-resistor (1D1R) cells [11, 47]. We consider three circuit models for joining wr,cw_{r,c} to βr,c\beta_{r,c} based on these configurations.

Square crossbar array with N word and N bit lines

Figure 2. Square crossbar array with NN word and NN bit lines. Each cross-point of the array is joined by either a nonlinear resistor alone (1R), or a resistor in series with a diode modeled either ideally (ideal 1D1R) or with the Shockley equation (Shockley 1D1R).

Motivated by the piecewise-linear resistor characteristics considered in [38], we first consider a 1R model, where each cross-point is joined by a nonlinear resistor with branch relation

i=vRmax⁡+(1Rmin⁡−1Rmax⁡)tanh⁡(v).(28)i=\frac{v}{R_{\max}}+\left(\frac{1}{R_{\min}}-\frac{1}{R_{\max}}\right)\tanh(v). \tag*{(28)}

Next, we consider the ideal 1D1R model [11, 47], which places an ideal diode (with behavior in Table I) in series with the 1R device. Finally, we consider the Shockley 1D1R model, which places a diode governed by the Shockley equation (26) in series with the 1R device. For 1D1R arrays, the circuit has n=3N2n = 3N^2 nodes and m=4N2m = 4N^2 branches, namely N(N−1)N(N - 1) word line resistors, N(N−1)N(N - 1) bit line resistors, 2N22N^2 device branches, NN source branches and NN loads. Similarly, 1R arrays have n=2N2n = 2N^2 nodes and m=3N2m = 3N^2 branches.

The line, source, and load branches are matched by setting their port resistances equal to the corresponding resistances. Each nonlinear resistor with branch relation (28) has incremental resistance in [Rmin⁡,Rmax⁡][R_{\min}, R_{\max}], so that the port resistance minimizing the bound (27) is γe=Rmin⁡Rmax⁡\gamma_e = \sqrt{R_{\min}R_{\max}}. However, voltage drops along the lines bias the operating point towards ve=0v_e = 0, where the incremental resistance is close to Rmin⁡R_{\min}. This motivates the choice γe=Rmin⁡\gamma_e = R_{\min}, which is used in our experiments. All diode models in Table 2 have reflection coefficient one. For diodes of both types, we use γe=Rmin⁡Rmax⁡\gamma_e = \sqrt{R_{\min}R_{\max}}, which yields faster convergence in our experiments.

Numerical implementation and results

We compare Algorithm 1 with ngspice on the three crossbar arrays models described above of size N×NN \times N, with N=16,32,…,1024N = 16, 32, \ldots, 1024. For each array size, ten random circuits are generated and simulated with both methods. For each crossbar array, the line resistances are Rℓ=5 ΩR_\ell= 5\ \Omega, the source voltages Vˉr\bar{V}_r are drawn uniformly from (−1,1.5) V(-1, 1.5)\ \mathrm{V}, the source resistances are Rs=50 ΩR_s = 50\ \Omega and the loads are RL=1 kΩR_L = 1\ \mathrm{k}\Omega. Every nonlinear resistor is described by (28), with Rmin⁡R_{\min} and Rmax⁡R_{\max} drawn per cell, log-uniformly, from [1,10] kΩ[1, 10]\ \mathrm{k}\Omega and [50,200] kΩ[50, 200]\ \mathrm{k}\Omega. In the 1D1R arrays, each resistor is in series with a diode, either using the ideal or Shockley model, with Is=1 nAI_s = 1\ \mathrm{nA}, VT=25.85 mVV_T = 25.85\ \mathrm{mV}. The resolvents of the nonlinear resistors (28) and Shockley diodes (26) are computed numerically as described in Section IV-F.

Algorithm 1 starts from a0=0a^0 = 0, with relaxation parameter α=1\alpha= 1 for 1R arrays and α=0.8\alpha= 0.8 for 1D1R arrays. It factorizes the weighted Laplacian AΓ−1A⊤A\Gamma^{-1}A^\top once with CHOLMOD (AMD ordering, one thread). It stops when KCL holds at every node to relative tolerance 10−910^{-9} and absolute tolerance 10−12 A10^{-12}\ \mathrm{A}, and the KVL residual is below 10−9max⁡∣v∣10^{-9}\max|v|. Across all experiments the two solvers’ node potentials agree to within 2.2×10−7 V2.2 \times10^{-7}\ \mathrm{V} on the 1R and ideal 1D1R arrays and 8×10−6 V8 \times10^{-6}\ \mathrm{V} on the Shockley 1D1R arrays. All experiments were conducted on the same desktop computer (6-core Intel Core i5, 31.8 GB RAM), each in a separate process. Runtime is measured as wall-clock time, including setup. Memory usage is measured as the peak process working set.

Figure 3 reports our numerical results. Algorithm 1 is faster and requires less memory than ngspice in every run with N>16N > 16. On the 1R array, Algorithm 1 converges in a number of iterations that does not depend on the array size, consistent with the bound of Theorem 4, which does not depend on the topology. For the 1R and ideal 1D1R arrays, ngspice’s KLU factorization failed at N=1024N = 1024. For the Shockley 1D1R arrays, ngspice reached the 1600 s time limit at N=512N = 512. The Shockley model also required damping of ngspice’s Newton iterations to converge.

Runtime, peak memory, and iteration time for 1R, ideal 1D1R, and Shockley 1D1R arrays

Figure 3. Runtime in seconds (top), peak memory in GB (middle) and, for Algorithm 1 only, iterations to convergence (bottom) for ngspice (dashed) and Algorithm 1 (solid), median over 10 random circuits per size. On the 1R and ideal 1D1R arrays, the KLU factorization of ngspice fails at N=1024N = 1024, and on the Shockley 1D1R arrays ngspice times out after 1600 s at N=512N = 512.

1RIdeal 1D1RShockley 1D1R
Resolvent evaluation29.521.336.4
Linear system solution36.341.134.4
Matrix–vector products9.99.98.1
Convergence checks20.323.417.5
Iterate update4.04.43.6

Table 3. Share (%) of one iteration of Algorithm 1 spent in each step on the 1024 × 1024 arrays, median over 10 random circuits.

Table III reports the median percentage of iteration time spent in each step on the 1024 × 1024 arrays. Iterations account for 71–99% of the total runtime of Algorithm 1, with the one-time factorization of AΓ−1A⊤A\Gamma^{-1}A^\top accounting for the remainder. The steps comprise branch resolvent evaluation (line 2), linear system solution using the Cholesky factor (line 3), sparse matrix–vector products with AA and A⊤A^\top (lines 3 and 4), convergence checks for KCL and KVL, and the relaxed iterate update (line 4). Resolvent evaluation and the linear system solution account for 62–71% of the iteration time, and optimizing these steps as discussed in Remark 3 offers substantial speedups.

Conclusion

The paper has developed an operator splitting method for computing operating points of nonlinear resistive networks. The behavioral formulation separates the branch relations from Kirchhoff’s laws and casts circuit simulation as a zero-finding problem. The resulting relaxed Peaceman–Rachford iteration uses scattering variables and branch port resistances, requiring the solution of independent scalar branch equations and a linear system with a fixed weighted graph Laplacian whose factorization can be reused. Convergence is established maximal monotone branch relations under suitable relaxation whenever an operating point exists. Contractive branch reflections yield a linear convergence bound independent of network topology. Numerical experiments on crossbar arrays illustrate the computational advantages.

Several directions remain open. Circuits with dynamic elements call for the same analysis in Hilbert spaces of signals. Further work includes inexact solves of the Laplacian system by iterative methods, the selection of the port resistances for nonlinear devices from data, and extensions of our formulation to dynamic optimization over system behaviors [30].

References

  1. [1]A. Momeni, B. Rahmani, B. Scellier, L. G. Wright, P. L. McMahon, C. Wanjura, Y. Li, A. Skalli, N. G. Berloff, T. Onodera, I. Oguz, F. Morichetti, P. del Hougne, M. Le Gallo, A. Sebastian, A. Mirhoseini, C. Zhang, D. Marković, D. Brunner, C. Moser, S. Gigan, F. Marquardt, A. Ozcan, J. Grollier, A. J. Liu, D. Psaltis, A. Alù, and R. Fleury, “Training of physical neural networks,” Nature, vol. 645, pp. 53–61, Sept. 2025.
  2. [2]D. Ielmini and H.-S. P. Wong, “In-memory computing with resistive switching devices,” Nature Electron., vol. 1, no. 6, pp. 333–343, 2018.
  3. [3]A. Sebastian, M. Le Gallo, R. Khaddam-Aljameh, and E. Eleftheriou, “Memory devices and applications for in-memory computing,” Nature Nanotechnol., vol. 15, no. 7, pp. 529–544, 2020.
  4. [4]Y. Huang, T. Ando, A. Sebastian, M.-F. Chang, J. J. Yang, and Q. Xia, “Memristor-based hardware accelerators for artificial intelligence,” Nat. Rev. Electr. Eng., vol. 1, no. 5, pp. 286–299, 2024.
  5. [5]W.-H. Chen, C. Dou, K.-X. Li, W.-Y. Lin, P.-Y. Li, J.-H. Huang, J.-H. Wang, W.-C. Wei, C.-X. Xue, Y.-C. Chiu, Y.-C. King, C.-J. Lin, R.-S. Liu, C.-C. Hsieh, K.-T. Tang, J. J. Yang, M.-S. Ho, and M.-F. Chang, “CMOS-integrated memristive non-volatile computing-in-memory for AI edge processors,” Nature Electronics, vol. 2, no. 9, pp. 420–428, 2019.DOI
  6. [6]B. Scellier, “A fast algorithm to simulate nonlinear resistive networks,” in Proc. 41st Int. Conf. Mach. Learn., vol. 235 of Proc. Mach. Learn. Res., pp. 43477–43503, 2024.arxiv.org/abs/2402.11674
  7. [7]T. Chaffey, “Circuit realization and hardware linearization of monotone operator equilibrium networks,” arXiv:2509.13793, 2025.arxiv.org/abs/2509.13793
  8. [8]T. Chaffey and R. Sepulchre, “Monotone one-port circuits,” IEEE Trans. Autom. Control, vol. 69, no. 2, pp. 783–796, 2024.DOI
  9. [9]A. Shahhosseini, T. Chaffey, and R. Sepulchre, “Operator-splitting methods for neuromorphic circuit simulation,” arXiv:2505.22363, 2025.arxiv.org/abs/2505.22363
  10. [10]A. Shahhosseini, T. Burger, and R. Sepulchre, “Variable metric splitting methods for neuromorphic circuit simulation,” in Proc. 64th IEEE Conf. Decis. Control, pp. 968–973, 2025.DOI
  11. [11]A. Chen, “A comprehensive crossbar array model with solutions for line resistance and nonlinear device characteristics,” IEEE Trans. Electron Devices, vol. 60, no. 4, pp. 1318–1326, 2013.DOI
  12. [12]L. W. Nagel, “SPICE2: A computer program to simulate semiconductor circuits,” Tech. Rep. UCB/ERL M520, Univ. California, Berkeley, CA, USA, 1975.
  13. [13]C.-W. Ho, A. E. Ruehli, and P. A. Brennan, “The modified nodal approach to network analysis,” IEEE Trans. Circuits Syst., vol. 22, no. 6, pp. 504–509, 1975.DOI
  14. [14]F. N. Najm, Circuit Simulation. Hoboken, NJ, USA: Wiley, 2010.
  15. [15]T. A. Davis and E. Palamadai Natarajan, “Algorithm 907: KLU, a direct sparse solver for circuit simulation problems,” ACM Trans. Math. Softw., vol. 37, no. 3, pp. 36:1–36:17, 2010.DOI
  16. [16]J. E. Spingarn, “Partial inverse of a monotone operator,” Appl. Math. Optim., vol. 10, no. 3, pp. 247–265, 1983.DOI
  17. [17]J. C. Willems, “The behavioral approach to open and interconnected systems,” IEEE Control Syst. Mag., vol. 27, no. 6, pp. 46–99, 2007.
  18. [18]D. Davis and W. Yin, “Convergence rate analysis of several splitting schemes,” in Splitting Methods in Communication, Imaging, Science, and Engineering (R. Glowinski, S. J. Osher, and W. Yin, eds.), pp. 115–163, Cham, Switzerland: Springer, 2016.arxiv.org/abs/1406.4834
  19. [19]P.-L. Lions and B. Mercier, “Splitting algorithms for the sum of two nonlinear operators,” SIAM J. Numer. Anal., vol. 16, no. 6, pp. 964–979, 1979.DOI
  20. [20]J. Eckstein and D. P. Bertsekas, “On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators,” Math. Programm., vol. 55, pp. 293–318, 1992.DOI
  21. [21]P. Mahey, S. Oualibouch, and T. Pham Dinh, “Proximal decomposition on the graph of a maximal monotone operator,” SIAM J. Optim., vol. 5, no. 2, pp. 454–466, 1995.DOI
  22. [22]B. D. H. Tellegen, “A general network theorem, with applications,” Philips Res. Rep., vol. 7, pp. 259–269, 1952.
  23. [23]B. D. O. Anderson and S. Vongpanitlerd, Network Analysis and Synthesis: A Modern Systems Theory Approach. Englewood Cliffs, NJ, USA: Prentice-Hall, 1973.
  24. [24]H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Cham, Switzerland: Springer, 2nd ed., 2017.
  25. [25]G. J. Minty, “Monotone networks,” Proc. Roy. Soc. London A, vol. 257, no. 1289, pp. 194–212, 1960.DOI
  26. [26]R. T. Rockafellar, “Monotone relations and network equilibrium,” in Variational Inequalities and Network Equilibrium Problems (F. Giannessi and A. Maugeri, eds.), pp. 271–288, New York, NY, USA: Plenum Press, 1995.
  27. [27]T. Chaffey, S. Banert, P. Giselsson, and R. Pates, “Circuit analysis using monotone+skew splitting,” Eur. J. Control, vol. 74, p. 100854, 2023.DOI
  28. [28]J. Quan, B. Evens, R. Sepulchre, and P. Patrinos, “Scaled relative graphs for nonmonotone operators with applications in circuit theory,” Eur. J. Control, vol. 86, p. 101335, 2025.
  29. [29]Y. Tang, C. Cenedese, A. Rimoldi, F. Dörfler, J. Lygeros, and A. Padoan, “Split-as-a-Pro: behavioral control via operator splitting and alternating projections,” in Proc. 23rd Eur. Control Conf., pp. 1495–1501, 2025.arxiv.org/abs/2505.19411
  30. [30]Y. Tang, C. Cenedese, A. Rimoldi, F. Dörfler, J. Lygeros, and A. Padoan, “Dynamic optimization over system behaviors.” In preparation, 2026.
  31. [31]P. Giselsson and S. Boyd, “Linear convergence and metric selection for Douglas–Rachford splitting and ADMM,” IEEE Trans. Autom. Control, vol. 62, no. 2, pp. 532–544, 2017.arxiv.org/abs/1410.8479
  32. [32]A. Fettweis, “Wave digital filters: Theory and practice,” Proc. IEEE, vol. 74, no. 2, pp. 270–327, 1986.DOI
  33. [33]A. Bernardini, K. J. Werner, J. O. Smith, and A. Sarti, “Generalized wave digital filter realizations of arbitrary reciprocal connection networks,” IEEE Trans. Circuits Syst. I, vol. 66, no. 2, pp. 694–707, 2019.DOI
  34. [34]A. Bernardini, R. Giampiccolo, E. Bozzo, and F. Fontana, “Wave digital extended fixed-point solvers for circuits with multiple one-port nonlinearities,” IEEE Trans. Circuits Syst. I, vol. 72, no. 5, pp. 2314–2326, 2025.DOI
  35. [35]E. K. Ryu and W. Yin, Large-Scale Convex Optimization: Algorithms and Analyses via Monotone Operators. Cambridge, U.K.: Cambridge Univ. Press, 2022.
  36. [36]B. Bollobás, Modern Graph Theory, vol. 184. New York, NY, USA: Springer, 1998.
  37. [37]F. Bullo, Lectures on Network Systems. Kindle Direct Publ., 1.6 ed., 2022.
  38. [38]L. O. Chua, C. A. Desoer, and E. S. Kuh, Linear and Nonlinear Circuits. New York, NY, USA: McGraw-Hill, 1987.
  39. [39]G. D. Hachtel, R. K. Brayton, and F. G. Gustavson, “The sparse tableau approach to network analysis and design,” IEEE Trans. Circuit Theory, vol. 18, no. 1, pp. 101–113, 1971.DOI
  40. [40]J. C. Willems, Classical Network Theory. San Francisco, CA, USA: Holden-Day, 1968.
  41. [41]J. C. Willems, “Dissipative dynamical systems Part I: General theory,” Arch. Rational Mech. Anal., vol. 45, no. 5, pp. 321–351, 1972.DOI
  42. [42]A. van der Schaft, L2-Gain and Passivity Techniques in Nonlinear Control. Cham, Switzerland: Springer, 3rd ed., 2017.
  43. [43]G. H. Golub and C. F. Van Loan, Matrix Computations. Baltimore, MD, USA: Johns Hopkins Univ. Press, 4th ed., 2013.
  44. [44]H. H. Bauschke, S. M. Moffat, and X. Wang, “Firmly nonexpansive mappings and maximally monotone operators: Correspondence and duality,” Set-Valued Var. Anal., vol. 20, no. 1, pp. 131–153, 2012.arxiv.org/abs/1101.4688
  45. [45]R. Kyng and S. Sachdeva, “Approximate Gaussian elimination for Laplacians: Fast, sparse, and simple,” in Proc. 57th Annu. IEEE Symp. Found. Comput. Sci., pp. 573–582, 2016.arxiv.org/abs/1605.02353
  46. [46]“ngspice: Open source SPICE simulator.” https://ngspice.sourceforge.io/. Accessed: Nov. 2, 2026.
  47. [47]M. Liu, Q. Liu, H. Lv, and S. Long, “Resistive switching devices: Mechanism, performance and integration,” in Handbook of Memristor Networks (L. Chua, G. C. Sirakoulis, and A. Adamatzky, eds.), pp. 843–911, Cham, Switzerland: Springer, 2019.DOI

Paper details

vlnc:W_7zbjsusb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

Not recorded for this paper

View statement
Looking for related papers…
Contents