Alternatives to the Newton's method

[Federerer]

Hi, recently I've found interesting (and quite old) paper that mentions various modifications to the Newton's method in order to improve performance. I've been wondering if you tried some of the alternative algorithms of solving that nonlinear system in the inner loop of the _process() function ;)
Secant method might be promising, because from what I remember, when I've been profiling simulation, most of the time in inner loop is spent calculating new Jacobian matrix. So even if it converges slower, it might actually be faster?

Quasi-Newtonian methods on wikipedia
Link to the mentioned paper.

[dsharlet]

Thanks for the link to that paper, it's very interesting. I think some versions of both ideas (partial and deferred updates) presented are worth trying! Particularly the exact, serial versions of both ideas:

• I think the approximate versions aren't going to help that much. We can evaluate the Jacobian, computing it via finite differences would also be expensive, and I also am pretty sure this would cost a very noticeable amount of numerical stability.
• I think our problem sizes are too small (and solved too frequently) for parallelism to be relevant, and I think SIMD is orthogonal to these methods for our use case.

I think the biggest challenge could be that numerical stability is already an issue for some circuits, but I'm not sure that these ideas (exact variants at least) will actually make this worse. They might not hurt at all.

This is really making me wish I followed through on my attempts at issue #97 (refactoring the simulation code), which I think would make it much easier to experiment with these ideas.

[Federerer]

So, I did some testing - tried to recalculate the derivatives only if calculated delta changed significantly (as defined in "done" condition) and the positive thing is that it works just fine, the negative is that it's 4x slower 😫 Well, it's faster in case of non-optimized version when we are not caching the intermediate expressions as a local variables, and we can't do that when calculating the derivatives conditionally. But the regular "cached" version still performs better, as the expressions are highly repetitive in most cases, so caching speeds things up more significantly than conditional calculation. In one example I checked how many times we are calling an expensive Math.Log function and it was 6 times in case of "cached" version and 24 times in "conditional" one. Even if we are saving some (usually 50 %) derivative calculations in second and further iterations it's still less than having to calculate 4 times more "heavy" functions in the first iteration.
Here are some examples of generated code in those 2 cases:
https://gist.github.com/Federerer/dce0fa3e09d23c9c6065b90a4cedd945
The second one is definitely longer than it has to be as I have to disable my "Inline Variables Used Once" visitor, as it's a little bit naive implementation currently and doesn't support scopes. 😁