The Designer's Guide Community Forum

The Designer's Guide Community Forum
https://designers-guide.org/forum/YaBB.pl
Simulators >> Circuit Simulators >> Time complexity SPICE simulator (Landau notation)
https://designers-guide.org/forum/YaBB.pl?num=1191598704

Message started by Visjnoe on Oct 5^th, 2007, 8:38am

Title: Time complexity SPICE simulator (Landau notation)
Post by Visjnoe on Oct 5^th, 2007, 8:38am

Dear all,

I cannot find this through web search (at first glance): what is the time complexity (Landau notation) of a typical SPICE simulator. I would say it is O(N^2) because of the size of the equations matrix and the time it takes to solve this.

Is this correct? Or are clever matrix solvers applied which reduce it to O((N)logN) or even O(N)?

Any insight welcome!

Kind Regards

Peter

Title: Re: Time complexity SPICE simulator (Landau notati
Post by byang on Oct 5^th, 2007, 8:54am

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

Title: Re: Time complexity SPICE simulator (Landau notati
Post by Stefan on Oct 5^th, 2007, 10:34am

A very interesting question !
Does anyone know of a good comparison to other simulators, like mixed signal ones
(sure, only models with linear equations might be comparable...)

Regards,
Stefan

Title: Re: Time complexity SPICE simulator (Landau notati
Post by aldavis on Oct 16^th, 2007, 11:27pm

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.