2012/2/9 al davis <[email protected]>: >> <[email protected]> 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 _______________________________________________ Gnucap-devel mailing list [email protected] https://lists.gnu.org/mailman/listinfo/gnucap-devel
