Re: gnucap speed

Great explanation, Al!

> 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.
>
>
> _______________________________________________
> Help-gnucap mailing list
> [email protected]
> https://lists.gnu.org/mailman/listinfo/help-gnucap
>

-- 
David Fang
http://www.csl.cornell.edu/~fang/
http://www.achronix.com/