[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-gnucap] gnucap speed
From: |
al davis |
Subject: |
Re: [Help-gnucap] gnucap speed |
Date: |
Fri, 22 Jul 2011 10:43:50 -0400 |
User-agent: |
KMail/1.13.7 (Linux/2.6.32-trunk-amd64; KDE/4.6.4; x86_64; ; ) |
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.