MATRIX MATH(ID:94/mat017)

Matrix algebra compiler for UNIVAC II 

• Country: us
  • languages for us
  • us/1953
• Began: 1953
  • Languages for 1953
  • 1950s languages
  • First generation
  • Early Cold War
• Published: 1954
  • 1954
• Type:Algebraic
  • Algebraic
• Sammet:NSC
  • NSC
  • NSC/1953
  • NSC/us

• UNIVAC Remington Rand
• UNIVAC II Sperry Univac

• Matrix

[Remington Rand Univac] "Manual for the Matrix Math Tape" Remington 1955 view details Extract: Preface
Preface

In order to facilitate reference to material in this manual, the sections have been so arranged that they explain the fundamental principles involved in adapting problems to Univac. These sections indicate the use of library routines., define input-output handling and editing methods,, and also outline the three categories of matrix routines.
Each section is prefaced by an introduction explaining the type of rout ines involved. These sections are followed by operating instructions and other suggestions whenever necessary. The routines offer the programmer the benefit of the results of previous problems encountered and the experience gained by many people over a period of years during which matrix problems, were solved at Univac installations.
Much of the material contained in the Matrix Math Manual is a result of the initial and subsequent efforts of the Computational Division, Directorate of Management Analysis, Headquarters., United States Air Force. We wish therefore, to express our special indebtedness to this division the Air Force. The efforts of all Univac users who have made valuable contributions to this publication are also deeply appreciated. Extract: INTRODUCTION
INTRODUCTION
This manual has been compiled to aid programmers in the use of Matrix Math Tape with the Univac System. Descriptions of the routines and operating instructions required for the successful solution of matrix problems are included.
The Matrix Math Tape, a collection of discrete routines, allows the programmer to select operations and organize them in any logical sequence he desires. This affords him a wider choice of options to suit varied requirements than would be possible with a single rigid program. The routines have been so devised that a program of matrix operations can be carried out with a minimum of intermediary action by the Supervisory Control.
This method does not prevent the building of so-called "Super Routines" which effect a series of operations without interruption. This type of routine will, of course, continue to be built. As new methods are discovered from time to time, this manual will be revised and the changes made available to users of the Univac System.
In order to obtain the full benefit of organizing a program incorporating the matrix routines as components, the programmer must have a thorough knowledge of the operations that can be performed by the routines. He must be familiar with the specifications, descriptions and operating procedures associated with each routine. In order to assure an effective,successful solution to his problem with a minimum expenditure of production time, he must plan the detailed series of operations beforehand.
Three important considerations are involved in the design and interrelating of these routines. First, a consistent scheme of input and output from one routine to the next is provided. Second, it is important to maintain control of the accuracy of the results while operating on large arrays of elements. Finally, routines are devised to operate within reasonably established limits for both tape and Uniservos. At present, as space is not the most important factor, it is possible to include routines that sacrifice space to time in runs involving multiplication and inversion. However, in the future, alternate methods for these operations may be programmed. Existing routines are extremely general in purpose in order to have a wider application, and therefore do not necessarily take advantage of any special peculiarities of a given array.
Processing, Arithmetic, and Service Routines are the three categories of Matrix Math Routines. In each case the matrix has been partitioned into sub-matrices. The so-called high level sub-routines treat the sub-matrices as entities (i.e. as members of ring), while the low level sub-routines are used to handle the elements within a sub-matrix. Extract: PROCESSING ROUTINES
PROCESSING ROUTINES: The purpose of these routines is essentially one of editing. Because of the inconvenience of preparing the input matrix in a partitioned array and computing the parameters associated with it, an input editing routine has been devised to perform it automatically. The programmer need only prepare a "list" tape, containing the elements of a matrix arranged sequentially row by row.
A tape containing a matrix pertaining to one of several fixed or floating decimal formats can be prepared from the output editing routines.  The formats can be printed by the Unifirinter.
The generating routines automatically prepare certain types of matrices (e.g., the unit matrix of arbitrary order) for testing or for computational purposes.
Then too, there is a conversion routine that generates a list from a tape prepared from punched cards by th,e Card-to-Ta-pe Converter and also checks the accuracy of the conversion.
ARITHMETIC ROUTINES: These routines accomplish the following operations performed with matrices:
1.  Addition
2.  Multiplication
3.   Inversion
4.  Transposition
5.   Modification
The Modifier routine provides the inverse of a matrix that differs from some other matrix in one row or column whose inverse has been obtained. By repetitive use of this routine, it may be feasible in certain instances to obtain an inverse when there are differences from a known inverse in many rows or columns.
SERVICE ROUTINES: At the present time there are three types of Matrix Service Routines available: (1) The Norm which computes the square root of the sum of the squares of the elements and is used for certain error and condition estimates; (2) Row Column Sums and (3) The Diagonal Unit Fill Routine.
Whenever required, routines are provided with automatic reruns. It will be noted that the routines follow a pattern of Uniservc allocation. The input is usually on Uniservo two, or two and three, and the output on Uniservo four. The programs have been so designed that the computational matrix in each case fits on one tape. The obligation of meeting this requirement limits the size of the matrix in terms of a square array to an order of approximately 310.
Extract: ADAPTATION TO UNIVAC
ADAPTATION TO UNIVAC
The time required to perform complex arithmetic operations on Univac is consumed not so much in addition and multiplication, as in controlling and sequencing the process, and in transferring information. This is particularly true when an involved floating decimal system is used.
Matrices are handled in partitioned form. Since tape has to be employed as auxiliary memory for large matrices, the use of standard size sub-matrices makes this convenient and efficient, and no time is lost in reading information. Submatrices permit the use of standard sub-routines to do the arithmetic, which can be highly refined by virtue of minimum latency coding and other means. However, the most important use of the sub-matrix is that it permits a high degree of control of the accuracy of inversion. The memory space and block length determine the optimum size for sub-matrices. In these routines they have been limited to a maximum of two blocks each, with a 10 x 10 sub-matrix apparently giving the highest efficiency.
Computational routines have generally been placed in two divisions, "high-level " and "low-level". The low-level routines carry out basic operations on sub-matrices of relatively small dimensions and the high level routines operate on the "super-matrices" having the submatrices as elements.
All routines discussed here are recorded on the Matrix Math Instruction Tape, but the parameters associated with the order of the matrices to be operated upon are left undetermined. When a routine is selected, control is transferred to a preliminary section of the appropriate high-level routine which sets the parameters, in accordance with the order indicated by the input matrices. Computation then proceeds according to the instructions of the high-level routine, which uses the low-level routines for arithmetic processing. The high-level routine may also select various other low-level routines or further sections of itself as needed in the course of the computation.
Progress of the computation is indicated on the Supervisory Control at certain crucial intervals. In general, no action is required by the operator from the commencement of an operation to its completion. When a series of distinct operations is to be carried out, tapes must be changed and the starting sequence repeated for each new processing.
Re-run procedures have been developed which do not depend upon the retention of the contents of the internal memory. This reduces operator intervention to a minimum requiring little more of the operator than the initial starting procedure. This is accomplished by using a variation of the word that selects the routine followed by the last type-out on the Supervisory Control Printer.
The proper program is then placed in the memory, parameters and counters reconstituted, and the computation begins again at a point slightly previous to that at which operations stopped.
Inasmuch as these routines were designed to be as general as possible, some form of floating decimal arithmetic has to be adopted. Briefly, each element of an n x m sub-matrix is represented in the full two word floating decimal form; then to conserve space each row is contracted according to a formula based on the following:
A row exponent is determined by choosing the exponent of the element of greatest absolute value in the row of the sub-matrix.  A sub-exponent is then determined for each element in the row by subtracting the element exponent from the row exponent. This sub-exponent is restricted to one digit and is inserted in the least significant digit of the word containing the element. This form is standard for all computational routines.
Extract: PROBLEM ORGANIZATION
PROBLEM ORGANIZATION
There is no one procedure that can be outlined for solving every problem in matrix algebra, since each case has its own peculiar requirements. In general, however, the following suggestions are applicable:
1.  Analyze the problem in order to derive the simplest and most economical expression for the equation or equations.
2.  Prepare the lists for the various distinct input matrices.
3.  Draw a simple flow chart and servo allocation chart outlining the processing to be done each step of the way, including input and output editing.
4.  On the basis of this, write a complete list of operating instructions to be used on the computer. These should provide for eventualities such as down-time in the middle of a long computation, computer detection of errors such as incorrect scaling, etc.
5.  Observe all the precautionary measures mentioned in this manual as well as those usually applicable to computer operation.
6.  Output edit and print the original input matrices, after they have been input edited for additional checking, if possible.
7.  When feasible employ checking operations, particularly if working with poorly conditioned matrices. This may involve determining Turing's condition number* and an independent determination of the error matrix.**
*  Turing, A.M. - Round-off errors, XX in Matrices Journal of Math & Physics.
Briefly, C(A) = 1 N(A) N(A~ ) is small for well conditioned matrices, for example in the vicinity of 2.5 for Leontieff matrices.
** For example, (l - A A"1) I = E1
A fairly good example of the economies that can be effected by the use of one type of reduction in preference to an equally legitimate alternative reduction is clearly seen in the case of a system with complex coefficients.


A system, Ax = K, with complex coefficients is broken down into its real and imaginary parts as follows, and expressions are derived for the solution of the real and the imaginary components of the unknowns separately:
1.    (A + iB)  (x + iy) = (K + iL)
2.    Ax + iBx + i Ay - By = (K + i L)
From these are formed 2 equations, the first containing only real terms, and the second containing only imaginary terms.
a.   Ax - By = K
b.   Bx + Ay = L
Then
3.      x = A"1    (K + By) and substituting this in (2b)
4.       BA"1 K + BA-iBy + Ay = L
5.       y = (BA^B + A)"1 (L - BA^K)
Then solving for y in (2b)
6.   y = A-i (L - Bx) and substituting in (2a)
7.   Ax - BA'1 L + BA^Bx = K which reduces to
8.   x = (BA^B + A)"1 (K + BA"1!.)
The similarities between (5) and (8) are noted. However, if the expression for y in (2a) has been substituted in (2b), then
9.   x = (AB-*A + B)"1 (L + AB^K)
Thus, using the expressions in (5) and (8) requires only 4 large operations, two inversions and two multiplications, whereas using (5) and (9) requires four inversions and four multiplications.
Extract: Cover of book