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