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

[al davis]

I am cross-posting this to the developer list, in hopes of 
moving the follow-ups there.  I like to keep the help list 
newbie friendly.

On Tuesday 07 February 2012, Geordie McBain wrote:
> Yes, I was wondering about that. In this very simple network
> topology, the equations can be phrased tridiagonally, and so
> admit solution by the algorithm of Thomas, which requires
> linear time, but I wasn't sure how that generalized to the
> arbitrary topologies admitted by Gnucap, at least without
> internal renumbering as suggested by the other poster, and
> also how reasonable it was to expect a general code to
> recognize a relatively trivial special case. Presumably a
> completely connected network yields a full matrix, which
> can't be solved in less than cubic time, can it?
> 
> (I'm yet to convince myself that halving the number of nodes
> can change the index of complexity, but as you assure us,
> I'll ponder it further.) On Feb 7, 2012 6:11 PM, "al davis"
> <address@hidden> wrote:

It's not the number of nodes, but rather how they are ordered.

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, 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.

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.  I expect this should 
run as fast as the flat version.