CMAT INSTALLATION

cmat is an exact arithmetic calculator program, written in ANSI C. It is designed to perform many of the standard arithmetical operations that can be carried out exactly, without approximations, on matrices and polynomials whose coefficients are either rational numbers, complex rational numbers, or elements of Zp - the finite field of p elements, where p is a prime less than R0=216=65536.

The C source files are available as a compressed tar file from http://www.numbertheory.org/cmat/.
It is assumed that the gnu C compiler is available. Otherwise all references to gcc in the three makefiles should be replaced by cc.

To install the program, transfer the file cmat.tar.gz to the user's home directory and type the following UNIX commands:

gunzip cmat.tar
tar xvf cmat.tar
rm cmat.tar

There will now be created in the user's home directory a directory CMAT which contains subdirectories int and poly. The int directory contains i*.c files and a Makefile; the poly directory contains p*.c files and a Makefile; the remaining files *.c, *.h, *.dat, parse.y, .cmatrc and Makefile reside in the CMAT directory itself.
Two LaTeXfiles doc.tex and readme.tex, together with a header file header.tex will reside in this directory.
To compile the programs, type make all. This compiles the executable programs cmatr, cmatcr and cmatm.

cmat has been developed on Pyramid and Sun machines, so there are bound to be glitches in the compilation on other UNIX machines. However a UNIX guru should be able to make the few changes necessary to allow compilation to proceed smoothly.

The file config.h contains default paths which are set up on the assumption that the four executable programs live in the directory /usr/local/bin while the *.dat files live in the directory /usr/local/lib/cmat.

To change the number M0 of stored global variables of each arithmetical type, the file integer.h should be edited and the programs recompiled.

Documentation

1. Files. There are various *.h files:

(a)
integer.h contains declarations of various arithmetic data structures:

(i) MPI, MPR, MPCI, MPCR;
(ii) MPMATI, MPMATR, MPMATR, MPMATCR, MPMATm;
(iii) POLYI, POLYR, POLYR, POLYCR, POLYm;
(iv) MPMATPI, MPMATPR, MPMATPCI, MPMATPCR, MPMATPm.

as well as definitions of constants R0,T0,M0,Z0,Y0,BUFLEN and some abbreviations.

(b)
cmat.h contains declarations of functions defined in files util.c and menu.c, as well as external declarations of variables used in the files.
(c)
config.h contains system dependent #defines.
(d)
primes.h contains an array of global variables corresponding to the first 2048 primes, together with a two-dimensional global array which provides a table-lookup for the inverses mod m of all residues a, 1 ≤ a ≤m, (a,m)=1, where m < 100.
(e)
fun.h contains declarations of all functions in all .c files residing in all three directories.

There are various *.dat files:

(a)
title.dat contains a title for cmat;
(b)
info.dat contains information about cmat;
(c)
menu.dat contains a menu for cmat;
(d)
menuR.dat contains the menus for cmatr;
(e)
menuCR.dat contains the menus for cmatcr;
(f)
menum.dat contains the menus for cmatm.

.cmatrc sets up the directory paths:

cmat=. for the executable programs and
datpath=. for the *.dat files.

If the variable DEBUG in integer.h is defined, an overall count of the number of bytes remaining as unfreed memory is printed on exiting the component programs cmatr, cmatcr and cmatm. Ideally this number should always be zero. If not, then this indicates that space was not freed at some stage in at least one of the algorithms; consequently an unwelcome buildup of used memory could result if the program is run repeatedly.

parse.y is a yacc file which produces a file parse.c for use in parsing simple arithmetic expressions suitable for use as formulae for the (i,,j)th element of a matrix. This line of the Makefile can be removed if one does not have yacc and the default file parse.c can be used.

2. The arithmetic data types.

The basic structure is the MPI (multiple precision integer) M which has three components: an unsigned integer M.D, a variable array of M.D+1 unsigned integers:

M.V[0],...,M.V[M.D],

where each of these array elements must be less than R0. There is a third structure component M.S, which records the sign. If m is the integer represented by the MPI M, there is a corresponding representation of m to base R0:

m=M.S(M.V[0]+...+M.V[M.D]R0M.D).

A rational number is represented by a structure M called an MPR. Here M.N and M.D are pointers to MPI's representing the numerator and denominator, respectively. The denominator must be positive and the numerator and denominator relatively prime.

A complex rational number m is represented by a structure M called an MPCR. Here M.R and M.I are pointers to MPR's representing the real and imaginary parts of m.

Polynomials are represented by linked lists along the lines of H. Flanders, Scientific Pascal, pp. 175-185, 342-357, Reston 1984, (Second Edition Birkhäuser, 1995):

POLYI, POLYR, POLYCI, POLYCR, POLYm,

each terminated by the NULL pointer. Only the non-zero terms of the polynomial are recorded. The zero polynomial is represented by the NULL pointer.

Matrices of scalars are represented by structures:

MPMATI, MPMATR, MPMATCI, MPMATCR, MPMATm.

If M is such a structure, the components M.R and M.C record the number of rows and columns, while the component M.V corresponds to a two-dimensional array of scalars of variable size.

There are also correspondingly matrices with polynomial elements:

MPMATPI, MPMATPR, MPMATPCI, MPMATPCR, MPMATPm.

It is important to remember that for the polynomial structure POLYm and matrices MPMATm and MPMATPm, the coefficients are always understood to be unsigned integers less than a prime p (the modulus), with p < R0. It is the user's responsibility to keep track of the various moduli used and to perform calculations with arithmetic objects only having the same prime modulus.

3. Other Global Variables.

Up to M0 objects of each type can be created and stored as global variables:

  1. rational numbers: R[0],...,R[M0-1];
  2. matrices with rational coefficients: RM[0],...,RM[M0-1];
  3. polynomials with rational coefficients: PR[0],...,PR[M0-1];
  4. matrices with polynomial rational coefficients: PRM[0],...,PRM[M0-1];
  5. complex rational numbers: CR[0],...,CR[M0-1];
  6. matrices with complex rational coefficients: CRM[0],...,CRM[M0-1;
  7. polynomials with complex rational coefficients: PCR[0],...,PCR[M0-1];
  8. matrices with polynomial complex rational coefficients: PCRM[0],...,PCRM [M0-1];
  9. matrices with coefficients (mod p): mM[0],...,mM[M0-1];
  10. polynomials with coefficients (mod p): Pm[0],...,Pm[M0-1];
  11. matrices with polynomial coefficients (mod p): PmM[0],...,PmM [M0-1];

These arrays always contain the appropriate zero object until replaced by either an object entered by the user or one resulting from a calculation.

4. Saving for future sessions.

When each of the programs cmatr, cmatcr, cmatm is run, the following files are respectively opened in the user's current directory:

(i) cR, cPR, cRM, cPRM;
(ii) cCR, cPCR, cCRM, cPCRM;
(iii) cPm, cmM, cPmM.
If these files do not already exist, they are created, with contents corresponding to appropriate zero arithmetic objects. At the end of each computing session, the user is given the option of saving data for further re-use in future sessions.

5. Memory bank. We use a memory banking algorithm implemented by Peter Adams. Previously, MPI's and other data structures were malloced and freed whenever they were required, which proved to be very time consuming. About 50% of the execution time was spent in calls to malloc() and free().

Now, rather than freeing when we have finished using them, we place them on a list of free MPI's (and corresponding lists for other data structures). When another MPI is required, if there is one of an appropriate size on the list, it can be used rather than calling malloc().

Any suggestions for improvement, as well as bug reports, should be reported to the author:

K. R. Matthews
email: webmaster@numbertheory.org
http://www.numbertheory.org/keith.html

20th June 2006