(* ---------------------------------------------------------------------------- * $Id: LINALGI.md,v 1.3 1995/11/05 09:21:55 kredel Exp $ * ---------------------------------------------------------------------------- * This file is part of MAS. * ---------------------------------------------------------------------------- * Copyright (c) 1989 - 1992 Universitaet Passau * ---------------------------------------------------------------------------- * $Log: LINALGI.md,v $ * Revision 1.3 1995/11/05 09:21:55 kredel * Fixed comments. * * Revision 1.2 1992/02/12 17:33:08 pesch * Moved CONST definition to the right place * * Revision 1.1 1992/01/22 15:12:31 kredel * Initial revision * * ---------------------------------------------------------------------------- *) DEFINITION MODULE LINALGI; (* MAS Linear Algebra Integer Definition Module. *) (*------------------------------------------------------------------------- Programmierpraktikum SS 1990: JUEGEN MUELLER, 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. --------------------------------------------------------------------------*) FROM MASSTOR IMPORT LIST;CONSTrcsid = "$Id: LINALGI.md,v 1.3 1995/11/05 09:21:55 kredel Exp $";CONSTcopyright = "Copyright (c) 1989 - 1992 Universitaet Passau";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 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;VARC, 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. A is an integer matrix. B 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;VARC, 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;VARL, 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. *)ENDLINALGI. (* -EOF- *)