Part way thru the elimination of unknowns we pause to consider the cost of this calculation.
Certain points have beeen retired and are no longer mentioned in equations for the remaining unknowns.
The retired points are partioned into holes which are sets of points that were initially transitively linked by adjacency.
For each such hole there will be unretired points that are adjacent to some retired point of the hole.
We call these unretired points the fronteer of the hole.
The equation for each point on the fronteer will involve all other points of the same fronteer.
We see that the space and time cost of this scheme is proportional to the square of the size of the fronteer.
We proceed by pushing back the fronteer as we retire new points.
The cost of each retirement is proportional to the size of the fronteer that the point belonged to.
There may be several holes, each growing until they meet and merge.
This affords opportunity for parallelism.
In the trivial linear mesh dealt with here, the hole is some left portion of the sequence of mesh points.
The routine solve retires points by consecutive index. Other orders might be strategic.
Given the way that the routine vg numbers the mesh points, the routine solve
produces just one hole which grows until all points are retired.
The code (solve (vg 4 25) ge) is slow for the fronteer of the hole typically has 25 members whereas the same problem is solved by (solve (vg 25 4) ge) with a fronteer of only 4 points.
Order of retiring points should pay attention to mesh layout.
Truncation Tricks
The coefficients in the equations for the unretired points that refer to other points is a direct measure of how much the ultimate value at one point depends on the other.
These values may become so small that the may be ignored because of one or two facts:
- They may produce insignificant augends as when a + b = a exactly in floating point,
- Other approximations in the simulation dominate the effect described by the term.
The first reason can well be automated,
The second probably requires algorithms with access to other factors in the simulation.
Equations are stiff when these coefficients are large.
The equations are then asked to carry information past many mesh points.