Re: [Help-gnucap] gnucap speed

[al davis]

On Friday 22 July 2011, Ramiro Aceves wrote:
> On gnucap: 0.719 seconds
> Same circuit on QUCS: 65 seconds.
> 
> I do not understand why there is such tremendous  time
> difference. Same  stop time, same step size. Gnucap goodness
> or Qucs badness....

I knew Qucs was slow on large circuits, but that circuit is 
pretty small.

There is a big difference in the algorithms.

Qucs uses very simple text-book algorithms, without 
optimization.  Gnucap is highly optimized.  NGspice is somewhere 
in between.

Qucs is really designed for adademic size problems where speed 
is not an issue.  Gnucap is really designed for very large 
problems, where even Spice is too slow.

To Qucs credit ..  If you try to read the code, as a beginner, 
you are likely to understand it.  I think they considered this 
to be important.

Typically, speed benchmarks show Gnucap speed to be a linear 
function of circuit size, NGspice speed to be a quadratic 
function of circuit size, Qucs speed to be a cubic function of 
circuit size.  I have experimented with some algorithms with 
speed as bad as an exponential function of circuit size.

To look deeper, let's look at the matrix solver.  All of them 
use a similar method, based on LU decomposition or Gauss 
Elimination.

The Qucs solver is classic.  Look at the code and you will see.  
It's the classic LU solver, straight out of any text on 
numerical analysis.  If you have every studied numerical 
analysis, you would know that LU decomposition speed is 
"O(n^3)", proportional to the size of the matrix cubed.  Look at 
the code, you will see the classic 3 nested loops, the classic 
square array.  (storage needs are quadratic .. "O(n^2)".

Some "homework grade" simulators use "expansion by minors" to 
solve the matrix .....  exponential time.

Real circuits result in most of the matrix entries being zero.  
If you care about space or speed, storing and manipulating these 
zero entries is a waste, so Spice uses a sparse matrix solver, 
that only stores and solves non-zero numbers.  This cuts both 
time and storage way down.  It is heuristic, so in theory it 
could be as bad as O(n^3), but usually isn't.  That difference 
in time you see is in all of those operations that multiply by 
zero or add zero.  Typically, it ends up being about O(n^2) 
because of the analysis time.

Gnucap carrys this further, by a simpler analysis that takes 
linear time, and further heuristics to not solve the whole 
matrix every time, and not dealing with all components every 
time.  One example of this is that resistors are solved only 
once, and never looked at again for the entire transient run.

I would love to have a way to run gnucap under the Qucs GUI.  
The Qucs GUI shows where they put their effort.  It's really 
nice!

This might happen.  ..  A Gnucap plugin to read and write the 
Qucs format, and a wrapper to use Qucs devices (the special RF 
ones). ....  and there it is.