Crawly Crypt Collection 1/crawlyvol1.bin/apps/math/matricks/matricks.doc

Text File | 1989-04-30 | 22KB | 515 lines

=======================================================

                  M A T R I C K S

             A Linear Algebra Package
                        by
                  Victor Eijkhout

=======================================================

=======================================================
                U S E R   M A N U A L
===================Introduction========================

'MaTricks' is a linear algebra package for purposes of research
and education. It is not meant to be a high precision numerical
library. Emphasis is on ease of input and ease of inspection of
results (filling in a Hilbert matrix takes literally 8
keystrokes, and matrices are in full view most of the time).
While most of the common matrix operations are included, there
exists the possibility to add user-defined modules to the
package. 'MaTricks' operates completely in text mode, and it
has extensive on-line help. It was written in STPascal version 2.0 of
CCD-D.Beyelstein.

A bit of history---------------------------------
I wrote a first version of this program when doing
research together with Ben Polman on band matrices (this has
since then been published in Linear Algebra and its
Applications, vol. 109), and I needed a tool to test my
hypotheses quickly. Originally written for the Ibm-pc,
'MaTricks' has recently been ported to the Atari and extended
considerably. I am contemplating the possibility of
a back-port.

The concept of shareware--------------------------
This program is shareware. This means that you are free to check
out this program to see if you like it. In case you want to
continue using it, I ask for a small contribution, say $10.
Your sense of honour is the only compulsion for obliging me.
There are advantages to registring yourself as a user, however.
See the section on user modules.

Send your shareware contribution to
          Victor Eijkhout
          Dingostraat 53
          6531 PA Nijmegen
          the Netherlands.
Questions, suggestions and bug reports can be sent to the
same address, or by email to
          [e-mail]     <- preferably this one
or        [e-mail]      (that's uucp).

You are invited to give this program to other people who
might be interested, with the restriction that this
manual is also passed in its entirity. The shareware rules
hold for any recipients of the program and manual.

About this manual-----------------------------------------
The MaTricks program has quite a lot of on-line help.
It should be quite possible to use the program
without ever referring to this manual. In fact, the only
thing found exclusively in this manual is the information
about interfacing the program to user-defined modules.
The other topics only get treated more elaborately in this
manual.

Note that this manual is not a linear algebra course.
It only describes how to perform certain operations,
that you supposedly know, by means of this program.

Disclaimer------------------------------------------------
Matricks is rather a harmless program.
It is purely for legal reasons that I include the following:
     "I make no warranty with respect to this manual, or the
      program it describes, and disclaim any implied or explicit
      suggestions of usefulness for any particular purpose.
      Use this program only if you are willing to assume all
      risks, and damages, if any, arising as a result, even if
      they are caused by negligence or other fault."



==================Data Limitations=========================

The main data structure of 'MaTricks' is an array of 10
matrices, the maximal size of which has arbitrarily been set to
37. While this is rather limited for real world computation, it
is probably sufficient for the purposes for which the program
was designed.

All ten matrices are square and of the same dimension, and there
are no vectors. After all, rectangular matrices are special
cases of square ones, and so are vectors.



=====================The Menus=======================

The program is structured around a number of menus (three at the
moment; this does not include the view screen)
that have one character commands.

Command lists-----------------------------------
A command can be chosen by typing the corresponding
character directly at the keyboard. Alternately
one can move through the list of commands using the
space bar, which moves the cursor down cyclically.
When the cursor has been positioned like this, the
command can be chosen by hitting <Return>. Typing <?> gives a
short description of the command.

Commands that have a matrix argument take the 'current matrix'
as its first or only argument. When the program prompts for an
argument, you can abort the command by entering an empty line.

If a command is in a submenu, the program returns to the main
menu after execution of the command. The submenus contain a
'quit to the main menu' command, in case you change your mind
about selecting a command from the submenu.


The Matrix List---------------------------------
In all menus the lower right corner of the screen displays a
short inventory of the ten matrices.
- An arrow indicates the 'current matrix'.
- Typing any of the digits 0--9 changes the
  number of the current matrix.
- Matrices that have been filled (either in view mode, or as the
  result of some operation) are marked with 'X'.
- To prevent you from losing track of your own actions, there is
  a facility for naming the matrices.



==========================View Mode==========================

The most important feature of 'MaTricks' is undoubtedly its full
screen view mode. A nine-by-nine portion of the matrix is
displayed here. Input of matrices is also done here.


Information Lines--------------------------------
In view mode, the lower lines of the screen give information
about the current matrix.
- The cursor position (in (i,j) coordinates) is always visible,
- if the matrix has been named its name is visible,
- the key <:> is a toggle for full-precision display of the
element under the cursor,
- the key <;> toggles the display of the current 'decay factor',
i.e., the current element divided by its neighbour. You are
prompted for the direction in which the neighbour is taken
(nsew). Choosing <o> will switch off decay factor display.

For matrices that have been filled using an operation in the
'iterative methods' menu, a topline is added to the screen,
displaying the status of the first couple of columns of the
matrix.


Cursor Movement---------------------------------------
There are three ways to move the cursor through the screen
across elements.
- First of all the cursor keys have been implemented.
- Secondly, in order to move along cross-directions, the 1--9
key of the keypad (excepting the 5) are also cursor movements.
- Thirdly, for touch typists the combination of control and the
basic positions of the right hand (uio, jkl, m,.) double the
keypad functions.

Adding the <control>-key to the first two possibilities gives
movement across nine-by-nine chunks.

The <home> key makes the cursor move to the (1,1)-element of the
matrix, <control>-<home> performs a similar jump to the
(n,n)-element.


Operations-----------------------------------------
Already in the view mode some matrix operations are possible.
s - symmetrise the matrix by taking its symmetric part,
a - anti-symmetrise the matrix in a like manner,
p - zero all elements (i,j) for which |i-j|>p
    (the quantity p is prompted for),
P - zero all elements (i,j) for which |i-j|<=p
    (again the quantity p is prompted for)
# - some elementary statistics on the current matrix.

Input------------------------------------------
Filling the matrix is done by positioning the cursor (if
necessary) and typing one of the following keys:
e - fill the element under the cursor,
r - fill the row on which the cursor stands,
c - fill the column in which the cursor stands,
d - fill the sub, super, or main diagonal on which the cursor
    stands, (if the matrix has been partitioned into block form
    this will fill the diagonal as far as it is part of the
    block-diagonal)
u - fill the upper triangle of the matrix (main diagonal not
    included),
l - fill the lower triangle of the matrix (main diagonal not
    included),
m - fill the whole matrix.

After hitting any of these keys, you are prompted for input.
This input can have a number of forms.
Input can be
- numeric:
                      type 3.1415 ;
  thus a few keystrokes suffice to fill
  a Toeplitz matrix,
- symbolic:
                      type 1/3
                      or   (20+2)/(10-3) ;
- with infix dyadic operators:
  '|' for maximum,
  '_' for minimum,
  '^' for ordinary exponentiation (of nonnegative numbers);
               thus typing 2^3 gives 8
  'e' for integer powers (negative base permitted)
                      type (-1)e5 ;
- with prefix monadic operators:
  's' for sine,
  'c' for cosine,
  'a' for absolute value;
      this requires brackets most of the time:
      for instance calculate distance from the main diagonal by
                           a(i-j) ,
- referring to matrix coordinates i,j,n;
  thus a Hilbert matrix
  is generated by          1/(i+j-1) ,
- referring to elements of the matrix:
                      type [i,j]
                       or  [i+1,j-1]
  (non-existing elements are taken as zero);
  thus you fill in a symmetric matrix by filling the
  lower triangle, and specifying the upper triangle
                        as [j,i] ,
- using choices: an if-then-else-fi clause has the following
  form:
                   {       :         :       }
                    if-part then-part else-part
  thus the above 'p' operation (for p=2) is equivalent to
                           {a(i-j)>2:0:[i,j]}
  The if-part can use the logical operators
                         > , < , =  and  !
  (the exclamation mark stands for not-equal).
  The else-part was intended to be [i,j] when ommited.
  It sometimes is. This is a known bug.


The Input Line Editor---------------------------------
A maximum of forty input expression is remembered in a
history buffer. This buffer can be traversed circularly
using the up and down arrow keys (think of the buffer
as a stack, the keys then indicate the direction from old to new,
or conversely; the latest contributions are added on top
of the stack).

For easy modification of old expressions (or for correcting
errors when you are typing something in) there is a simple line
editor built in.
- clear the whole line with the <Escape>-key,
- move through the line using left and right arrow keys,
- insert characters, and
- delete characters using <Backspace> and <Delete>.

Errors in the input------------------------------------
Error handling is not optimal; faulty input may give
several messages. If the screen is not updated correctly
after an error, give ',' to force a redraw.

Partitioning-------------------------------------------
Block matrices have been implemented. In order to specify the
location of the blocks the following keys are available:
-                             <
  the current column indicates the start of a block;
-                             ^
  the current row indicates the start of a block;
-                             ~
  clear all blocks.
There is always an implicit block starting at the (1,1)-element
of the matrix, so you needn't partition there.
If a partitioning has been given, the input 'd' operation
is limited to the block diagonal in which the cursor stands.
Block matrices allow block factorisations, and block iterative
methods (see below).



================the Manipulation Menu======================

The manipulation menu contains some of the most common matrix
operation.
- Addition, subtraction, multiplication are pretty standard.
- Inversion is performed using row interchanges. (This is subject
  to a toggle, in case you might want to compare accuracy with
  and without) Feel free to write your own much more
  sophisticated inversion routine.
- Factorisation is of LU type, with the diagonal of L all ones,
  and the pivots stored on the diagonal of the U factor.
  The l,u,d commands extract the factors and the pivots from
  a factorised matrix.
  Block factorisation uses the partitioning specified in view
  mode, or, if none has been specified, reduces to point
  factorisation. Again the L factor has an identity diagonal.
  The L,U,D extraction commands give block factors and a
  block diagonal matrix containing the block pivots.

Note that the block factorisation is a way of computing
Schur complements.



=============the Iterative Methods Menu=====================

The iterative methods menu contains two methods for the
solution of linear systems, the power method for computing
the dominant eigenvalue of a matrix (and its eigenvector thereto),
and the Jacobi method for approximating the eigenvalues (in general
eigenvalues cannot be computed exactly for matrix dimensions
exceeding five. This is a corollary of Galois theory).

If a partitioning has been specified, the iterative methods
become block methods.

All iterative methods need a matrix dimension of at least 3.

- Gauss-Jacobi/Gauss-Seidel. The righthand side vector of
  the linear system has to be stored in the first column of
  the matrix that is passed as the second argument to this
  command. The second column is used as initial vector, and
  the iterates overwrite this column. It needed not be filled
  initially. Upon completion of the iterative process,
  the third column of the matrix contains the product of the
  matrix and the last iterate. It takes only a column operation
  in view mode (to wit: [i,3]-[i,1] in the fourth column) to
  compute the residual from this.

- The power method computes succesive products with an initial
  matrix given in the first column of another matrix.
  Iterates are written into the second column, and Raleigh
  quotients are in the third, with the most recently computed one
  in the first row.

- The Jacobi method computes approximations to the eigenvalues
  of a symmetric matrix (your input is symmetrised first), by
  means of plane rotations that zero the maximal off-diagonal
  element of the matrix.


=================Dump to File===============================

It is possible to write matrices to an external file, or
to read them from a file. A write operation will dump
all filled matrices to the file specified, a read operation
will read all matrices contained in a file, but will attempt
not to overwrite the matrices that have been filled already.

As the file format is rather simple, it is perfectly possible
to accept input that has been prepared by another program.

For the location of input or output files a file selector
box is used, which is described in the next section.

The file format is as follows.
- The first line in the file contains a notice indicating the
  version of the file format.
- The second line has the (user-specified) dimension of the
  matrices and the number of matrices in the file,
  seperated by a space.
- The next line contains a zero if no partitioning was in effect
  when the file was written, or the number of non-trivial (that
  is, excluding the (1,1)-point) splits, followed by these
  splits, all seperated by spaces.

After this, for each matrix there is
- one line containing
  - a one-character description of the matrix, at the moment only
    'f' (which stands for 'full matrix' is supported)
  - one space, followed by the name of the matrix. Names have
    8 characters maximum.
- the elements of the matrix, stored by row, seperated by spaces,
  on any number of lines (one if you have Emacs, more if you
  have some less sophisticated editor that puts a limit
  on the line length).


====================User Modules============================

As it is impossible for a matrix package to embody
every matrix operation known to man, I have decided to
make 'MaTricks' user-extendible. The package can call
external programs and pass to them the address of its
internal data structures.

Below you find full documentation on the data structures
and just what is a Real. The easiest way to ensure compatibility
is of course to program in lovely STPascal of CCD.
Be sure to use the 'STPasage' shell of Ben Polman!


Calling External Programs---------------------------
A total of twenty external programs can be called using the
ten function keys, and the shift-function key combinations.
These stand for monadic and dyadic matrix operations respectively,
i.e., MaTricks will ask you for the number of the output matrix,
or the numbers of the other argument and the output matrix.
The external program is of course at liberty to disregard
these numbers.

After execution of the external program the output matrix is
made the current matrix and the output matrix is marked as
filled.


Program Selection---------------------------------------
Initially no programs are bound to the function keys. The first time
a key is used a file selector screen appears, enabling the user
to select an external program. This screen displays
- the available drives. Switch drives by typing one of the
  drive letters;
- the current path, and in the first column the folders therein.
  Move to a folder using arrow keys, and choose it by typing <Return>;
  the '.' stands for root of the disc, and '..' for close the current
  folder.
- the programs (.TOS, .PRG, and .TTP) in the current folder. Move
  to them using arrow keys, and choose them by typing <Return>.
  You will be asked for confirmation.
Abort the file selector by hitting <Undo>.

Saving the List of Modules----------------------------------
As soon as you have external modules, MaTricks will write a
file 'matricks.mxp' containing the names and locations of the
modules (the format is quite easy to figure out, in case you
are interested). You are allowed to rename this file.
In order to load it into the program, you have to
pass it as a parameter. This is easy working from a command shell;
if you work with the desktop you can install MaTricks to
be invoked by files with the '.mxp' extension.
Note that you have to install it as 'Tos Takes Parameters'.
For those lucky ones using STFinder: install this program
with options 'set default path to current', 'pass file as argument',
and 'don't include path in argument'.


Writing Your Own Modules------------------------------------
User modules can be called from within MaTricks; they are given
the address of the internal data structure of MaTricks.
This address is written in
hexadecimal notation and converted to a string. Your module
can retrieve it using 'argv' or 'cmd_getarg' or whatever
this function is called in your system.
At this address in memory stands the
'Com_blk' structure defined as follows:

Type Matrix_ptr  = ^Array[0..9]Of Array[1..37,1..37]Of Real;
     Fill_ptr    = ^Array[0..9]Of Boolean;
     Com_blk     = Record magic : Integer;
                          mats  : Matrix_ptr;
                          fils  : Fill_ptr;
                          mdim,size,cur,out,other
                                : Integer;
                          reserve1,reserve2,reserve3,reserve4
                                : Long_integer;
                   End;

This Pascal Record corresponds to a 'struct' in C.

- The magic int is 31415 (ints are two bytes); it is included
  to facilitate your debugging.
- The matrices are stored by row. Important: in STPascal a Real
  is a 6-byte structure: first 40 bits of mantissa, then 8 bit
  exponent. To the exponent an offset of $80 has been added.
  A null exponent denotes the number zero.
  As the mantissa is always normalised, its most significant
  bit is used for the sign, it is set for negative numbers.
- The row of Booleans indicates which of the ten matrices have
  been filled by the user. You are free to use empty matrices
  (or filled ones, for that matter) as working space.
  For C-programmers: a Boolean is a 16-bit word; it is 'True'
  (i.e., the corresponding matrix has been filled) if its
  least significant bit has been set.
- The integers have the following meaning:
  mdim  : matrices are allocated as 37-by-37 arrays. You can use this
          fact but if you want your module to be compatible with
          later versions of MaTricks (which may have a different
          size) you can use this parameter.
          It has the value 37 at the moment.
  size  : the matrix dimension as indicated by the user.
  cur   : the current matrix. This is at the same time the first
          argument that the user indicated for
          the function in your module.
  out   : the number of the matrix where the user wants you to
          put the results.
  other : if the module defines a dyadic operation this indicates the
          second input argument.
  the four Long_Integers at the end are reserved for future extensions
          to the MaTricks package.

====================This program is Shareware=======================
Remember that this program is not free: it is shareware. Therefore
you ought to register if you want to keep using it,
if only to ease your conscience.
However, there is an added bonus to registering: within certain
bounds I might be willing to comply with requests from
registered users for specific external modules for this program.
(Note that I consider 'how about computing all eigenvalues and
eigenvectors' not a reasonable request. If you are an algebra
teacher, get some students to do this; if you are an algebra
student, let's hope your teacher doesn't read this.......)