[Gnucap-devel] The incremental matrix update bug, and its fix

[al davis]

In case anyone is interested ..

Gnucap uses an incremental update scheme, where the matrix is 
cached, and each iteration updates it rather than rebuilding 
it.  This is called a "low rank update".  Then the solver does 
a partial solution, producing the next version of the 
decomposed matrix.  This is one of the techniques used in the 
so-called "fast-spice" simulators.  Combined with other changes 
that work together with it, it provides significant speed-up on 
large circuits.

This method first appeared in ACS, the predecessor to gnucap, 
long before the "fast-spice" simulators existed, so it is prior 
art not subject to later patents.

The idea is that it keeps the old matrix, and adds a correction 
to it where there are changes.  These corrections are marked 
and used to find an optimized algorithm to solve only the 
changed parts of the matrix, giving an updated set of "LU" 
matrices.  At all times, the system looks like a variant on the 
Crout method of LU decomposition.

The system works well when updates are small.  In theory, there 
could be an increase of round-off error.  In practice, there is 
essentially no increase when the updates are small.  When 
updates are large, a problem is flagged and it does a complete 
rebuild and solution the traditional way.  This flagging is 
done based on the existence of certain conditions that are 
likely to cause trouble.  There is no actual error check.

The bug is that one obvious case, when a transient step is 
rejected, did not force a rebuild.  This causes incremental 
update to continue from a very wrong matrix of a convergence 
failure and rejected step. The matrix has the failed values, 
but the desired values are from one step back.

Most of the time, it did not cause problems, because the 
correction mechanism still works, unless the correction is 
large enough to cause round-off errors.

The bug was introduced during an update of time step control, so 
0.35 has the bug but 0.34 and older versions do not.

The fix is to force a rebuild whenever a step is rejected, which 
is the way it was originally designed.