home *** CD-ROM | disk | FTP | other *** search
/ Crawly Crypt Collection 2 / crawlyvol2.bin / program / misc / mas / mashelp / linalgrn.def < prev    next >
Encoding:
Modula Definition  |  1990-10-15  |  9.9 KB  |  291 lines
  1.  
  2. (*-------------------------------------------------------------------------
  3. Definition Module: Linear Algebra Rational Number 
  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 LinAlgRN;
  23.  
  24. FROM MASSTOR IMPORT LIST;
  25.  
  26.  
  27. (* --------------- arbitrary matrices ------------- *)
  28.  
  29. PROCEDURE MDIM(M : LIST): LIST;
  30. (*Matrix dimension. M is a matrix. MDIM returns
  31. max(#row,#column) of M. *)
  32.  
  33.  
  34. PROCEDURE MGET(M, k, l : LIST): LIST;
  35. (*Matrix get. M is a matrix. k, l are integers, 0 <= k <= #rows(M),
  36. 0 <= l <= #columns(M). MGET returns the element M(k,l) of matrix M. *)
  37.  
  38.  
  39. PROCEDURE MSET(M, k, l, x : LIST): LIST;
  40. (*Matrix set. M is a matrix. k, l are integers, 0 <= k <= #rows(M),
  41. 0 <= l <= #columns(M). MSET sets the element M(k,l) to x. 
  42. The new matrix is returned. *) 
  43.  
  44.  
  45. PROCEDURE VDELEL(V, i : LIST): LIST;
  46. (*Vector delete element. V is a vector. The i-th element of V 
  47. is deleted. 0 <= i <= length(V). *)
  48.  
  49.  
  50. PROCEDURE MDELCOL(M, i : LIST): LIST;
  51. (*Matrix delete column. M is a vector of row vectors. In each 
  52. row the i-th element is deleted, 0 <= i <= #columns(M). The new 
  53. matrix is returned. *)
  54.  
  55.  
  56. PROCEDURE MMINOR(M, i, j : LIST): LIST;
  57. (*Matrix minor. M is a vector of row vectors. The i-th column, 
  58. 0 <= i <= #rows(M), and in each remaining row the j-th element,
  59. 0 <= j <= #columns(M), is deleted. *)
  60.  
  61.  
  62. PROCEDURE MTRANS(M : LIST): LIST;
  63. (*Matrix transpose. M is a matrix. The transposed matrix is returned. *)
  64.  
  65.  
  66. PROCEDURE VEL(a, n : LIST): LIST;
  67. (*Vector elements. A vector of length n with elements a is returned. *)
  68.  
  69.  
  70. PROCEDURE MFILL(M, m, n: LIST): LIST;
  71. (*Matrix fill. M is an upper triangular matrix. A (m x n) matrix 
  72. with zeros in the lower triangular part is returned. *)
  73.  
  74.  
  75. PROCEDURE MRANG(U: LIST): LIST;
  76. (*Matrix rang. U is an upper triangular matrix from a
  77. LU-decomposition. The rang of U is returned. *)
  78.  
  79.  
  80. (* --------------- rational number matrices ------------- *)
  81.  
  82. PROCEDURE RNMHILBERT(m, n : LIST): LIST;
  83. (*Rational number matrix HILBERT. m, n integer. A (m x n) rational 
  84. number hilbert matrix is returned. *)
  85.  
  86.  
  87. PROCEDURE RNUM(m, n : LIST): LIST;
  88. (*Rational number unit matrix. m, n integer. A (m x n) rational 
  89. number unit matrix is returned. *)
  90.  
  91.  
  92. PROCEDURE RNVWRITE(A : LIST);
  93. (*Rational number vector write. A is a rational number vector. 
  94. A is written to the output stream. *)
  95.  
  96.  
  97. PROCEDURE RNVREAD(): LIST;
  98. (*Rational number vector read. A rational number vector is 
  99. read from the input stream, and returned. *)
  100.  
  101.  
  102. PROCEDURE RNMWRITE(A : LIST);
  103. (*Rational number matrix write. A is a rational number matrix. 
  104. A is written to the output stream. *)
  105.  
  106.  
  107. PROCEDURE RNMREAD(): LIST;
  108. (*Rational number matrix read. A rational number matrix is 
  109. read from the input stream, and returned. *)
  110.  
  111.  
  112. PROCEDURE RNVFIV(A : LIST): LIST;
  113. (*Rational number vector from integer vector. A is an integer 
  114. vector. A rational number vector with denominators 1 
  115. and nominators equal to the elements of A is returned. *)
  116.  
  117.  
  118. PROCEDURE RNMFIM(M : LIST): LIST;
  119. (*Rational number matrix from integer matrix. A is an integer 
  120. matrix. A rational number matrix with denominators 1 
  121. and nominators equal to the elements of A is returned. *)
  122.  
  123.  
  124. PROCEDURE RNVDIF(A, B : LIST): LIST;
  125. (*Rational number vector difference. A and B are rational number 
  126. vectors. The rational number vector C = A - B is returned. *)
  127.  
  128.  
  129. PROCEDURE RNVQ(A, B : LIST): LIST;
  130. (*Rational number vector quotient. A and B are rational number vectors.
  131. The rational number vector C = A / FIRST(B) is returned. *)
  132.  
  133.  
  134. PROCEDURE RNVQF(A : LIST): LIST;
  135. (*Rational number vector quotient. A is a rational number vector.  
  136. The rational number vector C = A / FIRST(A) is returned. *)
  137.  
  138.  
  139. PROCEDURE RNVVSUM(A, B : LIST): LIST;
  140. (*Rational number vector vector sum. A and B are rational number vectors. 
  141. A rational number vector C = A + B is returned. *)
  142.  
  143.  
  144. PROCEDURE RNVSVSUM(A, B : LIST): LIST;
  145. (*Rational number vector scalar sum. A and B are rational number vectors.
  146. A rational number vector C = A + FIRST(B) is returned. *)
  147.  
  148.  
  149. PROCEDURE RNVSSUM(A : LIST): LIST;
  150. (*Rational number vector scalar sum. A is a rational number vector.
  151. A rational number vector ?? C = (a1+a2+...+an) is returned. *)
  152.  
  153.  
  154. PROCEDURE RNVSVPROD(A, B : LIST): LIST;
  155. (*Rational number vector scalar vector product. A and B are 
  156. rational number vectors. A rational number vector 
  157. C = (a1*FIRST(B), ..., an*FIRST(B)) is returned. *)
  158.  
  159.  
  160. PROCEDURE RNVVPROD(A, B : LIST): LIST;
  161. (*Rational number vector vector product. A and B are 
  162. rational number vectors. A rational number vector 
  163. C = (a1*b1, ..., an*bn) is returned. *)
  164.  
  165.  
  166. PROCEDURE RNVSPROD(A, B : LIST): LIST;
  167. (*Rational number vector scalar product. A and B are rational 
  168. number vectors. A rational number C = a1*b1 + ... + an*bn is
  169. returned. *)
  170.  
  171.  
  172. PROCEDURE RNVMAX(M : LIST): LIST;
  173. (*Rational number vector maximum norm. M is a rational number 
  174. vector. A rational number a = maximum absolute value M(i) 
  175. is returned. *)
  176.  
  177.  
  178. PROCEDURE RNVLC(a, A, b, B : LIST): LIST;
  179. (*Rational number vector linear combination. A and B are rational 
  180. number vectors. a and b are rational numbers. A rational number vector 
  181. C = a*A + b*B is returned. *)
  182.  
  183.  
  184. PROCEDURE RNSVPROD(a, A : LIST): LIST;
  185. (*Rational number vector product with scalar. A is a rational 
  186. number vector. a is a rational number. A rational number vector
  187. C = a*A is returned. *)
  188.  
  189.  
  190. PROCEDURE RNMSUM(A, B : LIST): LIST;
  191. (*Rational number matrix sum. A and B are rational number
  192. matrices. A rational number matrix C = A + B is returned. *)
  193.  
  194.  
  195. PROCEDURE RNMDIF(A, B : LIST): LIST;
  196. (*Rational number matrix difference. A and B are rational number
  197. matrices. A rational number matrix C = A - B is returned. *)
  198.  
  199.  
  200. PROCEDURE RNMPROD(A, B : LIST): LIST;
  201. (*Rational number matrix product. A and B are rational number
  202. matrices. A rational number matrix C = A * B is returned, if 
  203. the number of coloums of A is equal to the number of rows of B, 
  204. otherwise the empty matrix is returned. *)
  205.  
  206.  
  207. PROCEDURE RNSMPROD(A, B : LIST): LIST;
  208. (*Rational number scalar and matrix product. B is a rational 
  209. number matrix. A is a rational number. A rational number matrix 
  210. C = A * B is returned. *)
  211.  
  212.  
  213. PROCEDURE RNMMAX(M : LIST): LIST;
  214. (*Rational number matrix maximum norm. M is a rational number 
  215. matrix. A rational number a = maximum absolute value M(i,j) 
  216. is returned. *)
  217.  
  218.  
  219. PROCEDURE RNMGE(M : LIST): LIST;
  220. (*Rational number matrix Gaussian elimination. M is a (n x m) 
  221. rational number matrix. A (n x m) rational number matrix
  222. resulting from Gaussian elimination is returned.  
  223. RNMGELUD is called. *)
  224.  
  225.  
  226. PROCEDURE RNMDET(M : LIST): LIST;
  227. (*Rational number matrix determinant, using Gaussian elimination. 
  228. M is a rational number matrix. The determinant of M is returned. *)
  229.  
  230.  
  231. PROCEDURE RNMDETL(M : LIST): LIST;
  232. (*Rational number matrix determinant, using Laplace expansion. 
  233. M is a rational number matrix. The determinant of M is returned. *)
  234.  
  235.  
  236. PROCEDURE RNMGELUD(M : LIST; VAR L, U: LIST);
  237. (*Rational number matrix Gaussian elimination LU-decomposition. 
  238. M is a rational number matrix represented rowwise. L is a lower 
  239. triangular rational number matrix represented columnwise.
  240. U is an upper triangular rational number matrix represented rowwise.
  241. M = L * U for appropriate modifications of L and U. 
  242. The pivot operations are also recorded in L. *)
  243.  
  244.  
  245. PROCEDURE RNMLT(L, b : LIST): LIST;
  246. (*Rational matrix lower triangular matrix transformation. 
  247. L is a lower triangular rational number matrix represented 
  248. columnwise as generated by RNMGELUD. b is a rational number 
  249. vector. A rational number vector u = L * b is returned, 
  250. such that if M * x = b and M = L * U, then U * x = u. *)
  251.  
  252.  
  253. PROCEDURE RNMUT(U, b : LIST): LIST;
  254. (*Rational matrix upper triangular matrix transformation. 
  255. U is an upper triangular rational number matrix represented rowwise
  256. as generated by RNMGELUD. b is a rational number vector 
  257. b = L * b' as generated by RNMLT. A rational number vector x, 
  258. such that U * x = b is returned. If no such x exists, then an 
  259. empty vector is returned. If more than one such x exists, then 
  260. for free x(i), x(i) = 0 is taken. *)
  261.  
  262.  
  263. PROCEDURE RNMSDS(L, U, b : LIST): LIST;
  264. (*Rational number matrix solve decomposed system. 
  265. L is a lower triangular rational number matrix represented 
  266. columnwise, U is an upper triangular rational number matrix 
  267. represented rowwise. L and U as generated by RNMGELUD.
  268. If M = L * U, then a rational number vector x, such that 
  269. M * x = b is returned. If no such x exists, then an empty 
  270. vector is returned. If more than one such x exists, then 
  271. for free x(i), x(i) = 0 is taken. *)
  272.  
  273.  
  274. PROCEDURE RNMINV(A : LIST): LIST;
  275. (*Rational number matrix inversion. A is a rational number matrix 
  276. represented rowwise. If it exists, the inverse matrix of A is 
  277. returned, otherwise an empty matrix is returned. *)
  278.  
  279.  
  280. PROCEDURE RNMUNS(U : LIST): LIST;
  281. (*Rational number matrix upper triangular matrix solution null space. 
  282. U is an upper triangular rational number matrix represented rowwise
  283. as generated by RNMGELUD. A matrix X of linear independent rational 
  284. number vectors x is returned, such that for each x in X, U * x = 0 holds. 
  285. If only x = 0 satisfies the condition U * x = 0, then the 
  286. matrix X is empty. *)
  287.  
  288.  
  289. END LinAlgRN.
  290.  
  291.