% [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 -------