Peter,

I remember some people say that it is n^1.4 or something like that.

In my experience, it depends on the circuit type. For some circuits with "sparse" connections and not that many "loops", the Spice simulation complexity may be close to n. However, for circuits with mesh-like connection, for example, power grid, the complexity may be close to n^2. For package model, it could be even higher.

Yes, there is advanced circuit matrix solver that can handle even the mesh-like connections and get close to O(n) complexity. Do you have a circuit with high Spice time complexity?

Regards,

Baolin Yang
Gemini Design Technology, Inc.
www.gemini-da.com

It's not O(n^1.4).  Maybe if you repeat it often enough it becomes true, but when I see that claim I question the credibility of the whole paper.

Theoretically, it is O(n^3) but in practice, mainly due to sparse matrix techniques it is better than that.

Think of it as a polynomial ...  A*n^3 + B*n^2 + C*n + D.

Suppose A=.001, B=1, C=1000.  It will appear to be linear for small circuits.  At some point it might actually look like n^1.4.  You get coefficients like this with complex models, like a BSIM4.  With simpler models, the C term is smaller.

For benchmarks I have run, with mixed large circuits, Spice usually comes out at O(n^2).  I have seen worse.  I have not seen Spice act better with large circuits, although it can appear better with small circuits, where the "C" term dominates.  For a fully connected mesh, it is cubic.

Regarding other simulators  ..  With the same benchmarks, Gnucap usually comes out at O(n) with Spice accuracy and generality.  I have some experimental algorithms that appear to be better than O(n), using event queues and caching, still with Spice accuracy and generality.  In more detail, speed in gnucap is linearly related to the circuit size, times quadratically related to the average number of connections per node.  So, a fully connected mesh can become cubic, just like Spice.

By a "fully connected mesh" I mean that every node has a connection to every other node.  This is not a practical circuit.  Mesh-like circuits like power grids have a small number of connections at each node, giving a very reliable O(n^2) in Spice, O(n) in gnucap.

The reduced accuracy "fast spice" simulators should do better than O(n) because of the use of queues, caching, reduced accuracy, and reduced generality.  I don't have access to any of them, so I don't have numbers.  I would like to see them.