home *** CD-ROM | disk | FTP | other *** search
/ Crawly Crypt Collection 2 / crawlyvol2.bin / program / misc / mas / mashelp / linalgi.def < prev    next >
Encoding:
Modula Definition  |  1990-10-15  |  8.2 KB  |  231 lines

  1.  
  2. (*-------------------------------------------------------------------------
  3. Definition Module: Linear Algebra Integer 
  4.  
  5. Programmierpraktikum SS 1990: JÜRGEN MÜLLER, Heinz Kredel 
  6.  
  7. Contents: Standartoperations for matrix and vector manipulations,  
  8.           Gaussian elimination, LU-Decomposition, Solve,    
  9.           Inversion, Nullspace, Determinant. 
  10.  
  11. Stand : 27.09.90, Juergen Mueller                         
  12.         from then date of the file, Heinz Kredel             
  13.  
  14. Remarks: A vector is represented as a list of elements.
  15.          The elements may be integers or rational numbers.
  16.          A matix is represented as a list of vectors.
  17.          In most circumstances these vectors are interpreted row 
  18.          vectors, but they can also be interpreted as column vectors.
  19.  
  20. --------------------------------------------------------------------------*)
  21.  
  22. DEFINITION MODULE LinAlgI;
  23.  
  24. FROM MASSTOR IMPORT LIST;
  25.  
  26.  
  27. PROCEDURE IUM(m, n : LIST): LIST;
  28. (*Integer unit matrix. m, n integer. An (m x n) integer unit 
  29. matrix is returned. *)
  30.  
  31.  
  32. PROCEDURE IVWRITE(A : LIST);
  33. (*Integer vector write. A is an integer vector. A is written 
  34. to the output stream. *)
  35.  
  36.  
  37. PROCEDURE IMWRITE(A : LIST);
  38. (*Integer matrix write. A is an integer matrix. A is written 
  39. to the output stream. *)
  40.  
  41.  
  42. PROCEDURE IVVDIF(A, B : LIST): LIST;
  43. (*Integer vector difference. A and B are integer vectors. 
  44. The integer vector C = A - B is returned. *)
  45.  
  46.  
  47. PROCEDURE IKM(A, B : LIST): LIST;
  48. (*Integer vector component product. IKM returns the difference of 
  49. the product of the integer vector A with FIRST(B) and the product of 
  50. the integer vector B with FIRST(A). C = A * FIRST(B) - B * FIRST(A).
  51. C is an integer vector. *)
  52.  
  53.  
  54. PROCEDURE IVVSUM(A, B : LIST): LIST;
  55. (*Integer vector vector sum. A and B are integer vectors. 
  56. An integer vector C = A + B is returned. *)
  57.  
  58.  
  59. PROCEDURE IVSVSUM(A, B : LIST): LIST;
  60. (*Integer vector scalar and vector sum. A and B are integer vectors.
  61. An integer vector C = A + FIRST(B) is returned. *)
  62.  
  63.  
  64. PROCEDURE IVSSUM(A : LIST): LIST;
  65. (*Integer vector scalar sum. A is an integer vector. An integer 
  66. vector ?? C = (a1+a2+...+an) is returned. *)
  67.  
  68.  
  69. PROCEDURE IVSVPROD(A, B : LIST): LIST;
  70. (*Integer vector scalar and vector product. A and B are integer vectors.
  71. An integer vector C = (a1*FIRST(B), ..., an*FIRST(B) ) is returned. *)
  72.  
  73.  
  74. PROCEDURE IVVPROD(A, B : LIST): LIST;
  75. (*Integer vector vectors product. A and B are integer vectors.
  76. An integer vector C = (a1*b1, ..., an*bn) is returned. *)
  77.  
  78.  
  79. PROCEDURE IVSPROD(A, B : LIST): LIST;
  80. (*Integer vector scalar product. A and B are integer vectors.
  81. An integer C = a1*b1 + ... + an*bn is returned. *)
  82.  
  83.  
  84. PROCEDURE IVMAX(M : LIST): LIST;
  85. (*Integer vector maximum norm. M is an integer vector. 
  86. An integer a = maximum absolute value M(i) is returned. *)
  87.  
  88.  
  89. PROCEDURE IVLC(a, A, b, B : LIST): LIST;
  90. (*Integer vector linear combination. A and B are integer vectors. 
  91. a and b are integers. An integer vector C = a*A + b*B is returned. *)
  92.  
  93.  
  94. PROCEDURE IVSQ(a, A: LIST): LIST;
  95. (*Integer vector scalar quotient. A is an integer vector. 
  96. a is an integer. An integer vector C = A/a is returned. 
  97. a must divide each element of A exactly.  *)
  98.  
  99.  
  100. PROCEDURE IVFRNV(A: LIST): LIST;
  101. (*Integer vector from rational number vector. A is a rational 
  102. number vector. A is muliplied by a common multiple of its 
  103. denominators, then the denominators are removed. An integer 
  104. vector C = lcm(denom(A)) * A is returned.  *)
  105.  
  106.  
  107. PROCEDURE IVFRNV1(A, B : LIST; VAR C, D: LIST);
  108. (*Integer vector from rational number vector. A and B are 
  109. rational number vectors. A and B are muliplied by a common 
  110. multiple of their denominators, then the denominators are 
  111. removed. C and D are integer vectors, such that 
  112. C = lcm(denom(A),denom(B))*A and D = lcm(denom(A),denom(B))*B. *)
  113.  
  114.  
  115. PROCEDURE IMPROD(A, B : LIST): LIST;
  116. (*Integer matrix product. A and B are integer matrices. 
  117. An integer matrix C = A * B is returned, if the number of 
  118. coloums of A is equal to the number of rows of B, 
  119. otherwise the empty matrix is returned. *)
  120.  
  121.  
  122. PROCEDURE IMSUM(A, B : LIST): LIST;
  123. (*Integer matrix sum. A and B are integer matrices. 
  124. An integer matrix C = A + B is returned. *)
  125.  
  126.  
  127. PROCEDURE IMDIF(A, B : LIST): LIST;
  128. (*Integer matrix difference. A and B are integer matrices. 
  129. An integer matrix C = A - B is returned. *)
  130.  
  131.  
  132. PROCEDURE ISMPROD(A, B : LIST): LIST;
  133. (*Integer scalar and matrix product. B is an integer matrix. 
  134. A is an integer. An integer matrix C = A * B is returned. *)
  135.  
  136.  
  137. PROCEDURE IMMAX(M : LIST): LIST;
  138. (*Integer matrix maximum norm. M is an integer matrix. 
  139. An integer a = maximum absolute value M(i,j) is returned. *)
  140.  
  141.  
  142. PROCEDURE IMFRNM(A : LIST): LIST;
  143. (*Integer matrix from rational number matrix. A is a rational 
  144. number row matix. The rows of A are muliplied by a common 
  145. multiple of its denominators, then the denominators are 
  146. removed. An integer matix C is returned, such that for 
  147. all rows C(i) = lcm(denom(A(i))) * A(i). *)
  148.  
  149.  
  150. PROCEDURE IMFRNM1(A, B : LIST; VAR C, D: LIST);
  151. (*Integer matrix from rational number matrix. A is a rational 
  152. number row matix. B is a rational number column matix. 
  153. The rows of A and the rows of B are muliplied by
  154. a common multiple of their denominators, then the 
  155. denominators are removed. C and D are integer matices,
  156. such that C(i) = lcm(denom(A(i)),B(i)) * A(i) and
  157. D(i) = lcm(denom(A(i)),B(i)) * B(i). *)
  158.  
  159.  
  160. PROCEDURE IMGELUD(M : LIST; VAR L, U: LIST);
  161. (*Integer matrix Gaussian elimination LU-decomposition. 
  162. M is an integer matrix represented rowwise. L is a lower 
  163. triangular integer matrix represented columnwise.
  164. U is an upper triangular integer matrix represented rowwise.
  165. M = L * U for appropriate modifications of L and U. The pivot 
  166. operations and exact division factors are also recorded in L. *)
  167.  
  168.  
  169. PROCEDURE IMLT(L, b : LIST): LIST;
  170. (*Integer lower triangular matrix transformation. 
  171. L is a lower triangular integer matrix represented 
  172. columnwise as generated by IMGELUD. b is an integer vector. 
  173. An integer vector u = L * b is returned, such that 
  174. if M * x = b and M = L * U, then U * x = u. *)
  175.  
  176.  
  177. PROCEDURE IMUT(U, b : LIST): LIST;
  178. (*Integer upper triangular matrix transformation. 
  179. U is an upper triangular integer matrix represented rowwise
  180. as generated by IMGELUD. b is an integer vector 
  181. b = L * b' as generated by IMLT. A rational number (!) vector x, 
  182. such that U * x = b is returned. If no such x exists, then an 
  183. empty vector is returned. If more than one such x exists, then 
  184. for free x(i), x(i) = 0 is taken. *)
  185.  
  186.  
  187. PROCEDURE IMGE(M : LIST): LIST;
  188. (*Integer matrix Gaussian elimination. M is a (n x m) integer 
  189. matrix. A (n x m) integer matrix resulting from Gaussian 
  190. elimination is returned. IMGELUD is called. *)
  191.  
  192.  
  193. PROCEDURE IMSDS(L, U, b : LIST): LIST;
  194. (*Integer matrix solve decomposed system. L is a lower 
  195. triangular integer matrix represented columnwise, U is an upper 
  196. triangular integer matrix represented rowwise. L and U as 
  197. generated by IMGELUD. If M = L * U, then a rational number (!) 
  198. vector x, such that M * x = b is returned. If no such x exists, 
  199. then an empty vector is returned. If more than one such x exists, 
  200. then for free x(i), x(i) = 0 is taken. *)
  201.  
  202.  
  203. PROCEDURE RNMINVI(A : LIST): LIST;
  204. (*Rational number matrix inversion, integer algorithm. A is a 
  205. rational number matrix represented rowwise. If it exists, 
  206. the inverse matrix of A is returned, otherwise an empty matrix 
  207. is returned. The integer Gaussian elimination IMGELUD is used. *)
  208.  
  209.  
  210. PROCEDURE IMUNS(U : LIST): LIST;
  211. (*Integer matrix upper triangular matrix solution null space. 
  212. U is an upper triangular integer matrix represented rowwise
  213. as generated by IMGELUD. A matrix X of linear independent rational 
  214. number vectors x is returned, such that for each x in X, U * x = 0 holds. 
  215. If only x = 0 satisfies the condition U * x = 0, then the 
  216. matrix X is empty. *)
  217.  
  218.  
  219. PROCEDURE IMDETL(M : LIST): LIST;
  220. (*Integer matrix determinant, using Laplace expansion. 
  221. M is an integer matrix. The determinant of M is returned. *)
  222.  
  223.  
  224. PROCEDURE IMDET(M : LIST): LIST;
  225. (*Integer matrix determinant, using Gaussian elimination. 
  226. M is an integer matrix. The determinant of M is returned. *)
  227.  
  228.  
  229. END LinAlgI.
  230.  
  231.