Re: [Gnucap-devel] [Help-gnucap] subcircuits and speed

[Geordie McBain]

2012/2/9 al davis <address@hidden>:
>> <address@hidden> wrote:
>
> It's not the number of nodes, but rather how they are ordered.

Ah.  I thought I must be missing something obvious.  I can see how
ordering could easily be an issue.

> In this case, the ideal ordering would produce a tridiagonal
> matrix, which can be solved in linear time.  Gnucap's solver
> does solve a tridiagonal matrix in linear time.
>
> If you look at the code,

Which I should, but confess haven't yet.

> it's fairly obvious that Gnucap's node
> ordering algorithm is a stub, a place holder with intent to
> replace it with something better.  I had done some work on it,
> unreleased, using a simple depth-first-search that worked quite
> well, but never actually integrated it.
>
> What Felix is proposing is to do another ordering post-
> expansion, where the post-expansion ordering would in effect
> bring some subckt nodes down into their parent.  I agree that it
> should be available as an option, but there are disadvantages,
> which I can go into on the developer list.

O.K.

> In this case, the flat version is clearly faster, but I have
> other examples where the hierarchical version is faster.
>
> I'm curious about another variant ..  to use subckts, but to
> make the internal node an external node.

Like so?

%<---
TELEPHONE LINE (Holt 1963, p. 490)

.SUBCKT SEGMENT inlet internal outlet
R inlet internal 0.01220703125
L internal outlet 9.1552734375e-06
Y outlet 0 3.0517578125e-09
C outlet 0 4.57763671875e-11
.ENDS

Vg 0 1 AC 100
Rg 1 2 300
X1 2 3 4 SEGMENT
X2 4 5 6 SEGMENT
X3 6 7 8 SEGMENT
...
X32767 65534 65535 65536 SEGMENT
X32768 65536 65537 65538 SEGMENT
Rr 65538 0 200

.PRINT AC VM(2) VP(2) IM(Vg) IP(Vg) VM(Rr) VP(Rr) IM(Rr) IP(Rr)
.AC 795.774715459 > tlh2.32768.dat
.END
--->%


>  I expect this should run as fast as the flat version.


Well, my preliminary investigations indicates that in fact it runs
significantly faster that the flat version.  It has cured the cubic
problem,  and now seems to be quadratic, like the flat version, but
for the same number of segments, your suggestion is much faster.
  These are the times in seconds reported by the Bash built-in for
"time gnucap -b $CKT", and n is the number of segments (the total
number of nodes is 2n+2).

n     flat            hier.         exposed

2     0.008     0.012   0.014
4     0.008     0.008   0.012
8     0.009     0.008   0.009   
16    0.011     0.009   0.009   
32    0.015     0.010   0.017   
64    0.023     0.014   0.014   
128   0.043     0.033   0.016   
256   0.087     0.177   0.025   
512   0.248     1.348   0.048
1024  0.836     9.161   0.104
2048  4.160    69.799   0.251
4096 20.324   584.442   1.109

At this point I lost patience with the old .subckt implementation
(with its hidden internal node) and pulled it from the race.

n     flat      exposed

 8192   86.470    6.696
16384  364.241   26.334
32768 1415.092  110.479

I'll continue running this out a bit more, but I think it clearly
demonstrates that your fix has not only (a) changed the order of
complexity from cubic to quadratic, but also (b) outpaced the flat
version by an order of magnitude.

Thanks very much!

Geordie McBain