% [editors note, Eric Grosse]
% On my system, the tables come out blank unless I change
% \font\sm=cmbx10 at 7pt to \font\sm=cmbx7
\magnification=1200
\baselineskip=15pt\parskip=4pt\parindent=1truecm
\font\sm=cmbx10 at 7pt
\def\textref#1{#1}
\def\sect#1{\bigskip\centerline{\bf #1}\medskip}
\def\set#1{\left\{#1\right\}}
\def\mod{\hbox{mod}}
\newcount\qn\qn=0
\def\query#1{\global\advance\qn by 1 \footnote{${}^{\the\qn}$}{#1}}
\newcount\equnumb % ........count equation numbers
\equnumb = 0
\def\eq{\global\advance\equnumb by 1 \eqno(\the\equnumb)}
\def\Goliath{{\bf Goliath}}
\def\Fortran{{\bf FORTRAN}}
\centerline{\bf \Goliath: A Software System for the Exact Analysis of}
\centerline{\bf Rectangular Rank-Deficient Sparse Rational Linear Systems}
\bigskip
\centerline{by}
\centerline{Peter Alfeld\query{Please address correspondence to this author} and David J.~Eyre}
\centerline{Department of Mathematics}
\centerline{University of Utah}
\centerline{Salt Lake City, UT 84112, U.S.A}
\centerline{801-581-6842 or 801-581-6851}
\centerline{alfeld@science.utah.edu}
\bigskip
\sect{1. Introduction}
This paper is a User's Guide of the \Goliath{}\query{We chose the name
\Goliath{} (= {\bf G}enerally {\bf O}btainable {\bf LI}near system {\bf
A}nalyzer and {\bf TH}eorem Prover) because of the program's great
power. We {\it analyze\/} linear systems since we do more than just
solve them. The analysis is done in exact arithmetic, so the results
obtained constitute a proof regarding the properties of the linear
system under consideration, rather than ``numerical evidence''. Like
it's biblical namesake, the program is adept at handling large and
difficult opponents (problems), and clumsy when it comes to dealing
with small opponents. We are not trying to allude to some David who
might find a bug and strike our program down.} package.
The details of its operation,
and numerical experience with the package, are described elsewhere. Given a
(typically large and sparse) rational linear system $$AX=B\eq$$ where
$A$, $X$, and $B$ are $m \times n$, $n\times p$, and $m\times p$
matrices, respectively, \Goliath{} accomplishes the following tasks in
{\it exact} arithmetic:
\bigskip
\item{1.} Determination of the rank of $A$.
\item{2.} Identification of row dependencies. If the $i$-th equation is identified as linearly dependent
then it can be written as a linear combination of the {\it preceding} $i-1$ rows.
\item{3.} Calculation of a basis of the null space of $A$.
\item{4.} Solution of the linear system $(*)$.
\bigskip
\Goliath{} is designed specifically for the analysis of large and
sparse linear systems \textref{(1)}. For small dense linear systems it is not
competitive e.g., with Algorithm 641\query{J\"orn Springer, {\bf
ALGORITHM 641, Exact Solution of General Integer Systems of Linear
Equations}, Collected Algorithms from ACM}, although of course it can
analyze such systems also.
\Goliath{} proceeds by transforming the given rational linear system
into an integer system, and then solving that system modulo an appropriate number of
suitable prime numbers. The solution of the linear system or the null space are then
reconstructed via the Chinese Remainder Theorem. Internally, numbers are represented
in {\it mixed radix form} by their residues with respect to the various primes. Specifically,
let $p_1$, $p_2$, $\cdots$, $p_N$ be given distinct primes, $P = \prod_{i=1}^Np_i$ and let $z$ be an integer
in the interval $[0,P-1]$. Then $z$ is defined uniquely, and defines uniquely, a set of residues
$q_i$, $i=1,\cdots,N$, i.e.,
$$z = q_i \mod p_i,\quad i = 1,\cdots N.\eq$$
Moreover, $z$ can be written uniquely as
$$z=\sum_{j=1}^N \gamma_j \prod_{i=1}^{j-1} p_i.\eq$$ The $\gamma_j$ are the {\it mixed radix coefficients}.
However, on output, all numbers
are represented in {\it fixed radix form} with respect to a user specified basis $\beta$.
Thus the integer $z$ may be written as
$$z =\epsilon \sum_{i=0}^d \alpha_i \beta^i\quad\hbox{where}\quad 0\leq i\leq\beta-1\quad\hbox{where}\quad
\epsilon\in\set{-1,1}.\eq$$
The base $\beta$ must be such that its square does not overflow an integer word.
Internally, fixed radix numbers are stored in INTEGER arrays in the sequence
$$\epsilon(d+1), \alpha_d, \alpha_{d-1}, \cdots, \alpha_0.$$
Throughout the remainder of this guide we will use the following linear system as
an illustrative example:
$$\pmatrix{\xi & \eta & 0 \cr
0 & \xi & \eta \cr
\xi & \xi + \eta & \eta \cr
\xi & \eta-\xi & - \eta \cr}
\pmatrix{x_1 \cr x_2 \cr x_3 \cr } =
\pmatrix{\xi+\eta \cr \xi+\eta \cr 2(\xi+\eta) \cr 0 \cr}\eq$$
The third and fourth equations are the sum and difference,
respectively, of the first and second equation. Thus the rank of the
matrix is 2 and the null space is 1-dimensional. A particular solution
of the linear system (although not necessarily the one found by
\Goliath) is $$x_1 = x_2 = x_3 =1.\eq$$ The null space is spanned by the
vector defined by $$x_i = \left(-\xi\over\eta\right)^i,\quad
i=0,1,2.\eq$$
\sect{2. Input Files}
\Goliath{} requires an input integer file, but otherwise uses no auxiliary files.
It has a built-in facility to transform a rational system into an integer one.
Input files describing the linear system must be of one of three types:
\smallskip
\item{1.} {\bf Single Precision Rational.} Table 1 lists this input file for
$\xi = 1$ and $\eta=2$.
The first line of the file
must contain: $m$, $n$, $p$, $\phi$, where $\phi$ is the number of
non-zero elements in $A$ and $B$. The elements of $A$ and $B$ can be
thought of as being stored in an augmented work array $W$. Thus
$a_{ij}$ is stored int the $(i,j)$ position of the work array, whereas
$b_{ij}$ is stored in the $(i,n+j)$ position of the work array. For
each non-zero entry of $W$, say $w_{ij}= p_{ij}/q_{ij}$, there must be
a four-tupel beginning in a new line, and containing $i$, $j$,
$p_{ij}$, and $q_{ij}$. There must be no blank lines.
\item{2.} {\bf Arbitrary Precision Rational.} Table 2 lists this input file for our the above example, with $\xi =2^{-40}$ and
$\eta = 3^{-35}$.
The first line of this
file is identical to the first line for Single Precision Rational
files. For each non-zero entry of $W$ there must be a line
containing $i$ and $j$, followed by one one or more lines each for
$p_{ij}$ and $q_{ij}$. Both the numerator and denominator can be
written as string of arbitrarily many\query{Actually the digit count
is limited to 1000 in the current version of \Goliath. To change that
number the PARAMETER MAXC in SUBROUTINE MPREAD must be changed
appropriately.} digits, terminated by a dollar sign. Each line must
not contain more than 80 characters. A minus sign switches the sign of
the integer (numerator or denominator). Any characters other than
digit, minus, or dollar sign are ignored by the program.
The reason for the great flexibility in the arbitrary precision
rational file is not so much functionality but necessity. In order to
be able to process arbitrarily large numbers from various sources it
should be possible to have arbitrarily many digits as input written
over several lines. The input routine does some simple character
processing and skips over all characters other than those relevant for
expressing a multiple precision integer.
\item{3.} {\bf Arbitrary Precision Integer.} If the input file is rational, \Goliath{} first generates an
equivalent INTEGER file. The user may supply such a file directly.
It contains the non-zero integer entries in {\it fixed radix
notation\/}. The first line of the file contains $m$, $n$, $p$,
$\phi$, and $\beta$, where $\beta$ is the basis of the numbers on {\it
Input}. It may be different from the basis that is used for the {\it
output} of the solution (and specified as a parameter in the
appropriate subroutine, see section 3.). For each non-zero entry $N$
of $W$ of the form \textref{(4)}, there is one row containing $i$,
$j$, $d+1$, followed by a line containing $\epsilon$, $\alpha_d$,
$\alpha_{d-1}$, $\cdots$, $\alpha_0$. The integer file is read
repeatedly by the program, and the residuals modulo the various primes
is formed. The determinant of the diagonal scaling matrix (that
transforms the rational system into an integer one) is also used
several times, and is stored after its computation at the end of the
integer file. However, it need not be supplied by the user and can be
omitted when preparing an integer file.
In all three types of files, the non-zero entries must be ordered by
rows, i.e., the $i$ must be ordered in an increasing sequence. Within
a row, the sequence of the entries is arbitrary. There must be at
most one entry in the file for each location in the work array.
For the case $\xi=1$, $\eta=2$, the single precision rational
file describing the linear system is given in Table 1. For this case,
\Goliath{} will find the particular solution $$x_1=3,\quad x_2=0, \quad
x_3={3\over 2}\eq$$ and the computed basis of the null space will consist
of the single vector $$\left[4,-2,1\right]^T.\eq$$
\baselineskip=7pt
{\sm
\settabs 15 \columns
\midinsert
\vbox{
% xi = 1, Eta = 2 file = a1b2.rat
% raw data file:
% 4,3,1,13
% 1,1,1,1
% 1,2,2,1
% 1,4,3,1
% 2,2,1,1
% 2,3,2,1
% 2,4,3,1
% 3,1,1,1
% 3,2,3,1
% 3,3,2,1
% 3,4,6,1
% 4,1,1,1
% 4,2,1,1
% 4,3,-2,1
\+ &&&&&\hfill 4 &\hfill 3 &\hfill 1 &\hfill 13 &\cr
\+ &&&&&\hfill 1 &\hfill 1 &\hfill 1 &\hfill 1 &\cr
\+ &&&&&\hfill 1 &\hfill 2 &\hfill 2 &\hfill 1 &\cr
\+ &&&&&\hfill 1 &\hfill 4 &\hfill 3 &\hfill 1 &\cr
\+ &&&&&\hfill 2 &\hfill 2 &\hfill 1 &\hfill 1 &\cr
\+ &&&&&\hfill 2 &\hfill 3 &\hfill 2 &\hfill 1 &\cr
\+ &&&&&\hfill 2 &\hfill 4 &\hfill 3 &\hfill 1 &\cr
\+ &&&&&\hfill 3 &\hfill 1 &\hfill 1 &\hfill 1 &\cr
\+ &&&&&\hfill 3 &\hfill 2 &\hfill 3 &\hfill 1 &\cr
\+ &&&&&\hfill 3 &\hfill 3 &\hfill 2 &\hfill 1 &\cr
\+ &&&&&\hfill 3 &\hfill 4 &\hfill 6 &\hfill 1 &\cr
\+ &&&&&\hfill 4 &\hfill 1 &\hfill 1 &\hfill 1 &\cr
\+ &&&&&\hfill 4 &\hfill 2 &\hfill 1 &\hfill 1 &\cr
\+ &&&&&\hfill 4 &\hfill 3 &\hfill -2 &\hfill 1 &\cr
\bigskip
\centerline{{\bf Table 1:} Single Precision Rational Data File, $\xi=1$, $\eta=2$}
\bigskip}
\endinsert
}
\baselineskip=15pt
The Single Precision Rational file is probably the most convenient
if it can be used. However, sometimes the numbers defining the linear
system are too large to be expressed in this form. Table 2 lists an
Arbitrary Precision Rational file for the case
$\xi=2^{-40}$ and $\eta = 3^{-25}$. The table illustrates
the most compact data file possible. However, if desired for example the fourth
row could be replaced by the following lines:
\settabs 5 \columns
$$\vbox{
\+ & the following is the denominator of \cr
\+ & the one/one entry of the matrix: \cr
\+ & 109951162777 last digit: 6\$ & \cr}\eq$$
\baselineskip=7pt
{\sm
\settabs 15 \columns
\midinsert
\vbox{
% xi = 2**(-40), eta = 2**(-25) file: COMPLC.RAT
%
% raw data file:
% 4,3,1,13
% 1,1
% 1$
% 1099511627776$
% 1,2
% 1$
% 847288609443$
% 1,4
% 1946800237219$
% 931603678164736454688768$
% 2,2
% 1$
% 1099511627776$
% 2,3
% 1$
% 847288609443$
% 2,4
% 1946800237219$
% 931603678164736454688768$
% 3,1
% 1$
% 1099511627776$
% 3,2
% 1946800237219$
% 931603678164736454688768$
% 3,3
% 1$
% 847288609443$
% 3,4
% 1946800237219$
% 465801839082368227344384$
% 4,1
% 1$
% 1099511627776$
% 4,2
% 252223018333$
% 931603678164736454688768$
% 4,3
% -1$
% 847288609443$
\+ &&&& 4&\hfill 3&\hfill 1&\hfill 13 & \cr
\+ &&&& 1&\hfill 1 &\hfill \cr
\+ &&&& 1\$ & \cr
\+ &&&& 1099511627776\$ & \cr
\+ &&&& 1&\hfill 2 & \cr
\+ &&&& 1\$ & \cr
\+ &&&& 847288609443\$ & \cr
\+ &&&& 1&\hfill 4 & \cr
\+ &&&& 1946800237219\$ & \cr
\+ &&&& 931603678164736454688768\$ & \cr
\+ &&&& 2&\hfill 2 & \cr
\+ &&&& 1\$ & \cr
\+ &&&& 1099511627776\$ & \cr
\+ &&&& 2&\hfill 3 & \cr
\+ &&&& 1\$ & \cr
\+ &&&& 847288609443\$ & \cr
\+ &&&& 2&\hfill 4 & \cr
\+ &&&& 1946800237219\$ & \cr
\+ &&&& 931603678164736454688768\$ & \cr
\+ &&&& 3&\hfill 1 & \cr
\+ &&&& 1\$ & \cr
\+ &&&& 1099511627776\$ & \cr
\+ &&&& 3&\hfill 2 & \cr
\+ &&&& 1946800237219\$ & \cr
\+ &&&& 931603678164736454688768\$ & \cr
\+ &&&& 3&\hfill 3 & \cr
\+ &&&& 1\$ & \cr
\+ &&&& 847288609443\$ & \cr
\+ &&&& 3&\hfill 4 & \cr
\+ &&&& 1946800237219\$ & \cr
\+ &&&& 465801839082368227344384\$ & \cr
\+ &&&& 4&\hfill 1 & \cr
\+ &&&& 1\$ & \cr
\+ &&&& 1099511627776\$ & \cr
\+ &&&& 4&\hfill 2 & \cr
\+ &&&& 252223018333\$ & \cr
\+ &&&& 931603678164736454688768\$ & \cr
\+ &&&& 4&\hfill 3 & \cr
\+ &&&& -1\$ & \cr
\+ &&&& 847288609443\$ & \cr
\bigskip
\centerline{{\bf Table 2:} Arbitrary Precision Data File, $\xi = 2^{-40}$, $\eta = 3^{-35}$}
\bigskip
}
\endinsert
}
\baselineskip=15pt
\Goliath{} will find the solution
$$x_1={1946800237219\over 847288609443},\quad x_2 = 0, \quad
x_3 = {1946800237219\over 1099511627776}\eq$$
and the null vector
$$ y = \pmatrix{1208925819614629174706176 \cr
-931603678164736454688768 \cr
717897987691852588770249 \cr}\eq$$
For both types of rational file, \Goliath{} first creates an equivalent integer file.
Table 3 lists the integer file for the second case (with $\beta=10,000$). The final entry
(the determinant of the diagonal matrix that transforms the rational
system to an integer one) may be omitted in a user generated file.
The concluding message is written by the program.
\baselineskip=7pt
{\sm
\settabs 15 \columns
\midinsert\vbox{
% Integer file COMPLC.CNV
% xi = 2**(-40) eta = 3**(-25)
% 4 3 1 13 10000
% 1 1 4
% 1 8472 8860 9443
%
% 1 2 5
% 1 1 995 1162 7776
%
% 1 4 5
% 1 1 9468 23 7219
%
% 2 2 4
% 1 8472 8860 9443
%
% 2 3 5
% 1 1 995 1162 7776
%
% 2 4 5
% 1 1 9468 23 7219
%
% 3 1 4
% 1 8472 8860 9443
%
% 3 2 5
% 1 1 9468 23 7219
%
% 3 3 5
% 1 1 995 1162 7776
%
% 3 4 5
% 1 3 8936 47 4438
%
% 4 1 4
% 1 8472 8860 9443
%
% 4 2 4
% 1 2522 2301 8333
%
% 4 3 5
% -1 1 995 1162 7776
%
% 0 0 25
% 1 7532 2509 393 3759 2419 9139 4773 8438 6280
% 4061 4531 6968 7360 3820 1497 5258 2733 9740 6175
% 15 8839 6937 9801 4976
%
% final element is determinant of scaling matrix
%
%
%
%
\+&&& &\hfill 4 &\hfill 3 &\hfill 1 &\hfill 13 &\hfill 10000& \hfill &\cr
\+&&& &\hfill 1 &\hfill 1 &\hfill 4& \hfill &\cr
\+&&& &\hfill 1 &\hfill 8472 &\hfill 8860 &\hfill 9443& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 1 &\hfill 2 &\hfill 5& \hfill &\cr
\+&&& &\hfill 1 &\hfill 1 &\hfill 995 &\hfill 1162 &\hfill 7776& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 1 &\hfill 4 &\hfill 5& \hfill &\cr
\+&&& &\hfill 1 &\hfill 1 &\hfill 9468 &\hfill 23 &\hfill 7219& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 2 &\hfill 2 &\hfill 4& \hfill &\cr
\+&&& &\hfill 1 &\hfill 8472 &\hfill 8860 &\hfill 9443& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 2 &\hfill 3 &\hfill 5& \hfill &\cr
\+&&& &\hfill 1 &\hfill 1 &\hfill 995 &\hfill 1162 &\hfill 7776& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 2 &\hfill 4 &\hfill 5& \hfill &\cr
\+&&& &\hfill 1 &\hfill 1 &\hfill 9468 &\hfill 23 &\hfill 7219& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 3 &\hfill 1 &\hfill 4& \hfill &\cr
\+&&& &\hfill 1 &\hfill 8472 &\hfill 8860 &\hfill 9443& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 3 &\hfill 2 &\hfill 5& \hfill &\cr
\+&&& &\hfill 1 &\hfill 1 &\hfill 9468 &\hfill 23 &\hfill 7219& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 3 &\hfill 3 &\hfill 5& \hfill &\cr
\+&&& &\hfill 1 &\hfill 1 &\hfill 995 &\hfill 1162 &\hfill 7776& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 3 &\hfill 4 &\hfill 5& \hfill &\cr
\+&&& &\hfill 1 &\hfill 3 &\hfill 8936 &\hfill 47 &\hfill 4438& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 4 &\hfill 1 &\hfill 4& \hfill &\cr
\+&&& &\hfill 1 &\hfill 8472 &\hfill 8860 &\hfill 9443& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 4 &\hfill 2 &\hfill 4& \hfill &\cr
\+&&& &\hfill 1 &\hfill 2522 &\hfill 2301 &\hfill 8333& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 4 &\hfill 3 &\hfill 5& \hfill &\cr
\+&&& &\hfill -1 &\hfill 1 &\hfill 995 &\hfill 1162 &\hfill 7776& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& &\hfill 0 &\hfill 0 &\hfill 25& \hfill &\cr
\+&&& &\hfill 1 &\hfill 7532 &\hfill 2509 &\hfill 393 &\hfill 3759 &\hfill 2419 &\hfill 9139 &\hfill 4773 &\hfill 8438 &\hfill 6280& \hfill &\cr
\+&&& &\hfill 4061 &\hfill 4531 &\hfill 6968 &\hfill 7360 &\hfill 3820 &\hfill 1497 &\hfill 5258 &\hfill 2733 &\hfill 9740 &\hfill 6175& \hfill &\cr
\+&&& &\hfill 15 &\hfill 8839 &\hfill 6937 &\hfill 9801 &\hfill 4976& \hfill &\cr
\+&&& &\hfill & \hfill &\cr
\+&&& & final element is determinant of scaling matrix& \hfill &\cr
\bigskip
\centerline{{\bf Table 3:} Integer Data File, $\xi = 2^{-40}$, $\eta = 3^{-35}$}
\bigskip
}
\endinsert
}
\baselineskip=15pt
\sect{3. Using Goliath}
The \Goliath{} package can be accessed on various levels. In this
section we describe (in the sequence in which they occur) the first
few segments of the code distributed with this documentation. That code consists of
some 4,500 lines of portable FORTRAN. We have tested it on five different Machines
(a DEC 20, a Vax 8600, a Cray XMP-48, a Sun 3/50 workstation, and a Macintosh SE).
\sect{3.1 A sample main program}
The code distributed with this document begins with 61 lines of
comments that give a sample main program. It can be activated by
removing the asterisks in the first column. This is the program that
we used to test the code.
\sect{3.2 Subroutine GOLIA}
The sample main program is followed by the subroutine GOLIA which
prints an identifying message. That message should be modified
appropriately whenever the code is changed.
\sect{3.3 Subroutine SECOND}
In our testing we assumed that we can call a subroutine SECOND(T)
that assigns to T the amount of CPU time in seconds that has been
elapsed since the program started. This facility is available on many
systems. However, if it is not then the dummy subroutine SECOND following
GOLIA may be activated by removing the asterisks in the first column.
The part of the output concerned with the timing of the run will
be rendered meaningless.
\sect{3.4 Subroutine ANALYZ}
This is one of the core routines of the system. It is convenient
to use since the user has to supply only one (sufficiently large)
integer work array. That array is then carved up into various parts
by other routines called within ANALYZ. However, as a consequence the
results of the computations are buried so deeply within the system
that at this level they are accessible only in the output file
generated by the system.
The calling list of ANALYZ is
{\frenchspacing\obeylines\tt
~~~~~~SUBROUTINE~ANALYZ(ITRMO,IBASE,LGINT,IORAT,IOINT,IORES,IOLOG,LOG,
~~~~~X~JOB,ITYPE,ISTOP,IBLANK,IWRK,NWRK,HWRK,NH)
~~~~~~INTEGER~IWRK(NWRK)
~~~~~~REAL~HWRK(NH)
\nonfrenchspacing}
The parameters have the following
meaning:
\parindent=1truein
\item{{\bf ITRMO}} Integer input variable giving the default output
device number, usually the terminal.
\item{{\bf IBASE}} An integer constant, the base of the fixed radix output, usually a power
of 10. IBASE**2 must not overflow an integer word.
\item{{\bf LGINT}} An integer constant, the largest integer that can be represented on the machine.
\parindent=1truecm
The following 4 parameters point to appropriate files for input and
output. It is assumed that the files have been properly defined and
opened if they are to be used. The rational data file and the log file
may be unused, in which case the values of the corresponding
parameters are not referenced.
\parindent=1truein
\item{{\bf IORAT}} Unit number of the rational data file.
\item{{\bf IOINT}} Unit number of the intermediate Integer file.
\item{{\bf IORES}} Unit number of the result output file.
\item{{\bf IOLOG}} Unit number of the Log file.
\item{{\bf LOG}} An integer constant specifying the amount of intermediate
output. If LOG $>$ 1 log output is directed to the Log file.
Ordinarily, that information is useful only for debugging.
Possible values are:
\itemitem{0} No output.
\itemitem{1} Operation statistics at the end of the run, directed to
the output file.
\itemitem{2} Elimination information during the first pass of the
linear system.
\itemitem{3} More detailed elimination information during the first pass.
\itemitem{4} Detailed information during all passes.
\item{{\bf JOB}} Integer constant indicating type of Task to be completed. Possibilities include:
\itemitem{0} Analysis of rank and row dependencies. This information
is also included when 0 $<$ JOB $<$ 4.
\itemitem{1} Solution of Linear Systems only.
\itemitem{2} Analysis of the Null Space only.
\itemitem{3} Solution of Linear Systems and Analysis of Null Space.
\itemitem{4} Conversion Rational to Integer File only.
\item{{\bf ITYPE}} Integer Constant specifying type of Input file.
Possibilities include:
\itemitem{0} Arbitrary Precision Integer file, e.g, the file listed in
Table 3.
\itemitem{1} Single Precision Rational File, e.g., the file listed in
Table 1.
\itemitem{2} Arbitrary Precision Rational File, e.g., the file listed
in Table 2.
\item{{\bf ISTOP}} Integer Constant defining the stopping criterion.
Possibilities include:
\itemitem{$-2$} Modified Hadamard Bound, i.e., the Hadamard bound applied to the leading square
non-singular submatrix (after pivoting).
\itemitem{$-1$} Experimental ``Convergence Criterion''. This means
that the modified Hadamard bound is satisfied, and none of the mixed
radix coefficients of the solution or the null space changed in the
last three passes.
\itemitem{0} Hadamard Bound.
\itemitem{$>$ 0} Specified number of passes.
\item{{\bf IBLANK}} Indicates whether the individual terms in the
fixed radix output are separated by blanks (IBLANK = 1) or not (IBLANK
= 0).
\item{{\bf IWRK}} A 1 dimensional Integer work array of sufficient
size. The larger this array the larger the problem will be that can
be solved by the system. On the other hand, an unnecessarily large
array can cause a large amount of page swapping, increasing the
overhead in disk operations. For each problem, the system returns a
recommended size of this work array, see below.
\item{{\bf NWRK}} Size of IWRK.
\item{{\bf HWRK}} A 1 dimensional real work array, used for
computing the Hadamard bound.
\item{{\bf NH}} The size of HWRK. It must
be greater than $m$ + $n$ + $p$.
\parindent=1truecm
\sect{3.4 Subroutine DIALOG}
This subroutine enters a dialog with the user and asks for appropriate
filenames and parameter values. The calling list is
{\frenchspacing\obeylines\tt
~~~~~~SUBROUTINE~DIALOG(IWRK,NWRK,HWRK,NH,ITRMI,ITRMO,IBASE,LGINT)
~~~~~~INTEGER~IWRK(NWRK)
~~~~~~REAL~HWRK(NH)
\nonfrenchspacing}
The parameters are the same as for ANALYZ, except for
{\bf ITRMI} which
is an integer constant giving the unit number of the
device on which the dialog is carried out.
\sect{3.5 Subroutine RSDANA}
This is the heart of the package that actually carries out the
analysis. It may be called when DIALOG or ANALYZ do not offer
sufficient control or access. See the comments in RSDANA for more
information, and refer to the code of ANALYZ for an example of how one
might call RSDANA.
\sect{3.6 Multiple Precision Arithmetic}
Built into \Goliath{} is an arbitrary precision integer (API) arithmetic
package that can be used by itself. APIs are stored in integer arrays as described in the introduction.
The individual entries act as digits with respect to a specified
integer base. The square of the base must not overflow the integer
word size. Routines are available for the
following tasks:
\parindent=1truein
\item{{\bf MPADD}} Addition of two APIs.
\item{{\bf MPBASE}} Base conversion.
\item{{\bf MPCOPY}} Copies an API to an array.
\item{{\bf MPDIV}} Division of two APIs with remainder.
\item{{\bf MPGCD}} Computes the greatest common divisor of two
APIs
\item{{\bf MPLCM}} Computes the least common multiple of two
APIs
\item{{\bf MPMAKE}} Convert an integer word into an API.
\item{{\bf MPMAX}} Find the maximum of two APIs.
\item{{\bf MPMULT}} Multiply two APIs.
\item{{\bf MPOUT}} Print an API.
\item{{\bf MMPACK}} Strip leading zeros from an API.
\item{{\bf MPPWR}} Compute an integer power of an API.
\item{{\bf MPREAD}} Read an API (terminated
by a \$ sign as in the arbitrary precision rational data file).
\item{{\bf MPSUB}} Compute the difference of two APIs.
\parindent=1truecm
For more detailed information consult the code and embedded comments.
\sect{3.7 Prime Generation}
To avoid errors and artificial constraints \Goliath{} calculates prime
numbers when needed. The relevant subroutine is PRMS. It calls a
sieve of Eratosthenes, PSIEVE. For more information consult the code
and embedded comments.
\sect{4.~Output}
The system generates an output file that contains the following information:
\item{1.} An identifying message giving the version number of
\Goliath, and the date it was last changed (provided such change has
been duely recorded in the message printed by the subroutine GOLIA).
\item{2.} The number of rows, columns, and right hand sides of the
linear system, i.e., $m$, $n$, and $p$.
\item{3.} The number of passes required to satisfy Hadamard's bound.
\item{4.} The number of passes actually made.
\item{5.} The number of passes that did not yield any non-zero
coefficients in the mixed radix form of the solution and basis of the
null space.
\item{6.} The rank of the matrix $A$.
\item{7.} A list of dependent rows. If the $i$-th row, say, is listed
here it can be written as a linear combination of the first $i-1$
rows. This is accomplished by using column pivoting instead of row pivoting.
\item{8.} A list of linearly independent rows that span the row space.
this is the complement of the list of dependent rows.
\item{9.} Similarly, a basis of the column space.
\item{10.} The determinant of the leading non-singular submatrix of the
integer matrix.
\item{11.} The numerator and denominator of the corresponding rational matrix.
\item{12.} For each right hand side, the non-zero components of the
solutions, with a common denominator given first. Then for each
non-zero component there are two lines giving:
\itemitem{---} The physical row number, and
\itemitem{---} The Numerator in fixed radix form with the given base.
\item{13.} Non-zero components of a null space basis. The basis is integer.
For each base vector a corresponding column (i.e., variable) is
identified. The base vector has non-zero components for that
variable, and the variables corresponding to the columns spanning the
column space listed above. The other components are zero.
For each non-zero component of a null space base vector there are
two lines giving:
\itemitem{---} The row number of the component and the physical column
number in the hash table.
\itemitem{---} The numerical value of the component in fixed radix notation.
\item{14.} Technical data regarding the operation of the routine:
\itemitem{---} The maximum number of double hashes necessary for an
access to a matrix element during the Gaussian elimination. The
larger this number the less efficient is the method. The ideal value
is 0, it can be decreased by increasing the size of the work array.
\itemitem{---} Percentage of the hash table used for the elimination.
In this release\query{In unusual circumstances the percentage can be
modified by setting the PARAMETER FILL in the subroutine RSDANA} of
\Goliath{} that percentage will usually not exceed 50\%. This is a
good compromise between efficient use of memory and fast execution
speed.
\itemitem{---} Similar data for the solution part of the process,
i.e., the computation of the mixed radix coefficients of the solutions
of the linear systems and the basis of the null space.
\itemitem{---} Hashing efficiency. The larger this number the less
efficient is the use of the hash table. It can be decreased by
increasing the size of the integer work space.
\itemitem{---} An indicator of the efficiency of the elimination process.
Since numerical stability is no concern in exact arithmetic pivoting
is done with with a view of keeping fill-in low. At no stage of the
elimination does the number of non-zero elements in the matrix exceed
the product of the ``elimination efficiency'' and the initial number
of non-zero elements.
\itemitem{---} A measure of the fill-in in the matrix. This number
takes into account all non-zero entries generated in the elimination
process. The ``pivot efficiency'' term may be larger than the
``elimination efficiency'' since locations in the hash table that are
eliminated can be reused.
\itemitem{---} The percentage of the hash table that is used when
calculating the fixed radix forms of the solutions of the linear
systems and the basis of the null space from their mixed radix form.
\item{15.} A suggested size of the integer work space. This number
can be used as a guidance for the solution of similar problems. An
excessively large amount of work space can result in diminished
efficiency due to increased page swapping.
\sect{5.~A sample output file}
The following is a sample output file generated with JOB = 3,
IBLANK = 0, and BASE = 1000, for the file listed in Table 2.
\vfill\eject
\baselineskip=6pt
{\sm
\bigskip
\frenchspacing\tt\obeylines
~>>>~this~is~GOLIATH,~version~2.03,~April~12,~1989~Vax~version~
~~~~~********************************************************
~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~numerical~results~~~~~~~~~~~~~~~~~~~~
~~~~~~
~~~~~********************************************************
~~~~~input~matrix~contains:~~~~4~rows
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~3~columns
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1~rhs
~~~~~hadamard~bound~on~passes~is:~~~~11
~~~~~passes~for~termination:~~~~11
~~~~~unused~passes:~~~~5
~~~~~matrix~rank~is~~~~2
~~~~~the~dependent~rows~are
~~~~~~~~~~3~~~~~4
~~~~~the~row~space~is~spanned~by~rows
~~~~~~~~~~1~~~~~2
~~~~~the~column~space~is~spanned~by~columns
~~~~~~~~~~1~~~~~3
~~~~~********************************************************
~~~~~~
~~~~~~~each~of~the~integers~below~is~in~fixed-radix~form.
~~~~~~
~~~~~********************************************************
~~~~~the~minor~of~the~leading~non-singular~submatrix:
~~~~~~~931603678164736454688768
~~~~~the~determinant~of~the~rational~matrix:
~~~~~numerator~
~~~~~~~~~~1
~~~~~denominator~
~~~~~~~8085252431347553590473756381133411762217446054283685
~~~~~~~84592149222713720832
~~~~~********************************************************
~~~~~~
~~~~~~~~~~~~~~~~~~solutions~to~the~linear~systems~~~~~~~~~~~~
~~~~~~
~~~~~********************************************************
~~~~~solution~to~rhs~\#~1;~hash~column~key~~~4
~~~~~denominator~
~~~~~~~931603678164736454688768
~~~~~numerators~
~~~element:~~~~~~1
~~~~~~~~~~2140529497779365629394944
~~~element:~~~~~~3
~~~~~~~~~~1649501665856589043459017
\vfill\eject
~~~~~********************************************************
~~~~~~
~~~~~~~~~~~~~~non-zero~elements~in~the~null~space~basis~~~
~~~~~~
~~~~~~~~~~~read~as~(i,j)~element~in~pivoted~matrix~followed~
~~~~~~~~~~~~~~~the~value~expressed~in~fixed~radix~form~
~~~~~~
~~~~~********************************************************
~~~~~the~null~space~is~~~~~~1~dimensional.
~~~~~the~corresponding~matrix~columns~are:
~~~~~~~~~~2
~~~~~null~space~vector:~~~~1~hash~column~key:~~~3
~~~~~corresponding~matrix~column:~~~~2
~~~element:~~~~~~1
~~~~~~~~~~1208925819614629174706176
~~~element:~~~~~~2
~~~~~~-931603678164736454688768
~~~element:~~~~~~3
~~~~~~~717897987691852588770249
~~~~~********************************************************
~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~routine~statistics~~~~~~~~~~~~~~~~~~~~
~~~~~~
~~~~~~~~~~~~~~~note:~optimal~efficiency~ratings~=~1~~
~~~~~~
~~~~~********************************************************
~~~~~~elimination~maximum~double~hashes~necessary:~~~~~~0
~~~~~~elimination~hash~table~use:~~~~~~~13~of~~~49367~=~~~0.03\%
~~~~~~solution~hash~table~use:~~~~~~~12~of~~~24709~=~~~0.05\%
~~~~~~solution~maximum~double~hashes~necessary:~~~~~~0
~~~~~~~~~~~~~~~~~~~~~~~~~~~(\#~tot~hashes)~+~(\#~double~hashes)
~~~~~~hashing~efficiency~=~----------------------------------
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(\#~tot~hashes)~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~=~~~~~~1.00000
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~max~\#~of~non-zero~elements~~~
~~~~~~elimination~efficiency~=~------------------------------
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~initial~\#~of~non-zero~elements
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=~~~~~~1.00000
~~~~~~~~~~~~~~~~~~~~~~~~~~\#~initial~non-zero~+~\#~of~fillin~elements
~~~~~~pivot~efficiency~~=~-----------------------------------------
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~initial~\#~of~non-zero~elements
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=~~~~~~1.00000
~~~~~~output~hash~table~use:~~~~~~~~52~of~~~74093~=~~~0.07\%
~~~~~~suggested~minimum~for~size~of~work~space~in~analyz~=~~~2515
}
\baselineskip=15pt
\bye
-------