Page 93 - Compact Numerical Methods For Computers

82 Compact numerical methods for computers
then Gauss elimination and back-substitution can be carried out exactly as in
algorithms 5 and 6 if every array reference is made with A[ , ] replaced by
A[q[ , ]. However, a simplification occurs in the interchange step 3, which can
be replaced by a simple interchange of the row indices. That is, at step j, if the
pivot is in row q [k] q[j], or k j, then the indices are simply interchanged rather
than the entire rows. However, all array access operations are complicated.
Some overall increases in efficiency may be obtained if we take over the
compiler or interpreter function in accessing two-dimensional arrays. That is, we
store the working array A which is m = (n + p) by n in a single vector a of mn
elements. We can do this columnwise, so that
A[i ,j] = a[n * (j – 1) + i] (6.41)

or row-wise, so that
A[i, j] = a[m * (i – 1) + j]. (6.42)
These translations offer some simplifications of the elimination and back-
substitution algorithms. In fact, the row-wise form (6.41) is more useful for
elimination where the index of an element is simply incremented to proceed
across a row of the coefficient matrix. For back-substitution, we need to form
matrix-vector products which oblige us to access array elements by marching
simultaneously across rows and down columns. Implicit pivoting is also possible
with a one-dimensional storage scheme. This adds just one more item to those
from which a method must be selected.
It is probably clear to my readers that I have already decided that simplest is
best and intend to stick with algorithms 5 and 6. My reasons are as follows.

(i) Despite the elegance of implicit pivoting, the extra index vector and the
program code needed to make it work are counter to the spirit of a compact
algorithm.
(ii) The implicit interchange only gains in efficiency relative to the direct method
if an interchange is needed; this is without counting the overhead which array
access via q implies. But in many instances very few interchanges are required and
the whole discussion then boils down to an argument over the likely number of
interchanges in the problem set to be solved.
(iii) In coding Gauss elimination with back-substitution and the Gauss-Jordan
reduction with various of the above choices, S G Nash and I (unpublished
work) found that the implicit pivoting methods were surprisingly prone to ‘bugs’
which were difficult to discover. This applied particularly to the one-dimensional
storage forms. Most of these errors were simple typographical errors in entry of
the code. Since it is hoped the algorithms in this book will prove straightforward
to implement, only a direct method has been included.

6.4. COMPLEX SYSTEMS OF EQUATIONS
½
Consider the system of equations (where i = (–1) )
(Y+iZ) (u+iv) = g + ih. (6.43)