## Re: [Qucs-devel] Offer to help concerning the numerical difficulties

 Re: [Qucs-devel] Offer to help concerning the numerical difficulties From: Soeren D. Schulze - 2013-07-06 08:38:46 You're absolutely right. There are bottlenecks in Qucs all over the place. First of all, though, I'd like to fix the convergence problems because a fast but divergent solver isn't really worth anything. BDF methods are usually fastest (when implemented right), but they're also a bit fragile, so I think we should provide a one-step method, too. Apart from the linear solvers, the first bottleneck that caught my attention is the application of traditional Newton's method, which entails recomputation and re-decomposition of the Jacobian in every step. We should really use simplified Newton's method. While the theory says that traditional Newton's method has faster convergence, trading a few extra function evaluations (at most O(n^2), probably more like O(n)) for O(n^3) operations seems like a good deal. OK, applying some better matrix methods may reduce the latter to O(n^2), but the point still holds. And if we use one-step methods, we have to use simplified Newton's method anyway. The second bottleneck seems to be the polynomial interpolation to get the coefficients for the multi-step methods. It would be interesting to profile the percentage of the computation time that this actually takes. The cost is independent of the matrix size, but because it needs to be done in every step and upon every rejection, I think it's not negligible. But before changing anything here, it should be checked what well-tested codes like DASSL/DASPK do. Sören Am 04.07.2013 04:31, schrieb al davis: > On Tuesday 02 July 2013, Soeren D. Schulze wrote: >> To get it really fast (in case of large circuits), we should >> use some state-of-the-art iterative linear solver, such as >> GMRES. That is > > To get it really fast, you need to fine tune everything. Fast > matrix eval, fast model eval, watch cache hits, which functions > to inline, step control, know when you can take shortcuts, how > data is stored, .... > > Using a packaged library solver won't get you there. > > About 10 years ago, there were lots of papers about "Krylov > subspace methods", all quoting huge improvements over spice for > some special kind of circuit. They all missed the point. > > I have some large benchmarks for Gnucap ... One, with 589825 > nodes. Gnucap transient analysis takes about a minute with > default settings. NGspice takes over 8 hours to do the same. > > In Gnucap, only about 20% of that time has to do with the > matrix. This is a linear circuit. For a nonlinear circuit, the > matrix portion would be even less percentagewise, because of > more time in model evaluation. > > I can make it faster by changing the options to tradeoff some > accuracy for speed. The numbers I stated here are for the > default "spice accuracy with improved robustness". > > Having said all that .. I am curious how some other methods > perform in this situation. The matrix solver is one file in > gnucap. If you want to try another, I would really like to see > the results, so I will help you do it.