(*-------------------------------------------------------------------------
Definition Module: Linear Algebra Integer 

Programmierpraktikum SS 1990: JšRGEN MšLLER, Heinz Kredel 

Contents: Standartoperations for matrix and vector manipulations,  
          Gaussian elimination, LU-Decomposition, Solve,    
          Inversion, Nullspace, Determinant. 

Stand : 27.09.90, Juergen Mueller                         
        from then date of the file, Heinz Kredel             

Remarks: A vector is represented as a list of elements.
         The elements may be integers or rational numbers.
         A matix is represented as a list of vectors.
         In most circumstances these vectors are interpreted row 
         vectors, but they can also be interpreted as column vectors.

--------------------------------------------------------------------------*)

DEFINITION MODULE LinAlgI;

FROM MASSTOR IMPORT LIST;


PROCEDURE IUM(m, n : LIST): LIST;
(*Integer unit matrix. m, n integer. An (m x n) integer unit 
matrix is returned. *)


PROCEDURE IVWRITE(A : LIST);
(*Integer vector write. A is an integer vector. A is written 
to the output stream. *)


PROCEDURE IMWRITE(A : LIST);
(*Integer matrix write. A is an integer matrix. A is written 
to the output stream. *)


PROCEDURE IVVDIF(A, B : LIST): LIST;
(*Integer vector difference. A and B are integer vectors. 
The integer vector C = A - B is returned. *)
 

PROCEDURE IKM(A, B : LIST): LIST;
(*Integer vector component product. IKM returns the difference of 
the product of the integer vector A with FIRST(B) and the product of 
the integer vector B with FIRST(A). C = A * FIRST(B) - B * FIRST(A).
C is an integer vector. *)


PROCEDURE IVVSUM(A, B : LIST): LIST;
(*Integer vector vector sum. A and B are integer vectors. 
An integer vector C = A + B is returned. *)


PROCEDURE IVSVSUM(A, B : LIST): LIST;
(*Integer vector scalar and vector sum. A and B are integer vectors.
An integer vector C = A + FIRST(B) is returned. *)


PROCEDURE IVSSUM(A : LIST): LIST;
(*Integer vector scalar sum. A is an integer vector. An integer 
vector ?? C = (a1+a2+...+an) is returned. *)


PROCEDURE IVSVPROD(A, B : LIST): LIST;
(*Integer vector scalar and vector product. A and B are integer vectors.
An integer vector C = (a1*FIRST(B), ..., an*FIRST(B) ) is returned. *)


PROCEDURE IVVPROD(A, B : LIST): LIST;
(*Integer vector vectors product. A and B are integer vectors.
An integer vector C = (a1*b1, ..., an*bn) is returned. *)


PROCEDURE IVSPROD(A, B : LIST): LIST;
(*Integer vector scalar product. A and B are integer vectors.
An integer C = a1*b1 + ... + an*bn is returned. *)


PROCEDURE IVMAX(M : LIST): LIST;
(*Integer vector maximum norm. M is an integer vector. 
An integer a = maximum absolute value M(i) is returned. *)


PROCEDURE IVLC(a, A, b, B : LIST): LIST;
(*Integer vector linear combination. A and B are integer vectors. 
a and b are integers. An integer vector C = a*A + b*B is returned. *)


PROCEDURE IVSQ(a, A: LIST): LIST;
(*Integer vector scalar quotient. A is an integer vector. 
a is an integer. An integer vector C = A/a is returned. 
a must divide each element of A exactly.  *)


PROCEDURE IVFRNV(A: LIST): LIST;
(*Integer vector from rational number vector. A is a rational 
number vector. A is muliplied by a common multiple of its 
denominators, then the denominators are removed. An integer 
vector C = lcm(denom(A)) * A is returned.  *)


PROCEDURE IVFRNV1(A, B : LIST; VAR C, D: LIST);
(*Integer vector from rational number vector. A and B are 
rational number vectors. A and B are muliplied by a common 
multiple of their denominators, then the denominators are 
removed. C and D are integer vectors, such that 
C = lcm(denom(A),denom(B))*A and D = lcm(denom(A),denom(B))*B. *)


PROCEDURE IMPROD(A, B : LIST): LIST;
(*Integer matrix product. A and B are integer matrices. 
An integer matrix C = A * B is returned, if the number of 
coloums of A is equal to the number of rows of B, 
otherwise the empty matrix is returned. *)


PROCEDURE IMSUM(A, B : LIST): LIST;
(*Integer matrix sum. A and B are integer matrices. 
An integer matrix C = A + B is returned. *)


PROCEDURE IMDIF(A, B : LIST): LIST;
(*Integer matrix difference. A and B are integer matrices. 
An integer matrix C = A - B is returned. *)


PROCEDURE ISMPROD(A, B : LIST): LIST;
(*Integer scalar and matrix product. B is an integer matrix. 
A is an integer. An integer matrix C = A * B is returned. *)


PROCEDURE IMMAX(M : LIST): LIST;
(*Integer matrix maximum norm. M is an integer matrix. 
An integer a = maximum absolute value M(i,j) is returned. *)


PROCEDURE IMFRNM(A : LIST): LIST;
(*Integer matrix from rational number matrix. A is a rational 
number row matix. The rows of A are muliplied by a common 
multiple of its denominators, then the denominators are 
removed. An integer matix C is returned, such that for 
all rows C(i) = lcm(denom(A(i))) * A(i). *)


PROCEDURE IMFRNM1(A, B : LIST; VAR C, D: LIST);
(*Integer matrix from rational number matrix. A is a rational 
number row matix. B is a rational number column matix. 
The rows of A and the rows of B are muliplied by
a common multiple of their denominators, then the 
denominators are removed. C and D are integer matices,
such that C(i) = lcm(denom(A(i)),B(i)) * A(i) and
D(i) = lcm(denom(A(i)),B(i)) * B(i). *)


PROCEDURE IMGELUD(M : LIST; VAR L, U: LIST);
(*Integer matrix Gaussian elimination LU-decomposition. 
M is an integer matrix represented rowwise. L is a lower 
triangular integer matrix represented columnwise.
U is an upper triangular integer matrix represented rowwise.
M = L * U for appropriate modifications of L and U. The pivot 
operations and exact division factors are also recorded in L. *)


PROCEDURE IMLT(L, b : LIST): LIST;
(*Integer lower triangular matrix transformation. 
L is a lower triangular integer matrix represented 
columnwise as generated by IMGELUD. b is an integer vector. 
An integer vector u = L * b is returned, such that 
if M * x = b and M = L * U, then U * x = u. *)


PROCEDURE IMUT(U, b : LIST): LIST;
(*Integer upper triangular matrix transformation. 
U is an upper triangular integer matrix represented rowwise
as generated by IMGELUD. b is an integer vector 
b = L * b' as generated by IMLT. A rational number (!) vector x, 
such that U * x = b is returned. If no such x exists, then an 
empty vector is returned. If more than one such x exists, then 
for free x(i), x(i) = 0 is taken. *)


PROCEDURE IMGE(M : LIST): LIST;
(*Integer matrix Gaussian elimination. M is a (n x m) integer 
matrix. A (n x m) integer matrix resulting from Gaussian 
elimination is returned. IMGELUD is called. *)


PROCEDURE IMSDS(L, U, b : LIST): LIST;
(*Integer matrix solve decomposed system. L is a lower 
triangular integer matrix represented columnwise, U is an upper 
triangular integer matrix represented rowwise. L and U as 
generated by IMGELUD. If M = L * U, then a rational number (!) 
vector x, such that M * x = b is returned. If no such x exists, 
then an empty vector is returned. If more than one such x exists, 
then for free x(i), x(i) = 0 is taken. *)


PROCEDURE RNMINVI(A : LIST): LIST;
(*Rational number matrix inversion, integer algorithm. A is a 
rational number matrix represented rowwise. If it exists, 
the inverse matrix of A is returned, otherwise an empty matrix 
is returned. The integer Gaussian elimination IMGELUD is used. *)


PROCEDURE IMUNS(U : LIST): LIST;
(*Integer matrix upper triangular matrix solution null space. 
U is an upper triangular integer matrix represented rowwise
as generated by IMGELUD. A matrix X of linear independent rational 
number vectors x is returned, such that for each x in X, U * x = 0 holds. 
If only x = 0 satisfies the condition U * x = 0, then the 
matrix X is empty. *)


PROCEDURE IMDETL(M : LIST): LIST;
(*Integer matrix determinant, using Laplace expansion. 
M is an integer matrix. The determinant of M is returned. *)


PROCEDURE IMDET(M : LIST): LIST;
(*Integer matrix determinant, using Gaussian elimination. 
M is an integer matrix. The determinant of M is returned. *)


END LinAlgI.