Hariharan Narayanan
email: hariharan.narayanan@tifr.res.in

Port characteristic and maximum power transfer for diode resistor circuits

Keywords: Ideal diodes, Piecewise linear, Port characteristic, Maximum power, Interior point method. 2000 MSC: 94C05, 94C15

This paper deals with the problems of computing port characteristics and maximum power transfer for 1ports which contain (ideal) diodes, (positive) resistors and sources. The following are the main contributions.

1. An algorithm for solving circuits with (continuous positive slope) piecewise linear devices through repeated solution of circuits with primitive (single corner) versions of such devices. The number of repetitions is bounded above by the product of the number of devices and the product of the logarithms of the number of states (number of corners plus one) in the devices. 2. An adaptation of gradient descent methods for solving circuits with piecewise linear devices. 3. A linear time algorithm for the computation of port characteristic of a series parallel 1-port when the devices are piecewise linear and an approximation (of guaranteed level of accuracy) of the port characteristic when the device port characteristic is known approximately. 4. A simple algorithm for determining the region of validity and the maximum power transfer for a specified state of the diodes. When the number of states is polynomial in the number of diodes in the 1-port, this is used to give a polynomial time algorithm for the port characteristic. 5. An adaptation of efficient interior point methods for the solution of circuits with diodes, resistors and sources.

Introduction

The (ideal) diode is a powerful modelling tool in circuit theory. The simplest circuits which involve such devices are the circuits with sources, (positive) resistors and diodes. This class of circuits has come into prominence at the present time since they can be used to model solar cells ( [START_REF] Balato | Series-Parallel PV array re-configuration: Maximization of the extraction of energy and much more[END_REF][START_REF] Maki | Operation of series-connected silicon-based photovoltaic modules under partial shading conditions[END_REF]) to any required degree of accuracy.

In the late 50s, J.B.Dennis [START_REF] Dennis | Mathematical programming and electrical networks[END_REF] showed that analysis of diode resistor source (DRS) circuits reduces to the solution of a quadratic programming problem. However, efficient algorithms for solving such problems were developed only in the 90s and later ( [START_REF] Vaidya | A new algorithm for minimizing convex functions over convex sets[END_REF], [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF], [START_REF] Nesterov | Introductory Lectures on Convex Optimization: A Basic Course[END_REF]). Diode resistor 1-ports have continuous positive slope piecewise linear characteristics. The positive slope condition allows efficient methods of analysis. The study of the more general class of piecewise linear circuits without the positive slope condition has been undertaken by many workers (see [START_REF] Vandewalle | Piecewise-linear circuits and piecewise-linear analysis[END_REF], [START_REF] Leenaerts | Piecewise Linear Modeling and Analysis[END_REF]).

In the case where these circuits are series parallel, their analysis can be performed extremely fast (linear time in the number of diodes). Series parallel graphs were studied in a fundamental way first by Duffin [START_REF] Duffin | Topology of series-parallel networks[END_REF]. Panels of solar cells are series parallel combinations of such cells and therefore, in these cases, the online computations of port characteristics and power transfer can be performed accurately and fast.

In this paper, we present a number of new methods for analysing diode resistor circuits keeping in mind present day needs and the state of the art of mathematical programming.

We show that circuits with devices which have continuous positive slope piecewise linear characteristics, can be solved by repeatedly solving circuits, obtained by replacing these devices with ones which have only a single corner in their characteristics. Alternatively, we show that these circuits can be solved through a gradient descent algorithm which does not depend upon the number of corners in the device characteristics.

We show that there is a linear time algorithm for computing the port characteristics of piecewise linear device 1-ports which have series parallel graphs. For such circuits, we also derive bounds on the error in the characteristics when the device characteristics are known only approximately.

For a DRS 1-port, we give an algorithm for determining the region of validity and the maximum power transfer for a specified state of the diodes. When the number of states is polynomial in the number of diodes in the 1-port, this is used to give a polynomial time algorithm for computing the port characteristic.

We adapt efficient interior point methods for the solution of DRS circuits.

In what follows, by DRS multiports, we mean diode resistor source circuits where the diodes and ports together contain no loops or cutsets and the sources are accompanied by positive resistors. The outline of the paper is as follows.

Section 2 contains the definition and the basic properties of DRS circuits. Among other things we show that DRS multiports have unique solution for a given port termination by voltage or current sources.

Section 3 contains a method for solving circuits with piecewise linear devices, as above, by repeated solution of appropriate DRS circuits with the same number of diodes as the number of the original devices. The number of repetitions is bounded by the product of the number of devices and the product of the logarithms of the number of states (number of corners plus one) of the devices.

Section 4 studies DRS circuits through the resistive multiport that results when the diodes are replaced by ports. We show that the port characteristic of DRS 1-ports has to be continuous piecewise linear with positive slope and with finite number of corners.

Section 5 is on the port connection graph for a 1-port built by connecting smaller 1-ports. The notion of a connection tree for series parallel graphs is defined.

Section 6 is on series parallel DRS 1-ports. A linear time algorithm for building the port characteristics of such 1-ports is given. It is shown that the port characteristic of a series parallel DRS 1-port has number of corners bounded by the number of diodes in the 1-port.

Section 7 is on approximate computation of port characteristic of series parallel 1-ports, when the port characteristic of the 1-ports composing them is only known approximately.

Section 8 deals with the computation of maximum power transfer for explicitly given piecewise linear characteristics and with the approximate computation when the port characteristic is not known explicitly.

Section 9 is on the region of validity and maximum power transfer for a specified state of diodes in the multiport. The ideas are used to give an algorithm for the explicit computation of port characteristics of DRS 1-ports. The algorithm requires solution of resistive networks corresponding to valid diode states. Given one valid state all states are successively computed by such solutions (twice for each diode state).

Section 10 is on the adaptation of gradient descent methods for solving circuits with piecewise linear devices.

Section 11 is on the quadratic programming formulation for DRS circuits and on an adaptation of polynomial time interior point methods for solving DRS circuits. It is shown that these methods essentially reduce to replacing the diode characteristic by hyperbolas close to the on-off voltage and current axes and moving from one hyperbola to another closer to the axes. Each step in the algorithm requires the solution of a resistive network obtained by replacing the diode by a suitable Thevenin circuit.

Appendix contains an informal derivation of necessary and sufficient conditions for optimality of convex programming problems. An ideal diode has the v -i characteristic v ≤ 0, i ≥ 0, v × i = 0. We will call a multiport N P , (network N ) containing ideal diodes, positive resistors, current and voltage sources, a DRS multiport (DRS network) iff

1. there are no cutsets (minimal sets of edges which when deleted break up the graph) or loops of the graph of N P , containing only diodes and ports, 2. (see Figure 1) each current source occurs in parallel with a Norton circuit (positive resistor in parallel with a current source) or with a Thevenin circuit (positive resistor in series with a voltage source), each voltage source occurs in series with a Norton circuit or with a Thevenin circuit (in Figure 1, 'T /N ' refers to 'Thevenin/Norton').

We will call a DRS 1-port primitive iff it contains only one diode and this diode occurs in series (parallel) with a Thevenin circuit or a Norton circuit with the combination in parallel (series Convention We take the current i P in a port branch P to have direction opposite to the direction of the voltage v P (see Figure 2).

)
The following result is from [START_REF] Dennis | Mathematical programming and electrical networks[END_REF].

Theorem 2. Every DRS network has a solution.

The proof is by reducing the problem of solving the network to that of solving a convex quadratic programming problem (see Section 11). Theorem 3. Let N P be a DRS multiport. Let some of the ports be terminated by voltage sources and others by current sources. Then the resulting network N has a unique solution.

The proof is relegated to the appendix (see Appendix B). An important method of determining port characteristic of DRS 1-ports involves computing characteristics of smaller DRS 1-ports which occur at intermediate stages, using these as devices in a reduced 1-port (see Section 6 and 9.4). We prove later that v -i characteristics of DRS 1-ports are piecewise linear with positive slope and a finite number of corners (Corollary 13). We now focus attention on such 1-ports treating them as devices. Theorem 4 assures us that the procedure is justified. The proof is given in the appendix (see Appendix B). Theorem 4. Let N P be a multiport with the ports containing no loops or cutsets and with devices whose v -i characteristics are continuous piecewise linear with positive slope. Let some of the ports be terminated by voltage sources and others by current sources. Then the resulting network N has a unique solution.

For a piecewise linear characteristic, a corner refers to a point in the characteristic where the slope changes. Henceforth piecewise linear would mean continuous piecewise linear with positive slope and a finite number of corners.

The next result asserts that piecewise linear devices can be realized as DRS 1-ports. It is a straight forward application of the discussion of piecewise linear devices found in [START_REF] Chua | Linear and nonlinear circuits[END_REF]. We omit the routine proof. Lemma 5. A piecewise linear device with s -1 corners (s straight line segments) can be realized as a series parallel combination of (s -1) DRS 1-ports each with atmost one diode. A piecewise linear device with 1 corner can be realized as a primitive DRS subcircuit.

Example 29 in the appendix illustrates the idea behind the proof.

Solving networks with piecewise linear devices realized as DRS networks

We have seen that a network with piecewise linear devices can be solved as a DRS circuit (Lemma 5). However this would result in a network which has as many diodes as the sum of the number of line segments in the v -i characteristics of all the devices. In this section we prove a result which states that repeated solution of networks with only as many diodes as the number of piecewise linear devices in the original network is sufficient. The number of such solutions to be computed is bounded by the number of devices times the product of the logarithms of the number of line segments in the v -i characteristics of all the devices.

We call the straight line segments that make up the v -i characteristic of a piecewise linear device, the states of the device. (In Figure 3(a), the piecewise linear device has 4 states, the segment to the left of (v 0 , i 0 ), the one between (v 0 , i 0 ), (v 1 , i 1 ), the one between (v 1 , i 1 ), (v 2 , i 2 ), and the segment to the right of (v 2 , i 2 ).) We call a piecewise linear device with only one corner (two states) in its v -i characteristic, a primitive piecewise linear device and denote it by D. A primitive DRS subcircuit has such a v -i characteristic (see Figure 3 (c)).

Definition 6. Two piecewise linear devices agree over an open interval

(v 1 , v 2 ) ((i 1 , i 2 )) iff their v -i curves are identical over (v 1 , v 2 ) ((i 1 , i 2 )
). We say a primitive piecewise linear device D agrees with a piecewise linear device L, iff its corner (v , i ) is also a corner of the latter and the two agree with each other over an open interval containing v (i ). (The primitive device in Figure 3 (c), agrees with the piecewise linear device in Figure 3 (a).)

Definition 7. Let N P be a multiport composed of piecewise linear devices L 1 , • • • , L n . We say a point (v j , i j ) on the v -i characteristic of L j is to the left of a corner (right of a corner) (v corner j , i corner j ) of the device L j iff v j ≤ v corner j (v j ≥ v corner j
). Let v P (i P ) be a port voltage (current) and let (v P , i P ), (v 1 , i 1 ), • • • , (v n , i n ) be the corresponding unique solution of N P (Theorem 4). We say the solution is to the left of a corner (right of a corner)

(v corner j , i corner j ) of the device L j iff v j ≤ v corner j (v j ≥ v corner j ).
We now have a result which reduces the solution of a network containing piecewise linear devices, to that of networks each of which has primitive piecewise linear devices, in place of the piecewise linear devices of the former. Theorem 8. Let N P be a multiport on graph G P , with its ports containing no loops or cutsets and composed of devices

L 1 , • • • , L k , T k+1 , • • • T n ,
where the L i are piecewise linear and the T j , Thevenin circuits.

G 0 1 G 2 G G 0 1 G 2 G (v 1 , i 1 ) (v 1 , i 1 ) (a) L 1 1 G (v 1 , i 1 ) (v , i ) 0 0 (v , i ) 2 2 v i v i G 3 1 (b) L left v 2 G 1 D i (c) Figure 3: Devices L 1 , L lef t 1 , D 1 1. Let N reduced P be the multiport on graph G P , composed of piecewise linear devices D 1 , L 2 , • • • , L k , T k+1 , • • • T n ,
with the primitive piecewise linear device D 1 agreeing with L 1 . Let v P (i P ) be a port voltage (current) of N P and N reduced P and let (v

P , i P ), (v 1 , i 1 ), • • • , (v n , i n ), (v P , i P ), (v reduced 1 , i reduced 1 ), • • • , (v reduced n , i reduced n
), be the corresponding unique solutions of N P , N reduced P , respectively. Let (v 1 , i 1 ) be the common corner of D 1 , L 1 . Then, (v 1 , i 1 ) lies to the left (right) of (v

1 , i 1 ) in N P iff (v reduced 1 , i reduced 1
) lies to the left (right) of (v 1 , i 1 ) in N reduced P . 2. Let L j have s j states for j = 1, • • • , k, and let s r :≡ Π k r (log 2 (s j )). Then in the solution of N P for the given port voltage (current), the states of L 1 , • • • , L k , can be computed by solving Σ k 1 s r reduced multiports with the same input port voltage (current) and with L 1 , • • • , L k , replaced with either fixed Thevenin circuits or suitable primitive devices agreeing with them and with T k+1 , • • • T n as before.

Proof. 1. We use the fact that piecewise linear multiports with no loops or cutsets within their set of ports have unique solutions for any given v P (i P ) (Theorem 4). In the following argument we use port voltage v P as the input. Clearly the same argument is valid with port current i P as the input.

Let L lef t 1 be a piecewise linear device which agrees with L 1 to the left of (v 1 , i 1 ) and agrees with D 1 to the right of (v 1 , i 1 ) (see Figure 3). Note that L lef t 1 has a continuous positive slope v -i characteristic. Let N 1lef t P be the multiport on graph G P , obtained by retaining all devices except L 1 but replacing L 1 with L lef t 1 (see Figure 3). Since all its devices are piecewise linear, N 1lef t P has a unique solution when the port voltage is v P . In the unique solution of N P corresponding to v P , let the state of L 1 lie to the left of (v 1 , i 1 ). It is clear that this solution would also satisfy the constraints of N 1lef t P and therefore, must be its unique solution corresponding to v P . Next let N 1reduced P be the multiport obtained by retaining all devices except L 1 but replacing L 1 with D 1 . Suppose in its solution, the state of L 1 lies to the right of (v 1 , i 1 ). But this solution would also satisfy the constraints of N 1lef t P which violates the uniqueness of solution of N 1lef t P . We conclude that the unique solution of N 1reduced P corresponding to v P lies to the left of (v 1 , i 1 ). By a similar argument it follows that if in N P the unique solution corresponding to v P lies to the right of (v 1 , i 1 ), the unique solution of N 1reduced P corresponding to v P also lies to the right of (v 1 , i 1 ). 2. In the following argument, the Thevenin circuits T k+1 , • • • , T n , are left unchanged throughout. To determine the state of L 1 , we can check whether the state lies to the left or right of the corner that is picked, each time solving a circuit with a suitable primitive piecewise linear device D 1 and devices L 2 , • • • , L k , as before. This binary search on the states, requires us to solve log 2 (s 1 ) such circuits.

To obtain the state of L k when L 1 , • • • , L k-1 are replaced with fixed primitive devices D1 , • • • , Dk-1 and L k , as before, we need to solve log 2 (s k ) circuits with If we know the state l 1 of L 1 in N , we can replace it by a Thevenin circuit T 1 whose v -i characteristic is the straight line obtained by extending the straight line segment l 1 to -∞ and +∞. Finding the state of L 2 in the network with devices

L 1 , • • • , L k replaced D1 , • • • , Dk-1 , D k ,
T 1 , L 2 , • • • , L k , T k+1 , • • • , T n requires by the above argument, solution of Π k 2 log 2 (s j ) circuits with L 1 , • • • , L k , replaced with T 1 , D 2 , • • • , D k where D 2 , • • • , D k
are primitive devices chosen appropriately for binary search. In general finding the state of L r in the network with To solve the resulting network N , the binary search starts with the network N middle obtained by replacing D 1 , D 2 , D 3 , L 4 , L 5 in N , by D 1 , D 2 , D 3 , D 42 , L 5 , respectively. Suppose the state of D 42 in this solution is s 42rightextended . This means that the state of L 4 in the solution of N is to the right of (v 2 , i 2 ). In general this means that we now have to move to the 'middle' corner to the right of (v 2 , i 2 ), and replace L 4 by the corresponding primitive device. In the present case the corner is (v 3 , i 3 ) and the primitive device is D 43 . So we replace D 1 , D 2 , D 3 , L 4 , L 5 in N , by D 1 , D 2 , D 3 , D 43 , L 5 , respectively. Suppose in the solution, D 43 is in state s 42lef textended . We conclude that in the solution of N , the state of L 4 is to the left of (v 3 , i 3 ), and to the right of (v 2 , i 2 ), i.e., in state s 42 .

T 1 , • • • , T r-1 , L r , • • • , L k , T k+1 , • • • , T n requires by the above argument solution of Π k r log 2 (s j ) circuits with L 1 , • • • , L k replaced with T 1 , • • • , T r-1 , D r , • • • , D k where D r , • • • , D k are
Next consider the problem of finding the state of L 5 in the circuit where the devices are D 1 , D 2 , D 3 , D 4j , L 5 . This we do by solving the circuits with devices D 1 , D 2 , D 3 , D 4j , D 5i , keeping D 1 , D 2 , D 3 , D 4j fixed but varying D 5i according to the requirement of the binary search. We have to do this log(s 5 ) times. Note that the states of L 5 that we compute with say D 1 , D 2 , D 3 , D 4j and with D 1 , D 2 , D 3 , D 4r , r = j, need have nothing to do with each other and also nothing to do with its state in the final solution.

Thus to determine the state of L 4 in N (devices D 1 , D 2 , D 3 , L 4 , L 5 ) we have to solve log(s 4 ) × log(s 5 ) = 2log(s 5 ) circuits with devices D 1 , D 2 , D 3 , D 4j , D 5r , where D 4j , D 5r are chosen according to binary search.

Diode elimination multiport of a DRS multiport

Definition 10. Let D 1 , • • • , D k , be the diodes of a DRS multiport N P (network N ). By a state of the diodes we mean an ordered pair (D 1 , D 2 ) where D 1 ⊆ {D 1 , • • • , D k } and D 2 :≡ {D 1 , • • • , D k } -D 1 .
The multiport is said to be at a state (D 1 , D 2 ) for a particular port condition iff for that port condition i D1 is nonnegative, v D1 = 0 D1 , and v D2 is nonpositive, i D2 = 0 D2 . A diode state that occurs for some port condition of N P is said to be a valid state of N P . The multiport N D1,D2

P (network N D1,D2 ) at (D 1 , D 2 ) of N P (N )
is obtained by contracting D 1 and deleting D 2 . We will refer to the diode state at v P = -∞ as the initial state and that at v P = +∞ as the final state. Definition 11. Let N P be a DRS multiport. We say N DP is the diode elimination multiport of N P iff N DP has ports in place of the diodes of N P with the resistors, sources and the ports P unchanged.

Theorem 12. Let N DP be the diode elimination multiport of a DRS multiport N P . Let (D 1 , D 2 ) be a state of the diodes of N P . Then N DP has a hybrid port representation

  i D1 v D2 v P   =   g D1D1 h D1D2 h D1P h D2D1 r D2D2 r D2P h P D1 r P D2 r P P     v D1 i D2 i P   +   J D1 E D2 E P   (1)
and N D1,D2 P has the Thevenin representation

v P = r P P i P + E P , (2)
where r P P is a symmetric positive definite matrix.

Proof. Since N P is a DRS multiport, there are no loops or cutsets containing only diodes and ports. Therefore, the ports D P of N DP contain no loops or cutsets. Suppose the ports of multiport N DP are terminated by voltage sources at some of the ports and current sources at the others. The resulting network has only positive resistors, current and voltage sources. The voltage sources at the ports contain no loops and since each internal voltage source occurs in series with a Thevenin or Norton circuit, all the voltage sources together contain no loops. The current sources at the ports contain no cutsets and since each internal current source occurs in parallel with a Thevenin or Norton circuit, all the current sources together contain no cutsets. Therefore, this network has a unique solution and the currents and voltages at the ports of N DP are uniquely determined. Therefore N DP has every possible hybrid representation (corresponding to some ports as current input and others as voltage input ports). By the same argument N D1,D2 P also has every possible hybrid representation including the Thevenin representation, v P = r P P i P + E P . Since the multiport N D1,D2 P has only positive resistors and sources, we must have r P P as a symmetric positive definite matrix. The Thevenin representation of N D1,D2 P can be obtained from the hybrid representation in Equation 1 by setting voltages v D1 and currents i D2 , to zero. We conclude that r P P = r P P , E P = E P . The result follows.

Corollary 13. The v -i characteristic of a DRS 1-port N P is continuous piecewise linear with positive slope and with the number of straight line segments bounded by 2 k , where k is the number of diodes in the 1-port.

Proof. By Theorem 3, we know that port voltage v P is a function of the port current i P . From Theorem 12, it is clear that the port voltage v P is a positive slope affine function of the port current i P for each valid diode state. We note that the solution space of Equation 1 is convex when the diode state is fixed, i.e., if (i D1 , v D2 , i P , v P ), (i" D1 , v" D2 , i" P , v" P ), i D1 ≥ 0, v D1 = 0 D1 , v D2 ≤ 0, i D2 = 0 D2 , are two solutions, their convex combination also is a solution of the inequalities. (To avoid confusion we have taken the diode port current direction the same as the diode voltage direction.) Since the circuit has a unique solution for any port current i P this convex combination is the unique solution for the corresponding combination of port currents. Therefore if the diode states are the same at i P , i" P , between the two currents also they would be the same.

The continuity of the function is clear as long as the diode state remains the same. We now examine the situation where the diode state changes. For a particular port current i P , let D 11 (D 22 ) be the set of diodes where the current (voltage) in the diode is positive (negative) and let D 12 be the set of diodes for which both the current and voltage are equal to zero. We will say the state (D

(D 11 , D 22 , D 12 ). Because (D" 1 , D" 2 ) is compatible with (D 11 , D 22 , D 12
), it can also be taken to be the diode state when the port current is i P . We then have the relationship r (D"1,D"2) ∆i P = ∆v P for the diode state (D" 1 , D" 2 ), where r D2) , where (D From the above argument about convexity of the solution space when the diode state is the same, it follows that once the circuit has moved away from a diode state when v P (i P ) is increased, with a further increase, it cannot return to it. Thus the total number of diode states encountered between any port conditions (v 1 P , i 1 P ), (v 2 P , i 2 P ), v 1 P < v 2 P , i 1 P < i 2 P , cannot exceed 2 k , where k is the number of diodes in the DRS circuit. Each diode state is equivalent to one straight line segment and therefore therefore the result follows.

(D"1,D"2) is positive. Let r = max {(D1,D2)} r (D1,
Corollary 14. The v -i characteristic of a primitive DRS 1-port N P is piecewise linear with only two straight line segments.

Proof. Connect a current source J to the single port of N P and vary its value from -∞ to +∞. Let the 1-port seen by the single diode, when it is pulled out, be denoted by P D and let this have a Thevenin equivalent v P D = ri P D + E 1 + αJ, where E 1 depends on the sources within N P and is constant. (Note that r is positive and we must have i P D ≤ 0 since this port current is opposite to the diode current.) Suppose, without loss of generality, v P D = -∞ when J = -∞ so that i P D = 0, and α is positive. It is clear that as J increases, the state of the diode remains the same till E 1 + αJ = 0. When J increases beyond this value, E 1 + αJ becomes positive and we must have i P D ≤ 0, v P D = 0. Thus as J increases from -∞ to +∞ the diode changes state only once so that the v -i characteristic of N P is piecewise linear with only one corner and two straight line segments.

Connection of 1-ports according to port connection graph

The port connection graph G P is a directed graph with edge set {P, P 1 , • • • , P k }. Let the port edges of N P1 , • • • .N P k , be identified with P 1 , • • • , P k , with the same orientation. The resulting graph has as edge set, the union of the singleton set {P } with the edge sets of the N Pj . Let the edges P 1 , • • • , P k be deleted and let the device characteristic of the internal devices of the 1-ports be as before. The resulting 1-port N P is said to be a connection of 1-ports N P1 , • • • .N P k , according to port connection graph G P . (See Figure 4 (a) and (b).) To compute the port characteristic of N P we can first compute the port characteristics of N P1 , • • • .N P k , and define a new 1-port N reduced P on graph G P . If the N Pj are DRS multiports, then the edges P j of G P can be taken to have the piecewise linear port characteristic of N Pj as the device characteristic. These ideas are particularly relevant where G P is a series parallel graph. This case is discussed below.

Let G P1 , G P2 , have only the end points n 1 , n 2 of P 1 and P 2 in common. A parallel connection G P of graphs G P1 , G P2 , is built as follows. We attach G P1 , G P2 , at n 1 , n 2 and add the edge P between n 1 , n 2 and then delete P 1 , P 2 .

Let G P3 , G P4 , have a single node n in common which is an end point of both P 3 and P 4 . A series connection G P of graphs G P3 , G P4 , is built as follows. We attach G P3 , G P4 , at n and add the edge P between the other two end points of P 3 , P 4 and then delete P 3 , P 4 .

We say G P is series parallel iff it has a single edge and no isolated vertices or if it is a series or parallel combination of series parallel graphs with fewer edges. If the port connection graph G P on edge set {P, P 1 , • • • P k } is series parallel, we say N P is a series parallel connection of 1-ports N P1 , • • • .N P k , according to port connection graph G P . Definition 15. When 1-ports N P1 , N P2 , are connected in parallel or in series to result in 1-port N P , the direction of the port edges is said to be aligned, iff when in parallel, the port edges P 1 , P 2 , P, all leave or all enter the common nodes and when in series, P 1 enters the common node and P 2 leaves it, and P 1 , P, both leave their common node and P 2 , P, both enter their common node.

Remark 1. If the multiports being connected are not aligned, we have to reverse the port direction of one of the multiports, in order to align them. This would mean that the v -i characteristic of that multiport has both v-and i-axis flipped. This would not change the slopes but would change the position of the corners ((v , i ) becomes (-v , -i )). This alignment is required so that we can add the v -i characteristics along the v-or the i-direction, as the case may be, in order to compute the characteristics of the resulting multiport. Remark 2. Let N P be a series-parallel connection of primitive multiports with G P as its port connection diagram, but with its direction of edges unknown. There is a linear time algorithm [START_REF] Valdes | The recognition of Series Parallel digraphs[END_REF] which decomposes G P into series-parallel combination of single edges. If at every level of series or parallel combination, we take care to align the corresponding multiports, for a specified direction of the port edge, all the edges of G P would be directed so that they correspond to aligned series-parallel connections. Remark 3. We give a sketch of an algorithm for decomposing G P into series or parallel combination of smaller subgraphs, if such a combination exists.

We will suppose that G P does not have cut vertices, i.e., vertices whose deletion disconnects the graph. Let v 1 , v 2 be the endpoints of P in G P . Delete P. Let G be the resulting graph. Start a df s tree at v 1 and proceed until you reach v 2 avoiding it as much as possible, back tracking if required. Let E 2 be all the edges covered when back tracking from

v 2 up to v 1 . If E 2 = E(G), let G 2 be the subgraph on E 2 and let G 1 be the subgraph on E(G) -E 2 . Add P 1 , P 2 to G 1 , G 2 , respectively across v 1 , v 2 and let G P1 , G P2 , be the resulting graphs. Then G P would be a parallel combination of G P1 , G P2 . Suppose E 2 = E(G)
. By examining the back edges of the above dfs tree, a cut vertex of G would have been revealed, if it exists. Suppose v 3 is such a cut vertex. Let E 3 be the edges covered while backtracking from v 2 to v 3 , and let

E 1 = E(G) -E 2 . Let G 1 be the subgraph on E(G) -E 2 . Add P 1 across v 1 , v 3 , to G 1 and add P 2 across v 3 , v 2 , to G 2 . Let G P1 , G P2
, be the resulting graphs. Then G P would be a series combination of G P1 , G P2 . Definition 16. The connection tree of a series parallel 1-port N P (graph G P ) is defined as follows. The connection tree of a DRS 1-port N P , whose graph G P is a single edge is a node which is called its

root node. Let connection trees of DRS 1-ports N 1 P1 , N 2 P2 , be specified. If N P is a parallel connection of N 1 P1 , N 2 P2
, its connection tree is constructed by first defining a root node n 12 for it and joining it to the root nodes n 1 , n 2 of N 1 P1 , N 2 P2 , respectively by green edges. If N P is a series connection of N 1 P1 , N 2 P2 , its root node n 12 is joined to the root nodes n 1 , n 2 of N 1 P1 , N 2 P2 , respectively by red edges. Nodes of the connection tree which correspond to primitive 1-ports are called leaf nodes. Each node that is not a leaf node, is connected to exactly two nodes beneath it, which are called its children and atmost one node above it, called its parent, if it exists. The maximum length of a path from a node to a leaf node travelling from parent to child, is called its level. The level of the root node is called the depth of the connection tree.

Note that a series parallel DRS 1-port may have more than one connection tree. Figure 4 (a) shows the port connection graph G P of a DRS multiport that is a series parallel connection of DRS 1-ports which are denoted by single edges and Figure 4 (c) shows its connection tree, representing green edges as bold lines and red edges as broken lines. We note that the algorithm of [START_REF] Valdes | The recognition of Series Parallel digraphs[END_REF] (henceforth called Algorithm (series-parallel) ) can build the connection tree of such port connection graphs in linear time.

Port characteristic of series parallel combination of piecewise linear 1-ports

We outline an application to DRS 1-ports which are models of solar cells through ideal diodes, resistors, voltage and current sources. In this case the procedure for computing the port characteristic is linear time on the sum of the number of states of the individual piecewise linear devices.

Even if the graph of our DRS 1-port is non series parallel, we may be able to regard it as a series parallel combination of 1-ports with piecewise linear characteristics. This we could do by pulling out non series parallel subgraphs, attached to the rest of the graph at a pair of nodes, as 1-ports (see Section9.4). The algorithm of [START_REF] Hopcroft | Efficient algorithms for graph manipulation[END_REF] performs this task of pulling out such non series parallel subgraphs in linear time on the number of edges and nodes in the graph. We compute the port characteristics of these 1-ports initially, before we use the procedures described in this section. Therefore our description is in terms of 1-ports with piecewise linear characteristics rather than in terms of DRS 1-ports.

We begin with an elementary but basic lemma. We remind the reader that 'piecewise linear' refers to 'continuous piecewise linear with positive slope'.

Lemma 17. Let N 1 P , N 2 P , be 1-ports with piecewise linear v -i characteristics, respectively i = f 1 (v), i = f 2 (v). Let N parallel P , N series P , be the multiports obtained by aligned parallel connection of the 1-ports at P and aligned series connection of the 1-ports at P respectively. Let the corners of the characteristics of N 1 P , N 2 P , occur at

(v 1 , i 1 ) • • • , (v k , i k ), and (v 1 , i 1 ) • • • , (v m , i m )
(v 1 , f 1 (v 1 )+f 2 (v 1 )), • • • (v k , f 1 (v k )+f 2 (v k )), (v 1 , f 1 (v 1 )+f 2 (v 1 )), • • • , (v m , f 1 (v m )+ f 2 (v m )
) and the corners of N series P belong to the set of points (f -1

1 (i 1 )+f -1 2 (i 1 ), i 1 ), • • • (f -1 1 (i k )+f -1 2 (i k ), i k ), (f -1 1 (i 1 ) + f -1 2 (i 1 ), i 1 ), • • • , (f -1 1 (i m ) + f -1 2 (i m ), i m ).
Proof. The v-i characteristic of N parallel P is obtained by adding the currents i 1 P , i 2 P , into N 1 P , N 2 P , respectively for a given voltage v P . It follows that the points (v

1 , f 1 (v 1 ) + f 2 (v 1 )), • • • (v k , f 1 (v k ) + f 2 (v k ))), (v 1 , f 1 (v 1 ) + f 2 (v 1 )), • • • , (v m , f 1 (v m ) + f 2 (v 1 )), lie in the v -i characteristic of N parallel P . Suppose v -i characteristics of both N 1 P , N 2
P , are straight lines between v P , v" P . Then it is clear that the v -i characteristic of N parallel P would also be a straight line (whose slope would be the sum of the slopes of the characteristics of the individual multiports). If one orders (v

1 , i 1 ) • • • , (v k , i k ), (v 1 , i 1 ) • • • , (v m , i m ) according to increasing values of voltage say (v 1 , î1 ), • • • (v k+m , îk+m ), it follows that between vj , vj+1 , j = 1, • • • , k+m-1, the characteristic of N parallel P
would be a straight line with positive slope. Therefore any corners that exist must belong to the set (v 1 , î1 ), • • • (v k+m , îk+m ). We note that when the slope is positive, i = f (v) is an invertible function and the slope of f -1 (•) is positive. The proof of the series case is similar with the addition taking place along the i-axis.

We have the following consequence of Lemma 17.

Lemma 18. Let N P be a DRS 1-port built by series or parallel combination of DRS multiports N 1 P , N 2 P , where the v -i characteristic of N 1 P , N 2 P , have k 1 , k 2 corners respectively. Then N P has atmost k 1 + k 2 corners.

The following result is a consequence of Lemma 18.

Theorem 19. Let N P be a DRS 1-port that is obtained by series-parallel combination of DRS 1-ports N Pj , j = 1, • • • , k. We then have the following. Proof. 1. This is immediate from Lemma 18.

2. This is clearly true for k = 1. Let it be true for k < m. Let N P be a series or parallel combination of N 1 P1 , N 2 P2 , with all the corners in their v -i characteristics contained respectively within the open boxes -px < v < px, -px < i < px and -qx < v < qx, -qx < i < qx, Without loss of generality, we may assume that the multiports are aligned. When N 1 P1 , N 2 P2 , are put in parallel to result in N P , the final v -i characteristic is obtained by adding currents for a given voltage. It is clear that the corners of the v -i characteristic of

N P lie within -k x ≤ v ≤ k x, -mx ≤ i ≤ mx, where k = max{p, q}. Therefore the corners of the v -i characteristic of N P lie within -mx ≤ v ≤ mx, -mx ≤ i ≤ mx. When N 1 P1 , N 2 P2
, are put in series to result in N P , the final v -i characteristic is obtained by adding voltages for a given current. It is clear that the corners of the v-i characteristic of

N P lie within -mx ≤ v ≤ mx, -k x ≤ i ≤ k x, where k = max{p, q}. Therefore the corners of the v -i characteristic of N P lie within -mx ≤ v ≤ mx, -mx ≤ i ≤ mx.
The following result generalizes the essential idea of Theorem 19.

Theorem 20. Let N 1 P , N 2 P , be 1-ports with characteristics i 1 P = f 1 (v 1 P ), i 2 P = f 2 (v 2 P ), where f 1 (•), f 1 (•), are piecewise linear functions. Further, let N 1 P , N 2 P , have unique solutions for every port voltage (current). Then the series and parallel combinations of N 1 P , N 2 P , also inherit these properties.

Proof. Since f 1 (•), f 2 (•), are strictly monotonically increasing, they are invertible functions so that we have

v 1 P = (f 1 ) -1 (i 1 P ), v 2 P = (f 2 ) -1 (i 2 P
). We will only prove the result for the parallel case. The series case proof is by interchanging the roles of current and voltage. Let N 3 P be the parallel combination of N 1 P , N 2 P . Then its port characteristic is i 3 P = f 1 (v 3 P ) + f 2 (v 3 P ). For a given voltage v 3 P the port voltages of N 1 P , N 2 P , are unique being equal to it and therefore voltages and currents for the non port edges of N 1 P , N 2 P , are uniquely fixed. The function f 1 (•) + f 2 (•) is also strictly monotonically increasing and therefore invertible. For a given current i 3 P , the voltage v 3 P and therefore the port voltages of N 1 P , N 2 P , are uniquely fixed. As before, this fixes uniquely the voltages and currents for the non port edges of N 1 P , N 2 P .

Theorem 19 suggests a linear time algorithm for the computation of the v -i characteristic of a DRS 1port that is a series parallel connection of primitive DRS 1-ports whose v -i characteristics are known. We need a couple of preliminary definitions for the convenient description of the connection of the primitive 1-ports. Definition 21. Let N P be a DRS 1-port with all its corners (v j , i j ), j = 1, • • • k, in the open box -x < v < x, -x < i < x, and let (-x.f (-x)), (x.f (x)) be points in the v -i characteristic of N P . We will call (-x.f (-x)), (x.f (x)), the extreme points and, we will call the corners and the extreme points together, the essential points of N P .

The v -i characteristic of a DRS 1-port is determined by its essential points. We simply have to join the left extreme point (along the v-axis) to the left most corner and extend it to -∞, join each corner to the one to its right and the right most corner to the right extreme point and extend it to ∞. If the connection tree of a DRS 1-port N P and essential points of the primitive DRS 1-ports that are the leaf nodes of the connection tree are given, it is easy to compute the essential points of N P in linear time on the number of leaf nodes.

Algorithm I

Input: 1. The connection tree t(G P ) of the port connection graph G P of N P . 2. The essential points of the v -i characteristic of the leaf nodes of the device characteristic. Output: The essential points of the v -i characteristic of N P at the port P.

Step 1. Compute the essential points of the v -i characteristic of a node n at level m + 1 as follows.

Let edges e 1 , e 2 be between n 1 , n and n 2 , n, where n 1 is at level m and n 2 at level m or lower. Let the essential points of n 1 lie in the box -

x 1 ≤ i 1 ≤ +x 1 , -x 1 ≤ v 1 ≤ +x 1 and that of n 2 lie in the box -x 2 ≤ i 2 ≤ +x 2 , -x 2 ≤ v 2 ≤ +x 2 , with x 1 ≥ x 2 . Extend the v -i characteristic of n 2 to -x 1 ≤ i 2 ≤
+x 1 by extending the leftmost and rightmost line segments.

Step 2(a). If e 1 , e 2 are green, for each essential point (v , i ) of n 1 ((v , i ) of n 2 ), compute the point (v , i") of n 2 ( (v , i") of n 1 ) and thence the essential point (v , i + i") of n.

Step 2(b). If e 1 , e 2 are red, for each essential point (v , i ) of n 1 ((v , i ) of n 2 ), compute the point (v", i ) of n 2 ( (v", i ) of n 1 ) and thence the essential point (v + v", i ) of n. STOP if n is the root node.

Computation of port characteristics by approximation of piecewise linear devices

Piecewise linear devices lend themselves to approximations by devices whose v -i characteristics have fewer corners. Let (v l , i l ), (v r , i r ), be the left most and right most corners respectively of piecewise linear device L orig . We construct the v -i characteristic of the device L approx , as follows. We take as its left most and right most corners, points (v l , i l ), (v r , i r ), respectively, which lie in L orig and further are to the left and right of (v l , i l ), (v r , i r ), respectively. We make the two curves agree with each other in the intervals (-∞, v l ] and [v r , +∞) but modify the characteristic of L orig within [v l , v r ] appropriately.

Definition 22. Let v , i > 0. We say a v -i characteristic L approx is an ( v , i ) approximation to a characteristic L orig iff for each point (v , i ) in L orig , there exist points (v", i ), (v , i 3 ) in L approx such that |v" -v | ≤ v and |i 3 -i | ≤ i .
Example 23. The following are examples of ( v , i ) approximations. Take points (v l , i l ), (v r , i r ) of L orig which are to the left and right of the left most and right most corners respectively of L orig , to be points in L approx and let the latter agree with

L orig outside [v l , v r ].
1. Divide the interval (v l , v r ) into subintervals of length v and the interval (i l , i r ) into subintervals of length i . Sample L orig at the endpoints of these subintervals along the v and i axes and take these to be the corners of L approx . This is a suitable method where L approx has to be computed when L orig is not available explicitly (see Section 8.1). 2. Retain some of the corners of L orig , including the left most and right most, as corners in L approx and join successive retained corners by straight line segments. Let these successive corners never differ in width by more than v and in height by more than i . Outside the left most and right most corners, let L orig , L approx agree. This is a suitable method where L orig is available explicitly.

We now examine how much the port characteristics change if every piecewise linear device were replaced by its approximation when the underlying graph is series parallel. Using the fact that during parallel (series) combination, currents (voltages) get added, it can be shown that

L 3approx P is a (( 1 v + 2 v ), ( 1 i + 2 i of L 3orig P .
We will show this for the parallel case and for the case where points (v 1orig , i 1orig ) ∈ L 1orig P , (v 1orig , i 2orig ) ∈ L 2orig P , and points

(v 1orig -1 v , i 1orig ), (v 1orig , i 1orig + 1 i ) ∈ L 1approx P , (v 1orig -2 v , i 2orig ), (v 1orig , i 2orig + 2 i ) ∈ L 2approx P . The other cases are similar. The point (v 1orig , i 1orig + i 2orig ) ∈ L 3orig P . The segments of L 1approx P , L 2approx P between points (v 1orig -1 v , i 1orig ), (v 1orig , i 1orig + 1 i ), and points (v 1orig -2 v , i 2orig ), (v 1orig , i 2orig + 2 i )
, respectively are continuous increasing curves (both in the v-and in the i-direction). When these segments are added along the i-direction, the resulting segment of

L 3approx P contains points (v 1orig , i 1orig +i 2orig + 1 i + 2 i ), (v 1orig + 1 v + 2 v , i 1orig +i 2orig ).
In general, it can be seen that

L 3approx P contains points (v 1orig , i 1orig + i 2orig ± "), (v 1orig ± , i 1orig + i 2orig ), where 0 ≤ ≤ 1 v + 2 v and 0 ≤ " ≤ 1 i + 2 i . If L 1orig
L 3approx P is a ((k 1 + k 2 ) v , (k 1 + k 2 ) i )-approximation of L 3orig P .
Since the sets of leaf nodes of L 1orig P , L 2orig P do not intersect, (k 1 + k 2 ) is the number of leaf nodes of L 3orig P and the result is true in this case. By induction, the result is true when L 3orig P is the root node.

Maximum power transfer for 1-ports with piecewise linear characteristics

The computation of maximum power transfer when the port characteristic is piecewise linear is easy if the number of corners is not very large. When the 1-port is a series parallel combination of primitive DRS 1-ports, we have seen that the characteristic can be computed in linear time on the number of primitive 1ports (i.e., the number of diodes in the overall 1-port) and further the number corners does not exceed the number of diodes in the 1-port. The computation of maximum power transfer in this case is particularly easy and is outlined below.

Lemma 25. The line segment between the points

(v 1 , i 1 ), (v 2 , i 2 ), is equivalent to v = E + ir, i 1 ≤ i ≤ i 2 , where r = (v 2 -v 1 )/(i 2 -i 1 ), and E = [(i 2 /(i 2 -i 1 ))v 1 -(i 1 /(i 2 -i 1 ))]v 2 .
The minimum of the product v × i, at points in the line segment, occurs at

i = -E/2r, if i 1 ≤ -E/2r ≤ i 2 , otherwise it occurs at i = i 1 or i = i 2 .
To compute the minimum power absorbed (negative of maximum power transfer) points we first compute the v×i product at all the corners between (v 0 , 0) and (0, i k+1 ). Additionally if the minimum power, absorbed in a line segment between successive corners, occurs between its endpoints, compute that product and take the overall minimum of all these products. The corner points as well as the intermediate points at which this value is the v × i product, are the maximum power transfer points.

Approximate maximum power transfer for DRS 1-ports

The power absorbed v P × i P by a DRS 1-port will be negative (power delivered positive) only in the second and fourth quadrants of the v P -i P plane. We have seen that the v -i characteristic of a DRS 1port is piecewise linear with all the straight line segments having positive slope (Corollary 13). It follows that for computing the maximum power transfer, we need only examine the portion of the characteristic lying between (0, i sc ) and (v oc , 0). Without loss of generality, we will take v oc ≥ 0, i sc ≤ 0. As mentioned before, solving a DRS 1-port for a given voltage source or current source termination is a quadratic programming problem which can be solved efficiently. A natural way of approximating the v -i characteristic is to divide a box ĩ1 ≤ i ≤ ĩ2 , ṽ1 ≤ v ≤ ṽ2 , by a grid with k 1 + 1 vertical lines corresponding to voltages and k 2 + 1 horizontal lines corresponding to currents. We then compute the port current, port voltage corresponding to the vertical, horizontal lines respectively. Successive computed points along the characteristic will not be farther than (ṽ 2 -ṽ1 )/k 1 in the v coordinate and ( ĩ2 -ĩ1 )/k 2 in the i coordinate. This fact can be used to estimate the error between the actual maximum power transfer and the computed one, as in the next theorem.

Lemma 26. Let N P be a DRS 1-port with v oc ≥ 0, i sc ≤ 0. Let (ṽ 1 , ĩ1 ), (ṽ 2 , ĩ2 ) be points in the v -i characteristic of N P at the port

P such that 0 ≤ ṽ1 < ṽ2 ≤ v oc , i sc ≤ ĩ1 < ĩ2 ≤ 0, ṽm :≡ ṽ1 + (ṽ 2 -ṽ1 ) × (m/k 1 ), m = 0, • • • , k 1 , ĩn :≡ ĩ1 + ( ĩ2 -ĩ1 ) × (n/k 2 ), n = 0, • • • , k 2 .
Let ĩm , ṽn , be the port current and voltage when ṽm , ĩn , are the port voltage and current respectively. Let the points (ṽ m , ĩm ), (ṽ n , ĩn ), m = 0,

• • • , k 1 , n = 0, • • • , k 2 , be reordered as (v j , i j ), j = 0, • • • , k 1 + k 2 -1 such that (v j , i j ), (v j+1 , i j+1 ), j = 0, • • • , k 1 + k 2 -2 are successive points along the v -i characteristic.
1. Let (v , i ) be the point in the v -i characteristic of N P between the points (v j , i j ), (v j+1 , i j+1 ).

Then

max{|v × i -v j × i j |, |v × i -v j+1 × i j+1 |} ≤ |(v j+1 -v j ) × i j | + |(i j+1 -i j ) × v j | < |(ṽ 2 -ṽ1 ) × ĩ1 |/k 1 + |( ĩ2 -ĩ1 ) × ṽ2 |/k 2 . 2.
Let the minimum value of v P × i P along the characteristic between the points (ṽ 1 , ĩ1 ), (ṽ 2 , ĩ2 ) be reached at

(v", i") with ṽ1 ≤ v" ≤ ṽ2 , ĩ1 ≤ i" ≤ ĩ2 . Then |v" × i" -min 0≤j≤k1+k2-1 {v j × i j }| < |(ṽ 2 -ṽ1 ) × ĩ1 |/k 1 + |( ĩ2 -ĩ1 ) × ṽ2 |/k 2 .
Proof. 1. Because the slope of the v -i curve is always positive, we must have |i j | > |i j+1 | and therefore the rectangle corresponding to v P × i P at points in the characteristic between (v j , i j ), (v j+1 , i j+1 ) is contained in the rectangle corresponding to v j+1 × i j and contains the rectangle corresponding to v j × i j+1 . It follows that the power absorbed at points in the characteristic between (v j , i j ), (v j+1 , i j+1 ) lies between v j × i j+1 and v j+1 × i j . Therefore,

max{|v × i -v j × i j |, |v × i -v j+1 × i j+1 |} ≤ |v j × i j+1 -v j+1 × i j | = |v j × i j+1 -v j × i j + v j × i j -v j+1 × i j | = |(i j+1 -i j ) × v j + (v j -v j+1 ) × i j | = |(v j -v j+1 ) × i j | + |(i j+1 -i j ) × v j | (since (i j+1 -i j ) × v j and (v j -v j+1 ) × i j have the same sign) < |(ṽ 2 -ṽ1 ) × ĩ1 |/k 1 + |( ĩ2 -ĩ1 ) × ṽ2 |/k 2 .
2. Let (v", i") lie in the characteristic between the points (v j , i j ), (v j+1 , i j+1 ), 0

≤ j ≤ k 1 + k 2 -2. Then |v" × i" -min 0≤m≤k1+k2-1 {v m × i m }| ≤ min{|v" × i" -v j × i j |, |v" × i" -v j+1 × i j+1 |}. By part 1 above, max{|v × i -v j × i j |, |v × i -v j+1 × i j+1 |} < |(ṽ 2 -ṽ1 ) × ĩ1 |/k 1 + |( ĩ2 -ĩ1 ) × ṽ2 |/k 2 . Thus |v" × i" -min 0≤m≤k1+k2-1 {v m × i m }| < |(ṽ 2 -ṽ1 ) × ĩ1 |/k 1 + |( ĩ2 -ĩ1 ) × ṽ2 |/k 2 .
9. Validity region and maximum power transfer for a given diode state

General DRS multiport case

The maximum power transfer problem for N P at ports P for a valid diode state (D 1 , D 2 ) is as follows:

minimize v T P i P f or N P , where v D1 = 0, i D1 ≥ 0, i D2 = 0, v D2 ≤ 0. (3)
Consider the hybrid port representation for N DP in Equation 1. Under the valid state (D 1 , D 2 ), this equation reduces to

  g D1D1 h D1D2 h D1P h D2D1 r D2D2 r D2P h P D1 r P D2 r P P     0 D1 0 D2 i P   +   J D1 E D2 E P   =   i D1 ≥ 0 v D2 ≤ 0 v P   , (4)
which is equivalent to

h D1P i P + J D1 ≥ 0 (5)
r D2P i P + E D2 ≤ 0 (6)
r P P i P + E P = v P , (7)
Therefore, the maximum power transfer problem reduces to minimize E T P i P + i T P r P P i P under (8)

h D1P i P + J D1 ≥ 0 (9)
-

r D2P i P -E D2 ≥ 0. ( 10
)
Since the matrix r P P is a symmetric positive definite matrix, this is a convex quadratic programming problem which has a unique optimum value. There are polynomial time algorithms available now for solving convex programming problems [START_REF] Vaidya | A new algorithm for minimizing convex functions over convex sets[END_REF], [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF] (see Appendix A).

If we choose to use port voltages as inputs, we have to work with a hybrid matrix in place of the one in Equation 4, where in place of the variable v P on the right, we have i P and in place of i P , E P on the left, we have v P , J P respectively.

DRS 1-port case

The important special case where N P is a 1-port has a much simpler solution. Here, the inequalities of Equation 8 are in terms of a single scalar variable i P of the form a j i P ≥ b j , or a q i P ≤ b q , taking a j , a q to be non negative. The inequalities where the coefficient is zero are feasibility conditions of the form 0 ≥ b j or 0 ≤ b q . If (D 1 , D 2 ) is a valid diode state, these feasibility conditions would be satisfied. The remaining inequalities are of the form of the form a j i P ≥ b j , or a q i P ≤ b q , taking a j , a q to be positive. For the former inequalities, we must have i P ≥ max j { bj aj }. Let i 1 P :≡ max j { bj aj }. For the latter inequalities, we must have i P ≤ min j { bq aq }. Let i 2 P :≡ min q { bq aq }. If (D 1 , D 2 ) is a valid diode state, these would not be inconsistent and it would follow that i 1 P ≤ i 2 P and the interval over which (D 1 , D 2 ) is valid would be [i 1 P , i 2 P ]. For computation of maximum power transfer for the given diode state, we need to consider two situations. Case 1. All the inequalities are satisfied strictly, i.e., i P > max j { bj aj }, i P < min q { bq aq }, but E P i P + i P r P P i P reaches a minimum. This corresponds to the usual maximum power transfer for the linear case, viz. v P = -r P P i P so that E P = -2(r P P )i P .

Case 2. Atleast one of the inequalities is satisfied as an equality, i.e., i P = max j { bj aj } or i P = min q { bq aq }.

Since N P is a DRS multiport, it has a unique solution corresponding to the value of i P for either of the above cases. The following algorithm summarizes the above discussion.

Algorithm II

Input: A DRS 1port N P and a state (D 1 , D 2 ) for N P . Output: a) The interval of i P within which (D 1 , D 2 ) is valid. b) The port current i P for which the power output -v P i P is maximum for N P .

Step 1. Construct the inequalities of Equation 8. These are of the form a j i P ≥ b j , or a q i P ≤ b q , taking a j , a q to be non negative. The inequalities where the coefficient is zero are feasibility conditions of the form 0 ≥ b j or 0 ≤ b q . If these are incorrect declare (D 1 , D 2 ) to be invalid. The inequalities where the coefficient of i P is not zero are equivalent to i P ≥ max j { bj aj }, i P ≤ min q { bq aq }, a j , a q , positive. Let

i 1 P = max j { bj aj }, i 2 P = min q { bq aq }. If i 1 P > i 2 P , declare (D 1 , D 2 ) to be invalid. Otherwise declare (D 1 , D 2 ) to be valid in the interval i 1 P ≤ i P ≤ i 2 P . Step 2. Compute i 3 P = -E P 2r P P . If i 1 P ≤ i 3 P ≤ i 2 P , output i 3 P . If not output i 1
P or i 2 P for which -v P i P is maximum. STOP.

Methods for computing port characteristic

We have seen that the number of straight line segments in the port characteristic of a DRS 1-port is the number of valid diode states (Corollary 13). It is possible to construct circuits for which the number of valid states is exponential in the number of diodes. Therefore, explicitly computing the port characteristic of a DRS 1-port in some specified interval v 1 ≤ v 2 (i 1 ≤ i 2 ) is in general of exponential complexity in the number of diodes. There are situations where the number of valid diode states of the DRS 1-port is a polynomial in k. (The extreme situation of this kind was described in Subsection 6 where the number of diode states did not exceed the number of diodes. However, we saw that a much faster algorithm was available for computing the port characteristic, in that case.) Suppose the diode state at (v 1 , i 1 ) is known or has been computed solving a quadratic programming problem. We could increase the port voltage (current) until one of the inequalities becomes an equality, as in Step 1 of Algorithm II (i.e., setting i P = min q { bq aq }). We could then change the diode state correspondingly (i.e., if the equality holds at br ar , the diode at that position changes state) and recompute the diode voltage and current inequalities in Equation 8. This needs the evaluation of r P P and E P in the Equation r P P i P + E P = v P (see below Equation 5), which can be obtained by computing two solutions of the resistive network obtained by shorting or opening the appropriate diode ports -one setting all internal sources to zero and setting v P = 1, and second, keeping internal sources active but v P = 0. The process is repeated until (v 2 , i 2 ) is reached. Similarly, starting at (v 2 , i 2 ) we could have reached (v 1 , i 1 ) by decreasing the port voltage (current).

Suppose k is the number of states between (v 1 , i 1 ), (v 2 , i 2 ), v 1 ≤ v 2 . To exactly compute the piecewise linear v -i characteristic of N P , between (v 1 , i 1 ), (v 2 , i 2 ), we need to solve purely resistive networks, with the same number of resistors as in N P , 2 k times, in addition to solving the DRS 1-port N P with port voltage (current) equal to v 1 (i 1 ).

An alternative method is suitable for non series parallel networks which are small (say edge set of size about 10 or less). We could pick diode states at random and compute their interval of validity in terms of say i P using Algorithm II, until we encounter a valid diode state. The corresponding values of v P can be calculated through the equality in the third row of Equation 4. We can take this as our initial state, increase and decrease i P and use the same algorithm to compute the interval of validity of every valid diode state (D 1 , D 2 ), and the corresponding values of v P . This would automatically compute the v P -i P port characteristic for -∞ < v P < ∞, -∞ < i P < ∞. In this case, if k is the number of valid states, we need to use Algorithm II, for say m randomly picked states and then, for the k valid states. Each such calculation involves solution of two purely resistive networks, with the same number of resistors as in N P . The expected value of m can be seen to be 2 k/ k. An advantage here is that we do not need to solve N P with some fixed input, which, as mentioned before, is a quadratic programming problem. In order to make best use of the methods outlined above, we present a preprocessing scheme in the following informal algorithm. This reduces the port connection graph G P of a DRS 1-port N P to that of a piecewise linear 1-port N L P , that has the same port characteristic at P as N P . Computation of the port characteristic of N L P when it is series parallel is discussed in Section 6. For the general case, approximate computation of port characteristic for estimating the maximum power transfer is discussed in Section 8.1.

Definition 27. A graph with more than 3 nodes is said to be 3-connected if it does not get disconnected by removal of any two nodes. A 3-connected subcomponent is a subgraph which has two nodes in common with the subgraph on the remaining edges, and which becomes 3-connected with the addiition of an edge between the common nodes. A series subcomponent is a subgraph which has two nodes in common with the subgraph on the remaining edges and which is a series combination of edges. A parallel subcomponent is a subgraph which has two nodes in common with the subgraph on the remaining edges and which is a parallel combination of edges. Algorithm (3-connected) outputs 3-connected, series and parallel subcomponents of a graph [START_REF] Hopcroft | Efficient algorithms for graph manipulation[END_REF]. It is linear time on the number of edges and nodes in the graph.

Algorithm III

Input: A port connection graph G P of a DRS 1port N P in terms of primitive multiports with v -i characteristic of each edge given. Output: (a) A graph G reduced P that is either 3connected or series parallel, with v -i characteristic for each edge other than P. (b) The port characteristic of N P .

Step 1. Check if G P is series parallel, using Algorithm (series-parallel) [START_REF] Valdes | The recognition of Series Parallel digraphs[END_REF]. If it is, output the port characteristic of N P , using Algorithm I, output G P as G reduced P and STOP.

Step 2. If G P is not series parallel, decompose it into 3connected subcomponents and series parallel subcomponents using Algorithm (3-connected). If G P is 3connected, output G P as G reduced P , compute the port characteristic of N P , directly (no simplification possible here) and STOP.

Step 3. Let G 1 be one of the 3connected subcomponents. Let v 1 , v 2 denote its terminals. Split this component from G P at the terminals v 1 , v 2 . Add a directed edge P 1 from v 1 to v 2 in the two split subgraphs. Denote the subgraph containing the edge P by G 1 P and the other by G 2 P1 . Compute the port characteristic of G 2 P1 at P 1 and treat this as the v -i characteristic of the piecewise linear device P 1 in G 1 P . Computation of port characteristic G 2 P1 at P 1 proceeds replacing P by P 1 and G P by G 2 P1 and going back to

Step 1 (see Figure 5). STOP.

Remark 4. The method suggested in Algorithm III is effective only if explicit computation of port characteristic is performed for series parallel subgraphs or for 3-connected subgraphs with a small number of diodes (say ≤ 10). If the final reduced multiport N reduced P with piecewise linear devices is a series parallel graph, even an approximate computation of the characteristics of the devices in it, can be used to compute an approximation of the port characteristic of N P (Section 7). If N reduced P has a 3-connected graph, to compute the maximum power transfer, only the approximate method of Section 8.1, can be used since the number of states would be too large. (For instance if the graph has 10 edges and each piecewise linear device has 4 states, the number of states could be of the order of 2 20 .) We saw, in Theorem 8, a method of reducing solution of multiports with piecewise linear devices to that of repeated solution of multiports with the same number of diodes. In the next section we present an alternative method using gradient descent.

Analysis of circuits with piecewise linear devices through optimization methods

Optimization methods provide a useful option for the analysis of electrical circuits. Unlike the technique described in Section 4, these methods do not depend upon the number of corners in the v -i characteristics of the devices. The following gradient descent algorithm is essentially the one available in [START_REF] Nesterov | Introductory Lectures on Convex Optimization: A Basic Course[END_REF], page 142. In the next subsection we will adapt this algorithm to the solution of networks with piecewise linear devices.

Algorithm IV

Let the search region Q be closed and convex with diameter R. Let φ(•) be the convex function to be minimized over Q. Let φ(•) satisfy the Lipschitz condition |φ(x) -φ(y)| 2 ≤ M |x -y| 2 .

To compute x such that φ(x) -min x∈Q φ(x) ≤ > 0, proceed as follows. Choose

x 0 ∈ Q, N = M 2 R 2 2 , h = M . (k th iteration) Compute φ(x k ), ∇φ(x k ) and set x k+1 = projection of (x k -h ∇φ(x k ) |∇φ(x k )|2 ) onto Q. x = x N .

Circuit analysis through minimization of functions

Consider the problem

M inimize φ(i) (11)
Ai = J, (12)
Where φ(•) is continuously differentiable, and A is the reduced incidence matrix of a graph. Let x T :≡

(x 1 , • • • , x n ), ∇φ(i) T :≡ (∂φ(i)/∂(i 1 ), • • • , ∂φ(i)/∂(i n )). The condition for local optimum is ∇φ(i) T = λ T A.
We refer to the constraints

Ai -J = 0, v = A T λ, v = ∇φ(i), (13)
as the Lagrangian form of Equation 11. It is clear that these are the constraints of an electrical network N on a graph G whose reduced incidence matrix is (A| -I) with cutset free current sources J and a single 'multiport' device with characteristic v = ∇φ(i). Thus î is a local optimum for Equation 11, iff î is the current vector part of a solution of N . For every static network defined as

Ai -J = 0, v = A T λ, v = f (i), (14)
we can create an optimization problem as in Equation 11taking f (i) :≡ ∇φ(i). If in addition the function φ(i) is convex, it can be shown that the local optimum is also a global optimum.

In the case of piecewise linear devices, f (i

) T :≡ (f 1 (i 1 ), • • • , f n (i n ))
, where f j (i j ) is described by a (continuous positive slope) piecewise linear characteristic. The function φ(i) can be taken to be Σ f j (i j )di j , where the integration is performed over some convenient interval for i j which includes the current point i of interest. In our procedure, it is not necessary to compute this integral explicitly, since only ∇φ(i) plays a role. This function would be convex because the v -i characteristic of the piecewise linear devices have positive slope, i.e., each of the functions f j (i j ) in (f

1 (i 1 ), • • • , f n (i n )) = ∇φ(i 1 , • • • , i n )
, is an increasing function. Since the network N has no current source cutsets and the other devices are piecewise linear, by Theorem 4, it has a unique solution. Thus in this case there is a unique value of i at which the local optimum occurs.

A first order gradient descent algorithm that is an adaptation of Algorithm IV for the solution of Equation 11 is given below. We will suppose that for any given i j of the piecewise linear device L j , the voltage v j is available through an oracle. This means ∇φ

(i 1 , • • • , i n ) = (v 1 , • • • , v n ) is available given any (i 1 , • • • , i n ). Let R denote the diameter of the search region, i.e., |i -i 0 | 2 :≡ Σ j (i j -i 0 j ) 2 ≤ R, Ai = Ai 0 = J. Let M :≡ max{|(v 1 , • • • , v n )| 2 }, when (i 1 , • • • , i n ) is in the search region. (This is the Lipschitz constant for φ(i), i.e., |φ(i ) -φ(i))| 2 ≤ M |i -i| 2 .) Algorithm V Gradient Descent of φ(i) under constraint A(i) = J Input: Initial current i 0 such that Ai 0 = J, diameter R, Lipschitz constant M for φ(i), Oracle for ∇φ(i), A, J, error , number of steps N = M 2 R 2 2
, step size η :≡ M . Output: î such that A( î) = J, φ( î) -min Ai=J {φ(i)} ≤ .

Repeat for k = 0 to N -1 Let θ(i k ) be the projection of ∇φ(i k ) onto the space Ai = 0.

i k+1 = i k -η θ(i k ) |θ(i k )|2 . end repeat î :≡ i N .
Apart from the call to the oracle, the main computation in each step is that of evaluating θ(i k ) from ∇φ(i k ). To project a vector E, where E T :≡ (E 1 , • • • , E n ) on to the space Ai = 0, we need to solve the problem

F ind i T = (i 1 , • • • , i n ) such that (15) i T -v T = (E 1 , • • • , E n ), Ai = 0, v = A T λ. (16)
This is the same as solving the resistive network problem with constraints Ai = 0, v = A T λ, i = I(v + E). This yields λ = -(AA T ) -1 AE and i = A T λ + E. Throughout the iterations, the matrix AA T which has to be LU factored does not change so that only one such triangular factorization is required. We sketch below the equivalence of the solution of a DRS network to that of an appropriately constructed quadratic programming problem. In the main we follow the treatment in [START_REF] Dennis | Mathematical programming and electrical networks[END_REF]. We later adapt the interior point algorithm as described in [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF] for the solution of DRS networks.

E ' ' R D -i = i RE v D RE v = v RE D v' = ' RE -i' = i' D E (a) (b)
Let N be a DRS network on graph G with edge set E D ∪ E R ∪ E E ∪ E J corresponding to ideal diodes, positive resistors, voltage sources and current sources. Let N P be the multiport that is the diode elimination multiport of N , i.e., the diodes are pulled out and across the resulting terminals we have ports. Since the diodes do not contain loops or cutsets of G, the multiport N P has every possible hybrid representation and, in particular, the Thevenin equivalent v P = Ri P + E. The solution of N is equivalent, as far as the diode currents and voltages are concerned, to that of a reduced network N reduced on G reduced with edge set P ∪ E D ∪ E Ê , with the series combination of a voltage and diode across each each port, as in Figure 6 (a).

The equations of N reduced have the form

I|I i R Ê i D = 0; v R Ê = v D ; v R Ê = Ri R Ê + Ê (17) -v D ≥ 0, i D ≥ 0, v T D i D = 0, ( 18
)
where R is symmetric positive definite. Equation 17 is the Lagrangian form of the Quadratic programming problem

M inimize 1 2 i T R Ê Ri R Ê + ÊT i R Ê (19) i R Ê ≤ 0. ( 20
)
This is a convex programming problem (see Appendix A), where one has to minimize a strictly convex function over a convex region. When the objective function is bounded from below (as shown later), such a problem has a global optimum solution, which can be computed through polynomial time algorithms which are available since the early 90s ( [START_REF] Vaidya | A new algorithm for minimizing convex functions over convex sets[END_REF], [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF]). The self concordant barrier method of [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF] can be easily adapted for analysis of DRS networks as we show below.

Next consider the problem

M aximize - 1 2 (v T R Ê - ÊT )( R) -1 (v R Ê -Ê) (21) v R Ê = -λ (22) λ ≥ 0. ( 23
)
If we set v R Ê :≡ y + Ê, v D = -λ, this expression reduces to the equations of the network which is obtained by replacing the diode of Figure 6 (a), by a device with characteristic v D i D = -µ. Interior point methods start with some solution which satisfies the above equations and move to another which satisfies it with a lower value σµ, 0 < σ < 1, in place of µ. In practice ( [START_REF] Colombo | Further development of multiple centrality correctors for interior point methods[END_REF]), we can take ρ j λ j = µ j ∀j, µ j > 0, and the µ j can all be different. Also each µ j can be replaced at the next step with σ j µ j , 0 < σ j < 1, and the σ j also can all be different. Equation 34 yields the following constraints on the incremental variables.

∆i R Ê + ∆ρ = 0, ρ + ∆ρ > 0, ∆y = R∆i R Ê , ∆y + ∆λ = 0, ∆ρ j λ j + ρ j ∆λ j = ∆µ j ∀j, µ j + ∆µ j = σ j µ j > 0,

where we have ignored the ∆ρ j ∆λ j term. If we treat ∆i R Ê , ∆i D :≡ ∆ρ as current variables, ∆y, ∆v D :≡ -∆λ as voltage variables and keep the increments small enough so that ρ + ∆ρ > 0 and σ j µ j > 0, these are the equations for the 'incremental' network in Figure 6 (b) where an incremental current or voltage variable ∆z is denoted z . Note that ∆ρ j λ j + ρ j ∆λ j = ∆ρ j λ j -ρ j ∆y j = ∆µ j = (σ j -1)µ j has the form v D = R i D + E j , where v D :≡ ∆y j = -∆λ j , i D :≡ ∆ρ j , R :≡ (ρ j ) -1 λ j , E j :≡ (ρ j ) -1 (1 -σ j )µ j .

Each iteration requires one solution of the incremental network. From iteration to iteration the change in the incremental network is only in the parameters R and E . The resistive multiport (on the left of Figure 6 (b)), remains invariant. Preconditioned conjugate gradient methods (see for instance [START_REF] Greenbaum | Iterative Methods for Solving Linear Systems[END_REF]) are very suited for such situations, the preconditioner being the factored version of the incremental network at the first step. The authors of [START_REF] Colombo | Further development of multiple centrality correctors for interior point methods[END_REF] report that the number of iterations remains more or less constant (less than 30) when the size of the quadratic programming problem is of the order of 10 5 variables and constraints, with less than ten variables involved in each constraint. These methods appear very promising for computing approximate maximum power transfer as in Section 8.1.

Preconditioned Conjugate Gradient Method (PCG)

We sketch how PCG may be adapted to DRS network analysis while using the interior point method. We begin by describing resistive network analysis. For notational convenience we will assume that we have only resistors and current sources in the network. Since DRS networks permit transformation from the Thevenin to Norton form this is a feasible assumption. For retaining sparsity, it is better to work directly with nodal analysis equations rather than Equation 35, where the dense matrix R is computed explicitly.

Let A be the reduced incidence matrix of the graph of the network obtained by omitting one row of the incidence matrix per component of the graph. We partition the columns of A in terms of resistors and current sources as A = A R |A J . The nodal analysis equations are

A R GA T R v = -A J J,
where J is the vector of current source values, the matrix G is a diagonal matrix with positive entries along the diagonal representing the conductances. Since the current sources contain no cutsets, A R has linearly independent rows, so that A R GA T R is symmetric positive definite. Even if the network is large, each row of A R contains very few (say less than 5) nonzero entries. Since each column of A R has atmost 2 entries and G is diagonal, it can be seen that the total number of non zero entries of A R GA T R cannot exceed twice the number of resistors in the network. So the matrix is sparse, the ratio of nonzero entries to the total number of entries being bounded by 2|E R |/n 2 = 10n/n 2 = 10/n, where |E R | is the number of resistors and n, the number of nodes in the graph.

Computing the product A R GA T R x requires no more than 2|E R | multiplications. There are very efficient techniques for factorizing such sparse matrices into triangular matrices in the form A R GA T R = LL T , retaining sparsity for the factors also. Solving ('back substituting') the equation LL T x = b is known to be inexpensive in comparison with the effort required for factoring. With this background let us adapt PCG described below, to DRS network analysis.

To solve Âx = b, with preconditioner M = LL T . r 0 := b -Âx 0 , z 0 := M -1 r 0 , p 0 := z 0 , k := 0. The resistance in this branch is the excess over the previous resistance level. A similar construction is possible starting from the right and reducing the voltage. As before, when the conductance reduces (moving left in this case), a parallel module, and when it falls, a series module have to be introduced.

The primitive DRS realization in (b) is by moving from left to right and in (c), is by moving from right to left. In (b) the limb containing the diode becomes active above voltage v 1 and in c) the limb containing the diode becomes active below voltage v 2 .

Figure 1 :Figure 2 :

 12 Figure 1: Basic components of a DRS network

  with a Thevenin or Norton circuit. (examples are in Figure B.7 (b) (c)).

1 ,Figure 4 :

 14 Figure 4: Connection of 1-ports according to port connection graph

  respectively. Then the v -i characteristics of N parallel P , N series P , are also piecewise linear. The corners of N parallel P belong to the set of points

1 . 2 .

 12 If the DRS 1-ports N Pj , j = 1, • • • , k, are primitive, then the v -i characteristic of N P has atmost k corners. Let each of the corners of the 1-ports N Pj , j = 1, • • • , k, lie within the the open box -kx < v < kx, -kx < i < kx. Then all the corners of the v -i characteristic of N P lie within the box -kx ≤ v ≤ kx, -kx ≤ i ≤ kx.

Theorem 24 . 1 , 1 ,P,

 2411 Let N orig P , N approx P , be the 1-ports with the same series parallel graph G P but with the original piecewise linear devices L orig • • • , L orig n and with their ( v , i ) approximations L approx • • • , L approx n , respectively. Let their v -i characteristics at port P be L orig P and L approx P , respectively. Let k + 1 be the number of edges of G P (k be the leaf nodes of the connection tree of G P ). Then L approx P is a (k v , k i )approximation of L orig P . , let L japprox P be an ( j v , j i )-approximation of L jorig P , for j = 1, 2. Let the two original 1-ports be combined in parallel (series) to result in N 3orig P , with port characteristic L 3orig and the two approximation 1-ports be combined in parallel (series) to result in N 3approx P with port characteristics L 3approx P .

P , L 2orig P.

 2orig are leaf nodes in the connection tree, then L 3orig P is the parent node and by the above argument,L 3approx P is a (2 v , 2 i )-approximation of L 3origP The number of leaf nodes of L 3orig P is 2 and the result is true in this case. If L 1orig P , L 2orig P are higher level nodes with k 1 , k 2 leaf nodes respectively, let us assume that L 1approx P , L 2approx P are their (k 1 v , k 1 i )-, (k 2 v , k 2 i )-approximations respectively. The parent node is L 3orig P and it follows that

3 PFigure 5 : 9 . 4 .

 3594 Figure 5: Simplification of G P to G reduced P

Figure 6 :

 6 Figure 6: (a) N reduced (b) Incremental network

Figure B. 7 :

 7 Figure B.7: Realization of piecewise linear devices using diodes

  where D k is a primitive device chosen appropriately for binary search.Assume that to obtain the state of L r whenL 1 , • • • , L r-1 are replaced with fixed primitive devices D1 , • • • , Dr-1 and L r , • • • , L k as before, we need to solve Π k r log 2 (s j ) circuits with L 1 , • • • , L k replaced with D1 , • • • , Dr-1 , D r , • • • , D k where D r , • • • , D k areprimitive devices chosen appropriately for binary search. Therefore, to obtain the state of L r-1 when L 1 , • • • , L r-2 are replaced with fixed primitive devices D1 , • • • , Dr-2 and L r-1 , • • • , L k as before, we need to solve (Π k r log 2 (s j ))×log 2 (s r-1 ) circuits with L 1 , • • • , L k replaced with D1 , • • • , Dr-2 , D r-1 , • • • , D k where D r-1 , • • • , D k are primitive devices chosen appropriately for binary search. It follows that to obtain the state of L 1 we need to solve (Π k 1 log 2 (s j )) circuits with L 1 , • • • , L k replaced with D 1 , • • • , • • • , D k primitive devices chosen appropriately for binary search.

  primitive devices chosen appropriately for binary search. This proves the result.Example 9. Let N be the network obtained by connecting a voltage source of value v P at the port. Let N have piecewise linear devices D 1 , D 2 , D 3 , L 4 , L 5 . Let us suppose that the corners of L 4 occur at (v 1 , i 1 ), (v 2 , i 2 ), (v 3 , i 3 ), and let the corresponding states moving from v P = -∞ to v P = +∞, be s 40 , s 41 , s 42 , s 43 . Let D 41 , D 42 , D 43 , be primitive devices which have corners at (v 1 , i 1 ), (v 2 , i 2 ), (v 3 , i 3 ), respectively and agree with L 4 . Let us call the states of D 41 , s 40 , s 41rightextended , the states of D 42 , s 41lef textended , s 42rightextended , and the states of D 43 , s 42lef textended , s 43 .

equivalently

It can be verified that this has the Lagrangian form

If we set v R Ê :≡ -λ, i R Ê :≡ ( R) -1 (v R Ê -Ê), we get the following equivalent form

Note that this is identical to Equation 17, if we set µ :≡ i D , λ :≡ -v D .

We will next show that when both Equations 19 and 24 have feasible solutions, the value of the objective function of the former is always greater than or equal to that of the latter.

We have,

where we have used the facts that R is symmetric positive definite, i R Ê ≤ 0 and v R Ê = -λ, λ ≥ 0.

Examining the Lagrangian form, we see that

, that the net power absorbed by the resistors and the voltage sources is zero.

Interior point methods for DRS networks

We adapt the log-barrier method as described in [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF], to the solution of DRS networks. The quadratic programming problem of Equation 19 is solved by instead solving, repeatedly changing the parameter µ, the barrier subproblem

and maintaining the condition ρ > 0. The Lagrangian form for this problem is

repeat

if r k+1 is sufficiently small then exit loop.

The main computational effort in each iteration, ignoring the dot products, is in the product Âp k and in the solution of Mz k+1 := r k+1 . When  = A R GA T R , We have seen that Âp k requires not more than 2|E R | multiplications and M :≡ A R G initial A T R corresponds to the resistor values at the beginning of the iteration and is available in the factored form. So solution of Mz k+1 := r k+1 is inexpensive.

Conclusion

We have presented new and efficient methods of computing, explicitly or approximately, port characteristics and maximum power transfer conditions for diode resistor source (DRS) 1-ports. We have adapted gradient descent methods to the solution of networks with piecewise linear devices and polynomial time interior point methods to the solution of DRS networks.

Appendix A. Convex Programming

A convex programming problem is defined to be the following.

M inimize φ(x) equivalently M aximize -φ(x)

(A.1)

where φ(x) is a convex function and g(x) ≥ 0 defines a convex region. For convenience, we rewrite Equation A.1 as

). Suppose the optimum occurs at x 0 and ∆x is the perturbation about x 0 satisfying g(x 0 + ∆x) ≥ 0. We must have φ(x 0 + ∆x) ≥ φ(x 0 ), i.e., ∂φ(x) T | x 0 ∆x ≥ 0, whenever g(x 0 + ∆x) ≥ 0, i.e., whenever dg i | x 0 ∆x > 0, where g i (x 0 ) = 0. Using Farkas Lemma (see for instance Section 5.8.3 of [START_REF] Boyd | Convex Optimization[END_REF]), this means ∂φ(x

The vector λ can have positive components only in the positions where ρ has zero components (complementary slackness). Note that we have assumed that it is possible to perturb the optimal solution satisfying the feasibility condition g(x) ≥ 0. (This can be shown to be true when the feasibility region has more than one point and is convex.)

These conditions can be shown to be also sufficient when φ(•) is convex (-φ(•) is concave) and the feasibility region defined by g(x) ≥ 0 is convex. (If we have two points of local optimality, the line between them must lie in the convex region. Convex functions satisfy φ(λx

Using this one can see that if φ(x 1 ) > φ(x 2 ), then local optimality would be violated at x 1 , x 2 .)

We are particularly interested in the case where g(x) :≡ Ax -b. For this case, we refer to the constraints

as the Lagrangian form of the programming problem.

Interior point method ( [START_REF] Nesterov | Introductory Lectures on Convex Optimization: A Basic Course[END_REF]) for Equation A.1, with g(x) :≡ Ax -b, would begin with the formulation including a log barrier function in the term to be optimized,

The Lagrangian form for this problem is

keeping ρ > 0 always.

The incremental version of the Lagrangian form is

A∆x -∆ρ = 0, (A.13)

Remark 5. Dennis's treatment [START_REF] Dennis | Mathematical programming and electrical networks[END_REF] of convex programming (as opposed to quadratic programming) does not appear substantially more general. It also does not appear to have an electrical interpretation. It is not clear how to bring in complementary orthogonality. However Equation A.5 is simpler if we also work with a function φ(x) :≡ 1 2 (x T P x) + E T x. If φ(x) is strictly convex, then P x is a strictly increasing function, i.e., (z -x) T P x < (z -x) T P z, z = x. In the derivation of Equation A.5, let us take x :≡ i, y :≡ P x, v :≡ y + E. It follows that v :≡ -A T λ. Since Ai ≤ 0 and λ ≥ 0, we can see that i

In the network of Figure 6 (a), if we take v = ∂φ(x), y = v -E, equivalently, x = -∂θ(y), i.e., i = -∂θ(v -E), the topological and device characteristic constraints together are equivalent to the Lagrangian form of the primal convex programming problem

or its dual

Now θ(y) is the Legendre dual of f (x) :≡ 1 2 (x T P x). We have the general inequality f (x) -θ(y) -x T y ≥ 0. It then follows that f (x) + E T x -θ(y) ≥ 0 in general and f (x) + E T x -θ(y) = 0 for optimality. This is only slightly more general than the one with a resistive multiport in Figure 6 (a). Instead of P being symmetric positive definite, P x is taken as strictly increasing without insisting on symmetry.

Appendix B. Proofs of results in Section 2.1

We need the following preliminary result for the proofs.

Lemma 28. Let N P be a multiport with devices which are either diodes or those whose v -i characteristics are continuous piecewise linear with positive slope. Let the set of diodes and ports contain no loops or cutsets. Let some of the ports be terminated by voltage sources and others by current sources. Then the resulting network N has atmost one solution.

Proof. Let the sources at the ports

) are two distinct solutions of N for the same source values. Then by Tellegen's Theorem, we must have (v j -v j ") × (i j -i j ") = 0. We consider the following partition of the devices.

Sources;

subset of diodes in which the state is the same in both the solutions; subset of diodes in which the state is different in the two solutions; devices with continuous piecewise linear positive slope v -i characteristics;

The terms corresponding to the first two kinds of branches will have either (v j -v j ") or (i j -i j ") equal to zero. It follows that the remaining terms must add up to zero. Now, in the latter two kinds of devices, if (v , i ), (v", i") are two distinct points in the characteristic, we must have (v -v")×(i -i") > 0. We therefore have a contradiction unless there are no diodes in which the state is different in the two solutions and in the last kind of device we have (v j , i j ) = (v j ", i j "). The set of diodes and ports contains no loops or cutsets and therefore the remaining devices contain both a tree and a cotree. Therefore their voltages and currents (which are the same in both the solutions) uniquely determine the voltages and currents of the diodes and ports. Thus the two solutions are identical. We conclude that N can have atmost one solution.

Informally, the circuits are built as follows. Start from the left. Build the circuit which has the given straight line characteristic. We have used a Thevenin equivalent. At the first corner, the characteristic has to change. If, as in the present example, the conductance increases, add a parallel branch with a diode in series with a resistor and voltage source. This limb of the circuit becomes active for voltage greater or equal to v 1 . (Below this level it behaves like an open circuit.) The conductance in this branch is the excess over the previous conductance level. Suppose at the next corner the the conductance decreases (i.e., the resistance increases). Add a series branch with a diode in parallel with a current source and resistor. This limb of