Nonlinear equation solvers in SPICE simulators

Question

We have an assignment at the Parallel processing class, the target is to implement a Non-linear Equations solver on cuda based on Newton Raphson method and to interface this solver with an application that deals with nonlinear set of equations. We wanted to interface our solver with circuit simulators. We have picked up an open source simulator and every time the simulator is performing a DC operating point simulation it will invoke our cuda code. At this point we wanted to compare the performance of our solver against solvers implemented in other circuit simulators such as

• LTspice
• Ngspice
• Qucs

And also other software solvers e.g. Matlab optimization toolbox

We have tested these solvers against a circuit [which should map to a huge set of nonlinear eqns.]

The circuit netlist is generated by a script where the number of the nodes is given. We have formulated the set of nonlinear equations governing the above circuit as the following

The unknowns x[i] in this set of equations are the voltage nodes and the current at each resistor

We have managed to write this as a matlab function to test this circuit against matlab nonlinear solver algorithms featured in the optimization toolbox.

function F = non_linear_diode(X)
% Len(x) is always even 2*d
d = length(X)/2;
F = zeros(1, d*2);
i = 1e-3;     % Current source magnitude
r = 50;       % Resistors value
c1 = 1e-15;   % Diodes I_s
c2 = 0.0258;  % Diodes N*V_th

F(1) = X(1) - X(2) - i*r;
F(d) = X(d) - X(d+1) - X(2*d)*r;
F(d+1) = i - c1*(exp(X(2)/c2) -1) - X(d+2);

for ii = 2:(d -1)
    F(ii) = X(ii) - X(ii+1) - X(ii+d)*r;
    F(ii+d) = X(ii+d) - c1*(exp(X(ii+1)/c2) -1) - X(ii + d + 1);
end
F(d*2) = X(2*d) - c1*(exp(X(d+1)/c2) -1);
end

We have also written a script to generate Spice netlist for this problem

def gen_ckt(num):
    ret = ""
    for i in range(1, num):
        ret += 'R'+str(i)+" "+str(i)+" "+str(i+1)+" 50\n"
        ret += 'D'+str(i)+" "+str(i+1)+" 0 DI1N4004\n"

Where DI1N4004 is our diode model defined in the netlist. When testing the above solvers against the problem with 70,000 nodes i.e. 140,000 equations and unknowns

• Matlab runs out of memory
• Qucs takes forever
• All the spice based solvers somehow solved this problem in less than 2 seconds

We actually have no idea how spice solvers managed to avoid this memory problem, and even when testing this problem against fewer number of unknowns e.g. 3,000 the spice solvers always outperform matlab and qucs. Though as mentioned in [1] [2] [3] spice uses the damped Newton-Raphson approach to solve circuits with nonlinear components which is the same as all the solvers mentioned above

• Matlab Fsolve : dogleg method [Newton + Trust-region + steepest decent] [4]
• Qucs : damped Newton-Raphson [5]

My questions are

• How spice managed to solve such a huge system of nonlinear equations quickly and without running out of memory ? is it exploiting the circuit structure making use of the repeated elements ?
• Is this example fair enough ? i mean do we need to consider more practical circuits ? and if so can any one give an example for a circuit(s) where DC operating point simulation might be the bottleneck of the simulation time ?
• In [6] the authors mentioned ISCAS85 benchmark circuits should we consider these circuits in our tests ?
• Is the DC operating point the simulation type we should be targeting ? i mean should we focus to interface our solver to other types of simulations e.g. the transient analysis ?

References

1 : http://www.ni.com/white-paper/5808/en/

2 : http://www.ecircuitcenter.com/SpiceTopics/Overview/Overview.htm

3 : http://www.electronicdesign.com/boards/taking-peek-under-hood-your-spice-circuit-simulation-engine

4 : https://www.mathworks.com/help/optim/ug/fsolve.html

5 : http://qucs.sourceforge.net/tech/node16.html

6 : http://www.mos-ak.org/bucharest/presetnations/Lannutti_MOS-AK_Bucharest.pdf

Answer 1

How spice managed to solve such a huge system of nonlinear equations quickly and without running out of memory ?

Google sparse matrix solver.

A good SPICE very likely defaults (or knows when to switch to) a sparse matrix solver, since large circuits typically produce sparse matrices (each node connects to only a small fraction of the branches) it would be an obvious optimization to use (or have available) a sparse matrix solver in a SPICE. Even Nagel's original 1975 report (Thesis?) on SPICE discusses using sparse matrix methods.

Matlab certainly has a sparse matrix solver available, but you probably have to invoke it explicitly.

Qucs may not have this capability, or it might not be implemented particularly well, because it's a relatively raw open source project and its developers might not have got to the point of testing it on anything bigger than a toy problem.

(Hat tip to @jonk for the link to the Nagel report)

Is this example fair enough ? i mean do we need to consider more practical circuits ?

I would think you want to demonstrate your solver on a wide variety of different types of circuits. You probably want to consider circuits that are known to produce ill-conditioned matrices. Positive feedback circuits also often produce difficulties for non-linear solvers.

and if so can any one give an example for a circuit(s) where DC operating point simulation might be the bottleneck of the simulation time?

I would expec this to be common in any ill-conditioned circuit when setting up an AC simulation.

Is the DC operating point the simulation type we should be targeting ? i mean should we focus to interface our solver to other types of simulations e.g. the transient analysis ?

The other main simulation types (ac and transient) only require linear solvers. The AC simulation explicitly is about small variations about the operating point, so that the circuit can can be considered linear by perturbation theory. The transient solver linearizes the circuit at each time step, but re-calculates the local linear equivalent circuit for each time step. So if you're trying to demonstrate a non-linear solver, the DC solver is the one to demonstrate.