Anonymous user
Gaussian elimination: Difference between revisions
Added a Modula-3 implementation
m (added a reference to a Wikipedia article.) |
(Added a Modula-3 implementation) |
||
Line 2,186:
end
</lang>
=={{header|Modula-3}}==
This implementation defines a generic <code>Matrix</code> type so that the code can be used with different types. As a bonus, we implemented it to work with <i>rings</i> rather than fields, and tested it on two rings: the ring of integers and the ring of integers modulo 46. We include the interface of a ring modulo 46 below; the project's <code>m3makefile</code> (not included) is set up to automatically generates an interface and module for a matrix over each ring.
;requirements of the generic type
The <code>Matrix</code> needs its generic type to implement the following:
* It must have a type <code>T</code>, as per Modula-3 convention.
* It must have procedures
** <code>Nonzero(a: T): BOOLEAN</code>, which indicates whether <code>a</code> is nonzero;
** <code>Minus(a, b: T): T</code> and <code>Times(a, b: T): T</code>, which return the results of the procedures' names; and
** <code>Print(a: T)</code> which does what the name implies.
;Matrix interface
<lang modula3>GENERIC INTERFACE Matrix(RingElem);
(*
"RingElem" must export the following:
- a type T;
- procedures
+ "Nonzero(a: T): BOOLEAN", which indicates whether "a" is nonzero;
+ "Minus(a, b: T): T" and "Times(a, b: T): T",
which return the results you'd guess from the procedures' names; and
+ "Print(a: T)", which does what the name implies.
*)
TYPE
T <: Public;
Public = OBJECT
METHODS
init(READONLY data: ARRAY OF ARRAY OF RingElem.T): T;
(* use this to copy the entries in "data"; returns "self" *)
initDimensions(m, n: CARDINAL): T;
(* use this for an mxn matrix of random entries *)
num_rows(): CARDINAL;
(* returns the number of rows in "self" *)
num_cols(): CARDINAL;
(* returns the number of columns in "self" *)
entries(): REF ARRAY OF ARRAY OF RingElem.T;
(* returns the entries in "self" *)
triangularize();
(*
Performs Gaussian elimination in the context of a ring.
We can add scalar multiples of rows,
and we can swap rows, but we may lack multiplicative inverses,
so we cannot necessarily obtain 1 as a row's first entry.
*)
END;
PROCEDURE PrintMatrix(m: T);
(* prints the matrix row-by-row; sorry, no special padding to line up columns *)
END Matrix.</lang>
;Matrix implementation
<lang modula3>GENERIC MODULE Matrix(RingElem);
IMPORT IO;
TYPE
REVEAL T = Public BRANDED OBJECT
rows, cols: CARDINAL;
data: REF ARRAY OF ARRAY OF RingElem.T;
OVERRIDES
init := Init;
initDimensions := InitDimensions;
num_rows := Rows;
num_cols := Columns;
entries := Entries;
triangularize := Triangularize;
END;
PROCEDURE Init(self: T; READONLY d: ARRAY OF ARRAY OF RingElem.T): T =
BEGIN
self.rows := NUMBER(d);
self.cols := NUMBER(d[0]);
self.data := NEW(REF ARRAY OF ARRAY OF RingElem.T, self.rows, self.cols);
FOR i := FIRST(d) TO LAST(d) DO
FOR j := FIRST(d[0]) TO LAST(d[0]) DO
self.data[i-FIRST(d)][j-FIRST(d[0])] := d[i][j];
END;
END;
RETURN self;
END Init;
PROCEDURE InitDimensions(self: T; r, c: CARDINAL): T =
BEGIN
self.rows := r;
self.cols := c;
self.data := NEW(REF ARRAY OF ARRAY OF RingElem.T, r, c);
RETURN self;
END InitDimensions;
PROCEDURE Rows(self: T): CARDINAL =
BEGIN
RETURN self.rows;
END Rows;
PROCEDURE Columns(self: T): CARDINAL =
BEGIN
RETURN self.cols;
END Columns;
PROCEDURE Entries(self: T): REF ARRAY OF ARRAY OF RingElem.T =
BEGIN
RETURN self.data;
END Entries;
PROCEDURE SwapRows(VAR data: ARRAY OF ARRAY OF RingElem.T; i, j: CARDINAL) =
(* swaps rows i and j of data *)
VAR
a: RingElem.T;
BEGIN
WITH Ai = data[i], Aj = data[j], m = FIRST(data[0]), n = LAST(data[0]) DO
FOR k := m TO n DO
a := Ai[k];
Ai[k] := Aj[k];
Aj[k] := a;
END;
END;
END SwapRows;
PROCEDURE PivotExists(
VAR data: ARRAY OF ARRAY OF RingElem.T;
r: CARDINAL;
VAR i: CARDINAL;
j: CARDINAL
): BOOLEAN =
(*
Returns true iff column j of data has a pivot in some row at or after r.
The row with a pivot is stored in i.
*)
VAR
searching := TRUE;
result := LAST(data) + 1;
BEGIN
i := r;
WHILE searching AND i <= LAST(data) DO
IF RingElem.Nonzero(data[i,j]) THEN
searching := FALSE;
result := i;
ELSE
INC(i);
END;
END;
RETURN NOT searching;
END PivotExists;
PROCEDURE Pivot(VAR data: ARRAY OF ARRAY OF RingElem.T; i, j, k: CARDINAL) =
(*
Pivots on row i, column j to eliminate row k, column j.
*)
BEGIN
WITH n = LAST(data[0]), Ai = data[i], Ak = data[k] DO
VAR a := Ai[j]; b := Ak[j];
BEGIN
FOR l := j TO n DO
IF RingElem.Nonzero(Ai[l]) THEN
Ak[l] := RingElem.Minus(
RingElem.Times(Ak[l], a),
RingElem.Times(Ai[l], b)
);
ELSE
Ak[l] := RingElem.Times(Ak[l], a);
END;
END;
END;
END;
END Pivot;
PROCEDURE Triangularize(self: T) =
VAR
i: CARDINAL;
r := FIRST(self.data[0]);
BEGIN
WITH data = self.data, m = FIRST(data[0]), n = LAST(data[0]) DO
FOR j := m TO n DO
IF PivotExists(data^, r, i, j) THEN
IF i # j THEN
SwapRows(data^, i, r);
END;
FOR k := r + 1 TO LAST(data^) DO
IF RingElem.Nonzero(data[k][j]) THEN
Pivot(data^, r, j, k);
END;
END;
INC(r);
END;
END;
END;
END Triangularize;
PROCEDURE PrintMatrix(self: T) =
BEGIN
WITH data = self.data DO
FOR i := FIRST(data^) TO LAST(data^) DO
IO.Put("[ ");
WITH Ai = data[i] DO
FOR j := FIRST(Ai) TO LAST(Ai) DO
RingElem.Print(Ai[j]);
IF j # LAST(Ai) THEN
IO.PutChar(' ');
END;
END;
END;
IO.Put(" ]\n");
END;
END;
END PrintMatrix;
BEGIN
END Matrix.</lang>
; interface for the ring of integers modulo an integer
<lang modula3>INTERFACE ModularRing;
(*
Implements arithmetic modulo a nonzero integer.
Assertions check that the modulus is nonzero.
*)
TYPE
T = RECORD
value, modulus: CARDINAL;
END;
PROCEDURE Init(VAR a: T; value: INTEGER; modulus: CARDINAL);
(* initializes a to the given value and modulus *)
PROCEDURE Nonzero(n: T): BOOLEAN;
PROCEDURE Plus(a, b: T): T;
PROCEDURE Minus(a, b: T): T;
PROCEDURE Times(a, b: T): T;
PROCEDURE Print(a: T; withModulus := FALSE);
(*
when "withModulus" is "TRUE",
this adds after "a" the letter "m",
followed by the modulus
*)
END ModularRing.</lang>
;test implementation
It's fairly easy to initialize an array of types in Modula-3, but it can get cumbersome with structured types, so we wrote a procedure to convert an integer matrix to a matrix of integers modulo a number.
<lang modula3>MODULE GaussianElimination EXPORTS Main;
IMPORT IO, ModularRing AS MR, IntMatrix AS IM, ModMatrix AS MM;
CONST
(* data to set up the matrices *)
A1 = ARRAY OF INTEGER { 2, 1, 0 };
A2 = ARRAY OF INTEGER { 1, 2, 0 };
A3 = ARRAY OF INTEGER { 0, 3, 0 };
A = ARRAY OF ARRAY OF INTEGER { A1, A2, A3 };
B1 = ARRAY OF INTEGER { 4, 8, 0, -4, 0 };
B2 = ARRAY OF INTEGER { -3, -6, 0, 9, 0 };
B3 = ARRAY OF INTEGER { 1, 3, 5, 7, 2 };
B4 = ARRAY OF INTEGER { 7, 5, 3, 1, 2 };
B = ARRAY OF ARRAY OF INTEGER { B1, B2, B3, B4 };
PROCEDURE IntToModArray(READONLY A: IM.T; VAR B: MM.T; mod: CARDINAL) =
(*
copies a two-dimensional array of integers
to a two-dimension array of integers modulo "mod"
*)
BEGIN
B := NEW(MM.T).initDimensions(A.num_rows(), A.num_cols());
WITH Adata = A.entries(), Bdata = B.entries() DO
FOR i := FIRST(Adata^) TO LAST(Adata^) DO
WITH Ai = Adata[i], Bi = Bdata[i] DO
FOR j := FIRST(Ai) TO LAST(Ai) DO
MR.Init(Bi[j], Ai[j], mod);
END;
END;
END;
END;
END IntToModArray;
VAR
M: IM.T;
N: MM.T;
BEGIN
(* triangularize the data in A *)
M := NEW(IM.T).init(A);
IO.Put("Initial A:\n");
IM.PrintMatrix(M);
IO.PutChar('\n');
M.triangularize();
IO.Put("Final A:\n");
IM.PrintMatrix(M);
IO.PutChar('\n');
IO.PutChar('\n');
(* triangularize the data in B, all computations modulo 46 *)
M := NEW(IM.T).init(B);
IntToModArray(M, N, 46);
IO.Put("Initial B:\n");
MM.PrintMatrix(N);
IO.PutChar('\n');
N.triangularize();
IO.Put("Final B:\n");
MM.PrintMatrix(N);
IO.PutChar('\n');
END GaussianElimination.</lang>
{{out}}
<pre>
Initial A:
[ 2 1 0 ]
[ 1 2 0 ]
[ 0 3 0 ]
Final A:
[ 2 1 0 ]
[ 0 3 0 ]
[ 0 0 0 ]
Initial B:
[ 4 8 0 42 0 ]
[ 43 40 0 9 0 ]
[ 1 3 5 7 2 ]
[ 7 5 3 1 2 ]
Final B:
[ 4 8 0 42 0 ]
[ 0 4 20 32 8 ]
[ 0 0 32 38 44 ]
[ 0 0 0 24 0 ]
</pre>
=={{header|OCaml}}==
| |||