Reduced row echelon form: Difference between revisions
Content deleted Content added
SqrtNegInf (talk | contribs) m →{{header|Raku}}: Fix comment: Perl 6 --> Raku |
|||
(40 intermediate revisions by 23 users not shown) | |||
Line 1:
{{wikipedia|Rref#Pseudocode}}
{{task|Matrices}}
Line 55 ⟶ 56:
</pre>
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F ToReducedRowEchelonForm(&M)
V lead = 0
V rowCount = M.len
V columnCount = M[0].len
L(r) 0 .< rowCount
I lead >= columnCount
R
V i = r
L M[i][lead] == 0
i++
I i == rowCount
i = r
lead++
I columnCount == lead
R
swap(&M[i], &M[r])
V lv = M[r][lead]
M[r] = M[r].map(mrx -> mrx / Float(@lv))
L(i) 0 .< rowCount
I i != r
lv = M[i][lead]
M[i] = zip(M[r], M[i]).map((rv, iv) -> iv - @lv * rv)
lead++
V mtx = [[ 1.0, 2.0, -1.0, -4.0],
[ 2.0, 3.0, -1.0, -11.0],
[-2.0, 0.0, -3.0, 22.0]]
ToReducedRowEchelonForm(&mtx)
L(rw) mtx
print(rw.join(‘, ’))</syntaxhighlight>
{{out}}
<pre>
1, 0, 0, -8
0, 1, 0, 1
0, 0, 1, -2
</pre>
=={{header|360 Assembly}}==
{{trans|BBC BASIC}}
<
RREF CSECT
USING RREF,R12
Line 215 ⟶ 259:
PG DC CL48' '
YREGS
END RREF</
{{out}}
<pre>
Line 228 ⟶ 272:
Therefore return this statements are returning the Matrix object itself.
<
var lead:uint, i:uint, j:uint, r:uint = 0;
Line 264 ⟶ 308:
}
return this;
}</
=={{header|Ada}}==
matrices.ads:
<
type Element_Type is private;
Zero : Element_Type;
Line 278 ⟶ 322:
array (Positive range <>, Positive range <>) of Element_Type;
function Reduced_Row_Echelon_form (Source : Matrix) return Matrix;
end Matrices;</
matrices.adb:
<
procedure Swap_Rows (From : in out Matrix; First, Second : in Positive) is
Temporary : Element_Type;
Line 351 ⟶ 395:
return Result;
end Reduced_Row_Echelon_form;
end Matrices;</
Example use: main.adb:
<
with Ada.Text_IO;
procedure Main is
Line 381 ⟶ 425:
Ada.Text_IO.Put_Line ("reduced to:");
Print_Matrix (Reduced);
end Main;</
{{out}}
Line 393 ⟶ 437:
=={{header|Aime}}==
<
{
integer e, f, i, j, lead, r;
Line 459 ⟶ 503:
0;
}</
{{Out}}
<pre> 1 0 0 -8
Line 470 ⟶ 514:
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
<!-- {{does not work with|ELLA ALGOL 68|Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386 - ELLA has not FORMATted transput, also it generates a call to undefined C external }} -->
<
MODE VEC = [0]FIELD;
MODE MAT = [0,0]FIELD;
Line 523 ⟶ 567:
mat repr = $"("n(1 UPB mat-1)(f(vec repr)", "lx)f(vec repr)")"$;
printf((mat repr, mat, $l$))</
{{out}}
<pre>
Line 529 ⟶ 573:
( 0.0000, 1.0000, 0.0000, 1.0000),
( 0.0000, 0.0000, 1.0000, -2.0000))
</pre>
=={{header|ALGOL W}}==
From the pseudo code.
<syntaxhighlight lang="algolw">begin
% replaces M with it's reduced row echelon form %
% M should have bounds ( 0 :: rMax, 0 :: cMax ) %
procedure toReducedRowEchelonForm ( real array M ( *, * )
; integer value rMax, cMax
) ;
begin
integer lead;
lead := 0;
for r := 0 until rMax do begin
integer i;
if lead > cMax then goto done;
i := r;
while M( i, lead ) = 0 do begin
i := i + 1;
if rMax = i then begin
i := r;
lead := lead + 1;
if cMax = lead then goto done
end if_rowCount_eq_i
end while_M_i_lead_eq_0 ;
% Swap rows i and r %
for c := 0 until cMax do begin
real t;
t := M( i, c );
M( i, c ) := M( r, c );
M( r, c ) := t
end swap_rows_i_and_r ;
If M( r, lead ) not = 0 then begin
% divide row r by M[r, lead] %
real rLead;
rLead := M( r, lead );
for c := 0 until cMax do M( r, c ) := M( r, c ) / rLead
end if_M_r_lead_ne_0 ;
for i := 0 until rMax do begin
if i not = r then begin
% Subtract M[i, lead] multiplied by row r from row i %
real iLead;
iLead := M( i, lead );
for c := 0 until cMax do M( i, c ) := M( i, c ) - ( iLead * M( r, c ) )
end if_i_ne_r
end for_i ;
lead := lead + 1
end for_r ;
done:
end toReducedRowEchelonForm ;
% test the toReducedRowEchelonForm procedure %
begin
real array m( 0 :: 2, 0 :: 3 );
M( 0, 0 ) := 1; M( 0, 1 ) := 2; M( 0, 2 ) := -1; M( 0, 3 ) := -4;
M( 1, 0 ) := 2; M( 1, 1 ) := 3; M( 1, 2 ) := -1; M( 1, 3 ) := -11;
M( 2, 0 ) := -2; M( 2, 1 ) := 0; M( 2, 2 ) := -3; M( 2, 3 ) := 22;
toReducedRowEchelonForm( M, 2, 3 );
r_format := "A"; s_w := 0; r_w := 6; r_d := 1; % set output formating %
for r := 0 until 2 do begin
write( M( r, 0 ) );
for c := 1 until 3 do writeon( " ", M( r, c ) );
end for_r
end
end.</syntaxhighlight>
{{out}}
<pre>
1.0 0.0 0.0 -8.0
0.0 1.0 0.0 1.0
0.0 0.0 1.0 -2.0
</pre>
=={{header|ATS}}==
This program was made by modifying [[Gauss-Jordan_matrix_inversion#ATS]]. (The latter program is equivalent to finding the RREF of a particular matrix.)
<syntaxhighlight lang="ats">
%{^
#include <math.h>
#include <float.h>
%}
#include "share/atspre_staload.hats"
macdef NAN = g0f2f ($extval (float, "NAN"))
macdef Zero = g0i2f 0
macdef One = g0i2f 1
macdef Two = g0i2f 2
(* The following is often done by a single machine instruction. *)
macdef multiply_and_add (x, y, z) = (,(x) * ,(y)) + ,(z)
(*------------------------------------------------------------------*)
(* A "little matrix library" *)
typedef Matrix_Index_Map (m1 : int, n1 : int, m0 : int, n0 : int) =
{i1, j1 : pos | i1 <= m1; j1 <= n1}
(int i1, int j1) -<cloref0>
[i0, j0 : pos | i0 <= m0; j0 <= n0]
@(int i0, int j0)
datatype Real_Matrix (tk : tkind,
m1 : int, n1 : int,
m0 : int, n0 : int) =
| Real_Matrix of (matrixref (g0float tk, m0, n0),
int m1, int n1, int m0, int n0,
Matrix_Index_Map (m1, n1, m0, n0))
typedef Real_Matrix (tk : tkind, m1 : int, n1 : int) =
[m0, n0 : pos] Real_Matrix (tk, m1, n1, m0, n0)
typedef Real_Vector (tk : tkind, m1 : int, n1 : int) =
[m1 == 1 || n1 == 1] Real_Matrix (tk, m1, n1)
typedef Real_Row (tk : tkind, n1 : int) = Real_Vector (tk, 1, n1)
typedef Real_Column (tk : tkind, m1 : int) = Real_Vector (tk, m1, 1)
extern fn {tk : tkind}
Real_Matrix_make_elt :
{m0, n0 : pos}
(int m0, int n0, g0float tk) -< !wrt >
Real_Matrix (tk, m0, n0, m0, n0)
extern fn {tk : tkind}
Real_Matrix_copy :
{m1, n1 : pos}
Real_Matrix (tk, m1, n1) -< !refwrt > Real_Matrix (tk, m1, n1)
extern fn {tk : tkind}
Real_Matrix_copy_to :
{m1, n1 : pos}
(Real_Matrix (tk, m1, n1), (* destination *)
Real_Matrix (tk, m1, n1)) -< !refwrt >
void
extern fn {tk : tkind}
Real_Matrix_fill_with_elt :
{m1, n1 : pos}
(Real_Matrix (tk, m1, n1), g0float tk) -< !refwrt > void
extern fn {}
Real_Matrix_dimension :
{tk : tkind}
{m1, n1 : pos}
Real_Matrix (tk, m1, n1) -<> @(int m1, int n1)
extern fn {tk : tkind}
Real_Matrix_get_at :
{m1, n1 : pos}
{i1, j1 : pos | i1 <= m1; j1 <= n1}
(Real_Matrix (tk, m1, n1), int i1, int j1) -< !ref > g0float tk
extern fn {tk : tkind}
Real_Matrix_set_at :
{m1, n1 : pos}
{i1, j1 : pos | i1 <= m1; j1 <= n1}
(Real_Matrix (tk, m1, n1), int i1, int j1, g0float tk) -< !refwrt >
void
extern fn {}
Real_Matrix_apply_index_map :
{tk : tkind}
{m1, n1 : pos}
{m0, n0 : pos}
(Real_Matrix (tk, m0, n0), int m1, int n1,
Matrix_Index_Map (m1, n1, m0, n0)) -<>
Real_Matrix (tk, m1, n1)
extern fn {}
Real_Matrix_transpose :
(* This is transposed INDEXING. It does NOT copy the data. *)
{tk : tkind}
{m1, n1 : pos}
{m0, n0 : pos}
Real_Matrix (tk, m1, n1, m0, n0) -<>
Real_Matrix (tk, n1, m1, m0, n0)
extern fn {}
Real_Matrix_block :
(* This is block (submatrix) INDEXING. It does NOT copy the data. *)
{tk : tkind}
{p0, p1 : pos | p0 <= p1}
{q0, q1 : pos | q0 <= q1}
{m1, n1 : pos | p1 <= m1; q1 <= n1}
{m0, n0 : pos}
(Real_Matrix (tk, m1, n1, m0, n0),
int p0, int p1, int q0, int q1) -<>
Real_Matrix (tk, p1 - p0 + 1, q1 - q0 + 1, m0, n0)
extern fn {tk : tkind}
Real_Matrix_unit_matrix :
{m : pos}
int m -< !refwrt > Real_Matrix (tk, m, m)
extern fn {tk : tkind}
Real_Matrix_unit_matrix_to :
{m : pos}
Real_Matrix (tk, m, m) -< !refwrt > void
extern fn {tk : tkind}
Real_Matrix_matrix_sum :
{m, n : pos}
(Real_Matrix (tk, m, n), Real_Matrix (tk, m, n)) -< !refwrt >
Real_Matrix (tk, m, n)
extern fn {tk : tkind}
Real_Matrix_matrix_sum_to :
{m, n : pos}
(Real_Matrix (tk, m, n), (* destination*)
Real_Matrix (tk, m, n),
Real_Matrix (tk, m, n)) -< !refwrt >
void
extern fn {tk : tkind}
Real_Matrix_matrix_difference :
{m, n : pos}
(Real_Matrix (tk, m, n), Real_Matrix (tk, m, n)) -< !refwrt >
Real_Matrix (tk, m, n)
extern fn {tk : tkind}
Real_Matrix_matrix_difference_to :
{m, n : pos}
(Real_Matrix (tk, m, n), (* destination*)
Real_Matrix (tk, m, n),
Real_Matrix (tk, m, n)) -< !refwrt >
void
extern fn {tk : tkind}
Real_Matrix_matrix_product :
{m, n, p : pos}
(Real_Matrix (tk, m, n), Real_Matrix (tk, n, p)) -< !refwrt >
Real_Matrix (tk, m, p)
extern fn {tk : tkind}
Real_Matrix_matrix_product_to :
{m, n, p : pos}
(Real_Matrix (tk, m, p), (* destination*)
Real_Matrix (tk, m, n),
Real_Matrix (tk, n, p)) -< !refwrt >
void
extern fn {tk : tkind}
Real_Matrix_scalar_product :
{m, n : pos}
(Real_Matrix (tk, m, n), g0float tk) -< !refwrt >
Real_Matrix (tk, m, n)
extern fn {tk : tkind}
Real_Matrix_scalar_product_2 :
{m, n : pos}
(g0float tk, Real_Matrix (tk, m, n)) -< !refwrt >
Real_Matrix (tk, m, n)
extern fn {tk : tkind}
Real_Matrix_scalar_product_to :
{m, n : pos}
(Real_Matrix (tk, m, n), (* destination*)
Real_Matrix (tk, m, n), g0float tk) -< !refwrt > void
extern fn {tk : tkind} (* Useful for debugging. *)
Real_Matrix_fprint :
{m, n : pos}
(FILEref, Real_Matrix (tk, m, n)) -<1> void
overload copy with Real_Matrix_copy
overload copy_to with Real_Matrix_copy_to
overload fill_with_elt with Real_Matrix_fill_with_elt
overload dimension with Real_Matrix_dimension
overload [] with Real_Matrix_get_at
overload [] with Real_Matrix_set_at
overload apply_index_map with Real_Matrix_apply_index_map
overload transpose with Real_Matrix_transpose
overload block with Real_Matrix_block
overload unit_matrix with Real_Matrix_unit_matrix
overload unit_matrix_to with Real_Matrix_unit_matrix_to
overload matrix_sum with Real_Matrix_matrix_sum
overload matrix_sum_to with Real_Matrix_matrix_sum_to
overload matrix_difference with Real_Matrix_matrix_difference
overload matrix_difference_to with Real_Matrix_matrix_difference_to
overload matrix_product with Real_Matrix_matrix_product
overload matrix_product_to with Real_Matrix_matrix_product_to
overload scalar_product with Real_Matrix_scalar_product
overload scalar_product with Real_Matrix_scalar_product_2
overload scalar_product_to with Real_Matrix_scalar_product_to
overload + with matrix_sum
overload - with matrix_difference
overload * with matrix_product
overload * with scalar_product
(*------------------------------------------------------------------*)
(* Implementation of the "little matrix library" *)
implement {tk}
Real_Matrix_make_elt (m0, n0, elt) =
Real_Matrix (matrixref_make_elt<g0float tk> (i2sz m0, i2sz n0, elt),
m0, n0, m0, n0, lam (i1, j1) => @(i1, j1))
implement {}
Real_Matrix_dimension A =
case+ A of Real_Matrix (_, m1, n1, _, _, _) => @(m1, n1)
implement {tk}
Real_Matrix_get_at (A, i1, j1) =
let
val+ Real_Matrix (storage, _, _, _, n0, index_map) = A
val @(i0, j0) = index_map (i1, j1)
in
matrixref_get_at<g0float tk> (storage, pred i0, n0, pred j0)
end
implement {tk}
Real_Matrix_set_at (A, i1, j1, x) =
let
val+ Real_Matrix (storage, _, _, _, n0, index_map) = A
val @(i0, j0) = index_map (i1, j1)
in
matrixref_set_at<g0float tk> (storage, pred i0, n0, pred j0, x)
end
implement {}
Real_Matrix_apply_index_map (A, m1, n1, index_map) =
(* This is not the most efficient way to acquire new indexing, but
it will work. It requires three closures, instead of the two
needed by our implementations of "transpose" and "block". *)
let
val+ Real_Matrix (storage, m1a, n1a, m0, n0, index_map_1a) = A
in
Real_Matrix (storage, m1, n1, m0, n0,
lam (i1, j1) =>
index_map_1a (i1a, j1a) where
{ val @(i1a, j1a) = index_map (i1, j1) })
end
implement {}
Real_Matrix_transpose A =
let
val+ Real_Matrix (storage, m1, n1, m0, n0, index_map) = A
in
Real_Matrix (storage, n1, m1, m0, n0,
lam (i1, j1) => index_map (j1, i1))
end
implement {}
Real_Matrix_block (A, p0, p1, q0, q1) =
let
val+ Real_Matrix (storage, m1, n1, m0, n0, index_map) = A
in
Real_Matrix (storage, succ (p1 - p0), succ (q1 - q0), m0, n0,
lam (i1, j1) =>
index_map (p0 + pred i1, q0 + pred j1))
end
implement {tk}
Real_Matrix_copy A =
let
val @(m1, n1) = dimension A
val C = Real_Matrix_make_elt<tk> (m1, n1, A[1, 1])
val () = copy_to<tk> (C, A)
in
C
end
implement {tk}
Real_Matrix_copy_to (Dst, Src) =
let
val @(m1, n1) = dimension Src
prval [m1 : int] EQINT () = eqint_make_gint m1
prval [n1 : int] EQINT () = eqint_make_gint n1
var i : intGte 1
in
for* {i : pos | i <= m1 + 1} .<(m1 + 1) - i>.
(i : int i) =>
(i := 1; i <> succ m1; i := succ i)
let
var j : intGte 1
in
for* {j : pos | j <= n1 + 1} .<(n1 + 1) - j>.
(j : int j) =>
(j := 1; j <> succ n1; j := succ j)
Dst[i, j] := Src[i, j]
end
end
implement {tk}
Real_Matrix_fill_with_elt (A, elt) =
let
val @(m1, n1) = dimension A
prval [m1 : int] EQINT () = eqint_make_gint m1
prval [n1 : int] EQINT () = eqint_make_gint n1
var i : intGte 1
in
for* {i : pos | i <= m1 + 1} .<(m1 + 1) - i>.
(i : int i) =>
(i := 1; i <> succ m1; i := succ i)
let
var j : intGte 1
in
for* {j : pos | j <= n1 + 1} .<(n1 + 1) - j>.
(j : int j) =>
(j := 1; j <> succ n1; j := succ j)
A[i, j] := elt
end
end
implement {tk}
Real_Matrix_unit_matrix {m} m =
let
val A = Real_Matrix_make_elt<tk> (m, m, Zero)
var i : intGte 1
in
for* {i : pos | i <= m + 1} .<(m + 1) - i>.
(i : int i) =>
(i := 1; i <> succ m; i := succ i)
A[i, i] := One;
A
end
implement {tk}
Real_Matrix_unit_matrix_to A =
let
val @(m, _) = dimension A
prval [m : int] EQINT () = eqint_make_gint m
var i : intGte 1
in
for* {i : pos | i <= m + 1} .<(m + 1) - i>.
(i : int i) =>
(i := 1; i <> succ m; i := succ i)
let
var j : intGte 1
in
for* {j : pos | j <= m + 1} .<(m + 1) - j>.
(j : int j) =>
(j := 1; j <> succ m; j := succ j)
A[i, j] := (if i = j then One else Zero)
end
end
implement {tk}
Real_Matrix_matrix_sum (A, B) =
let
val @(m, n) = dimension A
val C = Real_Matrix_make_elt<tk> (m, n, NAN)
val () = matrix_sum_to<tk> (C, A, B)
in
C
end
implement {tk}
Real_Matrix_matrix_sum_to (C, A, B) =
let
val @(m, n) = dimension A
prval [m : int] EQINT () = eqint_make_gint m
prval [n : int] EQINT () = eqint_make_gint n
var i : intGte 1
in
for* {i : pos | i <= m + 1} .<(m + 1) - i>.
(i : int i) =>
(i := 1; i <> succ m; i := succ i)
let
var j : intGte 1
in
for* {j : pos | j <= n + 1} .<(n + 1) - j>.
(j : int j) =>
(j := 1; j <> succ n; j := succ j)
C[i, j] := A[i, j] + B[i, j]
end
end
implement {tk}
Real_Matrix_matrix_difference (A, B) =
let
val @(m, n) = dimension A
val C = Real_Matrix_make_elt<tk> (m, n, NAN)
val () = matrix_difference_to<tk> (C, A, B)
in
C
end
implement {tk}
Real_Matrix_matrix_difference_to (C, A, B) =
let
val @(m, n) = dimension A
prval [m : int] EQINT () = eqint_make_gint m
prval [n : int] EQINT () = eqint_make_gint n
var i : intGte 1
in
for* {i : pos | i <= m + 1} .<(m + 1) - i>.
(i : int i) =>
(i := 1; i <> succ m; i := succ i)
let
var j : intGte 1
in
for* {j : pos | j <= n + 1} .<(n + 1) - j>.
(j : int j) =>
(j := 1; j <> succ n; j := succ j)
C[i, j] := A[i, j] - B[i, j]
end
end
implement {tk}
Real_Matrix_matrix_product (A, B) =
let
val @(m, n) = dimension A and @(_, p) = dimension B
val C = Real_Matrix_make_elt<tk> (m, p, NAN)
val () = matrix_product_to<tk> (C, A, B)
in
C
end
implement {tk}
Real_Matrix_matrix_product_to (C, A, B) =
let
val @(m, n) = dimension A and @(_, p) = dimension B
prval [m : int] EQINT () = eqint_make_gint m
prval [n : int] EQINT () = eqint_make_gint n
prval [p : int] EQINT () = eqint_make_gint p
var i : intGte 1
in
for* {i : pos | i <= m + 1} .<(m + 1) - i>.
(i : int i) =>
(i := 1; i <> succ m; i := succ i)
let
var k : intGte 1
in
for* {k : pos | k <= p + 1} .<(p + 1) - k>.
(k : int k) =>
(k := 1; k <> succ p; k := succ k)
let
var j : intGte 1
in
C[i, k] := A[i, 1] * B[1, k];
for* {j : pos | j <= n + 1} .<(n + 1) - j>.
(j : int j) =>
(j := 2; j <> succ n; j := succ j)
C[i, k] :=
multiply_and_add (A[i, j], B[j, k], C[i, k])
end
end
end
implement {tk}
Real_Matrix_scalar_product (A, r) =
let
val @(m, n) = dimension A
val C = Real_Matrix_make_elt<tk> (m, n, NAN)
val () = scalar_product_to<tk> (C, A, r)
in
C
end
implement {tk}
Real_Matrix_scalar_product_2 (r, A) =
Real_Matrix_scalar_product<tk> (A, r)
implement {tk}
Real_Matrix_scalar_product_to (C, A, r) =
let
val @(m, n) = dimension A
prval [m : int] EQINT () = eqint_make_gint m
prval [n : int] EQINT () = eqint_make_gint n
var i : intGte 1
in
for* {i : pos | i <= m + 1} .<(m + 1) - i>.
(i : int i) =>
(i := 1; i <> succ m; i := succ i)
let
var j : intGte 1
in
for* {j : pos | j <= n + 1} .<(n + 1) - j>.
(j : int j) =>
(j := 1; j <> succ n; j := succ j)
C[i, j] := A[i, j] * r
end
end
implement {tk}
Real_Matrix_fprint {m, n} (outf, A) =
let
val @(m, n) = dimension A
var i : intGte 1
in
for* {i : pos | i <= m + 1} .<(m + 1) - i>.
(i : int i) =>
(i := 1; i <> succ m; i := succ i)
let
var j : intGte 1
in
for* {j : pos | j <= n + 1} .<(n + 1) - j>.
(j : int j) =>
(j := 1; j <> succ n; j := succ j)
let
typedef FILEstar = $extype"FILE *"
extern castfn FILEref2star : FILEref -<> FILEstar
val _ = $extfcall (int, "fprintf", FILEref2star outf,
"%16.6g", A[i, j])
in
end;
fprintln! (outf)
end
end
(*------------------------------------------------------------------*)
(* Reduced row echelon form, by Gauss-Jordan elimination *)
extern fn {tk : tkind}
Real_Matrix_reduced_row_echelon_form :
{m, n : pos}
Real_Matrix (tk, m, n) -< !refwrt > Real_Matrix (tk, m, n)
implement {tk}
Real_Matrix_reduced_row_echelon_form {m, n} A =
let
val @(m, n) = dimension A
typedef one_to_m = intBtwe (1, m)
typedef one_to_n = intBtwe (1, n)
(* Partial pivoting, to improve the numerical stability. *)
implement
array_tabulate$fopr<one_to_m> i =
let
val i = g1ofg0 (sz2i (succ i))
val () = assertloc ((1 <= i) * (i <= m))
in
i
end
val rows_permutation =
$effmask_all arrayref_tabulate<one_to_m> (i2sz m)
fn
index_map : Matrix_Index_Map (m, n, m, n) =
lam (i1, j1) => $effmask_ref
(@(i0, j1) where { val i0 = rows_permutation[i1 - 1] })
val A = apply_index_map (copy<tk> A, m, n, index_map)
fn {}
exchange_rows (i1 : one_to_m,
i2 : one_to_m) :<!refwrt> void =
if i1 <> i2 then
let
val k1 = rows_permutation[pred i1]
and k2 = rows_permutation[pred i2]
in
rows_permutation[pred i1] := k2;
rows_permutation[pred i2] := k1
end
fn {}
normalize_pivot_row (i : one_to_m,
j : one_to_n) :<!refwrt> void =
let
prval [j : int] EQINT () = eqint_make_gint j
val pivot_val = A[i, j]
var k : intGte 1
in
A[i, j] := One;
for* {k : int | j + 1 <= k; k <= n + 1} .<(n + 1) - k>.
(k : int k) =>
(k := succ j; k <> succ n; k := succ k)
A[i, k] := A[i, k] / pivot_val
end
fn
subtract_normalized_pivot_row (ipiv : one_to_m,
i : one_to_m,
j : one_to_n) :<!refwrt> void =
let
prval [j : int] EQINT () = eqint_make_gint j
val factor = ~A[i, j]
var k : intGte 1
in
A[i, j] := Zero;
for* {k : int | j + 1 <= k; k <= n + 1} .<(n + 1) - k>.
(k : int k) =>
(k := succ j; k <> succ n; k := succ k)
A[i, k] := multiply_and_add (A[ipiv, k], factor, A[i, k])
end
fun
main_loop {i, j : pos | i <= m; i <= j; j <= n + 1}
.<(n + 1) - j>.
(i : int i, j : int j) :<!refwrt> void =
if j <> succ n then
let
fun
select_pivot {k : int | i <= k; k <= m + 1}
.<(m + 1) - k>.
(k : int k,
max_abs : g0float tk,
k_max_abs : intBtwe (i - 1, m))
:<!ref> intBtwe (i - 1, m) =
if k = succ m then
k_max_abs
else
let
val abs_akj = abs A[k, j]
in
if abs_akj > max_abs then
select_pivot (succ k, abs_akj, k)
else
select_pivot (succ k, max_abs, k_max_abs)
end
val i_pivot = select_pivot (i, Zero, pred i)
prval [i_pivot : int] EQINT () = eqint_make_gint i_pivot
in
if i_pivot = pred i then
(* There is no pivot in this column. *)
main_loop (i, succ j)
else
let
var k : intGte 1
in
exchange_rows (i_pivot, i);
normalize_pivot_row (i, j);
for* {k : int | 1 <= k; k <= i} .<i - k>.
(k : int k) =>
(k := 1; k <> i; k := succ k)
subtract_normalized_pivot_row (i, k, j);
for* {k : int | i + 1 <= k; k <= m + 1} .<(m + 1) - k>.
(k : int k) =>
(k := succ i; k <> succ m; k := succ k)
subtract_normalized_pivot_row (i, k, j);
if i <> m then
main_loop (succ i, succ j)
end
end
in
main_loop (1, 1);
A
end
overload reduced_row_echelon_form with
Real_Matrix_reduced_row_echelon_form
(*------------------------------------------------------------------*)
implement
main0 () =
let
val () = println! ()
val () = println! ("Here is the requested solution:")
val () = println! ()
val A = Real_Matrix_make_elt (3, 4, NAN)
val () =
(A[1,1] := 1.0; A[1,2] := 2.0; A[1,3] := ~1.0; A[1,4] := ~4.0;
A[2,1] := 2.0; A[2,2] := 3.0; A[2,3] := ~1.0; A[2,4] := ~11.0;
A[3,1] := ~2.0; A[3,2] := 0.0; A[3,3] := ~3.0; A[3,4] := 22.0)
val B = reduced_row_echelon_form A
val () = Real_Matrix_fprint (stdout_ref, B)
val () = println! ()
val () = println! ("Here is a RREF with a more interesting shape:")
val () = println! ()
val A = Real_Matrix_make_elt (3, 5, NAN)
val () =
(A[1,1] := 0.0; A[1,2] := 0.0; A[1,3] := ~1.0; A[1,4] := 2.0; A[1,5] := 0.0;
A[2,1] := 0.0; A[2,2] := 0.0; A[2,3] := ~1.0; A[2,4] := 1.0; A[2,5] := 1.0;
A[3,1] := 2.0; A[3,2] := 8.0; A[3,3] := 1.0; A[3,4] := ~4.0; A[3,5] := 2.0)
val B = reduced_row_echelon_form A
val () = Real_Matrix_fprint (stdout_ref, B)
val () = println! ()
val () = println! ("It is the RREF of this matrix:")
val () = println! ()
val () = Real_Matrix_fprint (stdout_ref, A)
val () = println! ()
in
end
(*------------------------------------------------------------------*)
</syntaxhighlight>
{{out}}
<pre>$ patscc -std=gnu2x -g -O2 -DATS_MEMALLOC_GCBDW reduced_row_echelon_task.dats -lgc && ./a.out
Here is the requested solution:
1 0 0 -8
0 1 0 1
0 0 1 -2
Here is a RREF with a more interesting shape:
1 4 0 0 0
0 0 1 0 -2
0 0 0 1 -1
It is the RREF of this matrix:
0 0 -1 2 0
0 0 -1 1 1
2 8 1 -4 2
</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">ToReducedRowEchelonForm(M){
rowCount := M.Count() ; the number of rows in M
columnCount := M.1.Count() ; the number of columns in M
r := lead := 1
while (r <= rowCount) {
if (columnCount < lead)
return M
i := r
while (M[i, lead] = 0) {
i++
if (rowCount+1 = i) {
i := r, lead++
if (columnCount+1 = lead)
return M
}
}
if (i<>r)
for col, v in M[i] ; Swap rows i and r
tempVal := M[i, col], M[i, col] := M[r, col], M[r, col] := tempVal
num := M[r, lead]
if (M[r, lead] <> 0)
for col, val in M[r]
M[r, col] /= num ; If M[r, lead] is not 0 divide row r by M[r, lead]
i := 2
while (i <= rowCount) {
num := M[i, lead]
if (i <> r)
for col, val in M[i] ; Subtract M[i, lead] multiplied by row r from row i
M[i, col] -= num * M[r, col]
i++
}
lead++, r++
}
return M
}</syntaxhighlight>
Examples:<syntaxhighlight lang="autohotkey">M := [[1 , 2, -1, -4 ]
, [2 , 3, -1, -11]
, [-2, 0, -3, 22]]
M := ToReducedRowEchelonForm(M)
for row, obj in M
{
for col, v in obj
output .= RegExReplace(v, "\.0+$|0+$") "`t"
output .= "`n"
}
MsgBox % output
return</syntaxhighlight>
{{out}}
<pre>1 0 0 -8
-0 1 0 1
-0 -0 1 -2
</pre>
=={{header|AutoIt}}==
<syntaxhighlight lang="autoit">
Global $ivMatrix[3][4] = [[1, 2, -1, -4],[2, 3, -1, -11],[-2, 0, -3, 22]]
ToReducedRowEchelonForm($ivMatrix)
Line 585 ⟶ 1,482:
Return $matrix
EndFunc ;==>ToReducedRowEchelonForm
</syntaxhighlight>
{{out}}
<pre>[1,0,0,-8]
Line 591 ⟶ 1,488:
[-0,-0,1,-2]</pre>
=={{header|
==={{header|BASIC256}}===
<syntaxhighlight lang="basic256">arraybase 1
global matrix
dim matrix = {{1, 2, -1, -4}, {2, 3, -1, -11}, { -2, 0, -3, 22}}
call RREF (matrix)
for row = 1 to 3
for col = 1 to 4
if matrix[row, col] = 0 then
print "0"; chr(9);
else
print matrix[row, col]; chr(9);
end if
next
print
next
end
subroutine RREF(m)
nrows = matrix[?,]
ncols = matrix[,?]
lead = 1
for r = 1 to nrows
if lead >= ncols then exit for
i = r
while matrix[i, lead] = 0
i += 1
if i = nrows then
i = r
lead += 1
if lead = ncols then exit for
end if
end while
for j = 1 to ncols
temp = matrix[i, j]
matrix[i, j] = matrix[r, j]
matrix[r, j] = temp
next
n = matrix[r, lead]
if n <> 1 then
for j = 0 to ncols
matrix[r, j] /= n
next
end if
for i = 1 to nrows
if i <> r then
n = matrix[i, lead]
for j = 1 to ncols
matrix[i, j] -= matrix[r, j] * n
next
end if
next
lead += 1
next
end subroutine</syntaxhighlight>
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
<
matrix() = 1, 2, -1, -4, \
\ 2, 3, -1, -11, \
Line 634 ⟶ 1,589:
lead% += 1
NEXT r%
ENDPROC</
{{out}}
<pre>
Line 643 ⟶ 1,598:
=={{header|C}}==
<
#define TALLOC(n,typ) malloc(n*sizeof(typ))
Line 798 ⟶ 1,753:
MtxDisplay(m1);
return 0;
}</
=={{header|C sharp|C#}}==
<
namespace rref
Line 860 ⟶ 1,815:
}
}
}</
=={{header|C++}}==
Line 868 ⟶ 1,823:
{{works with|g++|4.1.2 20061115 (prerelease) (Debian 4.1.1-21)}}
<
#include <cstddef>
#include <cassert>
Line 1,053 ⟶ 2,008:
return EXIT_SUCCESS;
}</
{{out}}
<pre>
Line 1,063 ⟶ 2,018:
=={{header|Common Lisp}}==
Direct implementation of the pseudo-code given.
<
(let* ((dimensions (array-dimensions matrix))
(row-count (first dimensions))
Line 1,106 ⟶ 2,061:
(* scale (aref matrix r c))))))
(incf lead))
:finally (return matrix)))))</
=={{header|D}}==
<
void toReducedRowEchelonForm(T)(T[][] M) pure nothrow @nogc {
Line 1,150 ⟶ 2,105:
A.toReducedRowEchelonForm;
writefln("%(%(%2d %)\n%)", A);
}</
{{out}}
<pre> 1 0 0 -8
0 1 0 1
0 0 1 -2</pre>
=={{header|EasyLang}}==
{{trans|Go}}
<syntaxhighlight>
proc rref . m[][] .
nrow = len m[][]
ncol = len m[1][]
lead = 1
for r to nrow
if lead > ncol
return
.
i = r
while m[i][lead] = 0
i += 1
if i > nrow
i = r
lead += 1
if lead > ncol
return
.
.
.
swap m[i][] m[r][]
m = m[r][lead]
for k to ncol
m[r][k] /= m
.
for i to nrow
if i <> r
m = m[i][lead]
for k to ncol
m[i][k] -= m * m[r][k]
.
.
.
lead += 1
.
.
test[][] = [ [ 1 2 -1 -4 ] [ 2 3 -1 -11 ] [ -2 0 -3 22 ] ]
rref test[][]
print test[][]
</syntaxhighlight>
=={{header|Euphoria}}==
<
integer lead,rowCount,columnCount,i
sequence temp
Line 1,195 ⟶ 2,193:
{ { 1, 2, -1, -4 },
{ 2, 3, -1, -11 },
{ -2, 0, -3, 22 } })</
{{out}}
Line 1,205 ⟶ 2,203:
=={{header|Factor}}==
<
{ { 1 2 -1 -4 } { 2 3 -1 -11 } { -2 0 -3 22 } } solution .</
{{out}}
<pre>
Line 1,213 ⟶ 2,211:
=={{header|Fortran}}==
<
implicit none
contains
Line 1,251 ⟶ 2,249:
deallocate(trow)
end subroutine to_rref
end module Rref</
<
use rref
implicit none
Line 1,275 ⟶ 2,273:
end do
end program prg_test</
=={{header|FreeBASIC}}==
Include the code from [[Matrix multiplication#FreeBASIC]] because this function uses the matrix type defined there and I don't want to reproduce it all here.
<syntaxhighlight lang="freebasic">#include once "matmult.bas"
sub rowswap( byval M as Matrix, i as uinteger, j as uinteger )
dim as integer k
for k = 0 to ubound(M.m, 2)
swap M.m(j, k), M.m(i, k)
next k
end sub
function rowech(byval M as Matrix) as Matrix
dim as uinteger lead = 0, rowCount = 1+ubound(M.m, 1), colCount = 1+ubound(M.m, 2)
dim as uinteger r, i, j
dim as double K
for r = 0 to rowCount-1
if lead >= colCount then exit for
i = r
while M.m(i, lead) = 0
i += 1
if i = rowCount then
i = r
lead += 1
if lead = colCount then exit for
endif
wend
rowswap M, r, i
K = M.m(r,lead)
if K <> 0 then
for j = 0 to colCount-1
M.m(r,j) /= K
next j
endif
for i = 0 to rowCount-1
if i <> r then
K = M.m(i, lead)
for j = 0 to colCount-1
M.m(i,j) -= M.m(r,j) * K
next j
endif
next i
lead += 1
next r
return M
end function
dim as Matrix M = Matrix (3, 4)
dim as Matrix N
M.m(0,0) = 1 : M.m(0,1) = 2 : M.m(0,2) = -1 : M.M(0,3) = -4
M.m(1,0) = 2 : M.m(1,1) = 3 : M.m(1,2) = -1 : M.m(1,3) = -11
M.m(2,0) = -2: M.m(2,1) = 0 : M.m(2,2) = -3 : M.m(2,3) = 22
dim as integer i, j
N = rowech(M)
for i=0 to 2
for j = 0 to 3
print N.m(i, j),
next j
print
next i</syntaxhighlight>
{{out}}
<pre>
1 0 0 -8
-0 1 0 1
-0 -0 1 -2
</pre>
=={{header|Go}}==
===2D representation===
From WP pseudocode:
<
import "fmt"
Line 1,338 ⟶ 2,407:
lead++
}
}</
{{out}} (not so pretty, sorry)
<pre>
Line 1,351 ⟶ 2,420:
===Flat representation===
<
import "fmt"
Line 1,433 ⟶ 2,502:
m.rref()
m.print("Reduced:")
}</
{{out}}
<pre>
Line 1,452 ⟶ 2,521:
Options are provided for both ''partial pivoting'' and ''scaled partial pivoting''.
The default option is no pivoting at all.
<
NONE({ i, it -> 1 }),
PARTIAL({ i, it -> - (it[i].abs()) }),
Line 1,483 ⟶ 2,552:
}
matrix
}</
This test first demonstrates the test case provided, and then demonstrates another test case designed to show the dangers of not using pivoting on an otherwise solvable matrix. Both test cases exercise all three pivoting options.
<
println "Tests for matrix A:"
Line 1,531 ⟶ 2,600:
println "pivoting == Pivoting.SCALED"
reducedRowEchelonForm(matrixCopy(b), Pivoting.SCALED).each { println it }
println()</
{{out}}
Line 1,575 ⟶ 2,644:
This program was produced by translating from the Python and gradually refactoring the result into a more functional style.
<
rref :: Fractional a => [[a]] -> [[a]]
Line 1,606 ⟶ 2,675:
{- Replaces the element at the given index. -}
replace n e l = a ++ e : b
where (a, _ : b) = splitAt n l</
=={{header|Icon}} and {{header|Unicon}}==
Works in both languages:
<
tM := [[ 1, 2, -1, -4],
[ 2, 3, -1,-11],
Line 1,643 ⟶ 2,712:
procedure showMat(M)
every r := !M do every writes(right(!r,5)||" " | "\n")
end</
{{out}}
Line 1,655 ⟶ 2,724:
=={{header|J}}==
The reduced row echelon form of a matrix can be obtained using the <code>gauss_jordan</code> verb from the [
'''
<
NB. form: (row,col) pivot M
pivot=: dyad define
Line 1,693 ⟶ 2,762:
end.
mtx
)</
<hr style="clear: both"/>
'''Usage:'''
<
]A=: 1 2 _1 _4 , 2 3 _1 _11 ,: _2 0 _3 22
1 2 _1 _4
Line 1,705 ⟶ 2,775:
1 0 0 _8
0 1 0 1
0 0 1 _2</
Additional examples, recommended on talk page:
<syntaxhighlight lang="j">
gauss_jordan 2 0 _1 0 0,1 0 0 _1 0,3 0 0 _2 _1,0 1 0 0 _2,:0 1 _1 0 0
1 0 0 0 _1
Line 1,725 ⟶ 2,795:
1 0
0 1
0 0</
And:
<
1 0 0 0 0 0 1 0 0 0 0 _1 0 0 0 0 0 0
1 0 0 0 0 0 0 1 0 0 0 0 _1 0 0 0 0 0
Line 1,765 ⟶ 2,835:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0.512821
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0.820513</
=={{header|Java}}==
''This requires Apache Commons 2.2+''
<
import java.lang.Math;
import org.apache.commons.math.fraction.Fraction;
Line 2,028 ⟶ 3,098:
System.out.println("after\n" + a.toString() + "\n");
}
}</
=={{header|JavaScript}}==
{{works with|SpiderMonkey}} for the <code>print()</code> function.
Extends the Matrix class defined at [[Matrix Transpose#JavaScript]]
<
Matrix.prototype.toReducedRowEchelonForm = function() {
var lead = 0;
Line 2,086 ⟶ 3,156:
[ 3, 3, 0, 7]
]);
print(m.toReducedRowEchelonForm());</
{{out}}
<pre>1,0,0,-8
Line 2,095 ⟶ 3,165:
0,1,0,1.666666666666667
0,0,1,1</pre>
=={{header|jq}}==
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq, and with fq.'''
'''Generic Functions'''
<syntaxhighlight lang=jq>
# swap .[$i] and .[$j]
def array_swap($i; $j):
if $i == $j then .
elif $i < $j then array_swap($j; $i)
else .[$i] as $t | .[:$j] + [$t] + .[$j:$i] + .[$i + 1:]
end ;
# element-wise subtraction: $a - $b
def array_subtract($a; $b):
$a | [range(0;length) as $i | .[$i] - $b[$i]];
def lpad($len):
tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
# Ensure -0 prints as 0
def matrix_print:
([.[][] | tostring | length] | max) as $max
| .[] | map(if . == 0 then 0 else . end | lpad($max))
| join(" ");
</syntaxhighlight>
'''The Task'''
<syntaxhighlight lang=jq>
# RREF
# assume input is a rectangular numeric matrix
def toReducedRowEchelonForm:
length as $nr
| (.[0]|length) as $nc
| { lead: 0, r: -1, a: .}
| until ($nc == .lead or .r == $nr;
.r += 1
| .r as $r
| .i = $r
| until ($nc == .lead or .a[.i][.lead] != 0;
.i += 1
| if $nr == .i
then .i = $r
| .lead += 1
else .
end )
| if $nc > .lead and $nr > $r
then .i as $i
| .a |= array_swap($i; $r)
| .a[$r][.lead] as $div
| if $div != 0
then .a[$r] |= map(. / $div)
else .
end
| reduce range(0; $nr) as $k (.;
if $k != $r
then .a[$k][.lead] as $mult
| .a[$k] = array_subtract(.a[$k]; (.a[$r] | map(. * $mult)))
else .
end )
| .lead += 1
else .
end )
| .a;
[ [ 1, 2, -1, -4],
[ 2, 3, -1, -11],
[-2, 0, -3, 22] ],
[ [1, 2, -1, -4],
[2, 4, -1, -11],
[-2, 0, -6, 24] ]
| "Original:", matrix_print, "",
"RREF:", (toReducedRowEchelonForm|matrix_print), "\n"
</syntaxhighlight>
{{output}}
'''Invocation:''' jq -nrc -f reduced-row-echelon-form.jq
<pre>
Original:
1 2 -1 -4
2 3 -1 -11
-2 0 -3 22
RREF:
1 0 0 -8
0 1 0 1
0 0 1 -2
Original:
1 2 -1 -4
2 4 -1 -11
-2 0 -6 24
RREF:
1 0 0 -3
0 1 0 -2
0 0 1 -3
</pre>
=={{header|Julia}}==
Line 2,114 ⟶ 3,283:
=={{header|Kotlin}}==
<
typealias Matrix = Array<DoubleArray>
Line 2,193 ⟶ 3,362:
m.printf("Reduced row echelon form:")
}
}</
{{out}}
Line 2,223 ⟶ 3,392:
=={{header|Lua}}==
<
local lead = 1
local n_rows, n_cols = #M, #M[1]
Line 2,268 ⟶ 3,437:
end
io.write( "\n" )
end</
{{out}}
<pre>1 0 0 -8
Line 2,276 ⟶ 3,445:
=={{header|M2000 Interpreter}}==
low bound 1 for array
<syntaxhighlight lang="m2000 interpreter">
Module Base1 {
dim base 1, A(3, 4)
Line 2,322 ⟶ 3,491:
}
Base1
</syntaxhighlight>
Low bound 0 for array
<syntaxhighlight lang="m2000 interpreter">
Module base0 {
dim base 0, A(3, 4)
Line 2,372 ⟶ 3,541:
}
base0
</syntaxhighlight>
=={{header|Maple}}==
<syntaxhighlight lang="maple">
with(LinearAlgebra):
ReducedRowEchelonForm(<<1,2,-2>|<2,3,0>|<-1,-1,-3>|<-4,-11,22>>);
</syntaxhighlight>
{{out}}
<pre>
Line 2,390 ⟶ 3,559:
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
{{out}}
<
=={{header|MATLAB}}==
<
=={{header|Maxima}}==
<
k:min(p,q),
for i thru min(p,q) do (if a[i,i]=0 then (k:i-1,return())),
Line 2,412 ⟶ 3,581:
rref(a);
matrix([1,0,0,0,1/2],[0,1,0,0,-1],[0,0,1,0,-1/2],[0,0,0,1,1],[0,0,0,0,0])</
=={{header|Nim}}==
===Using rationals===
To avoid rounding issues, we can use rationals and convert to floats only at the end.
<syntaxhighlight lang="nim">import rationals, strutils
type Fraction = Rational[int]
const Zero: Fraction = 0 // 1
type Matrix[M, N: static Positive] = array[M, array[N, Fraction]]
func toMatrix[M, N: static Positive](a: array[M, array[N, int]]): Matrix[M, N] =
## Convert a matrix of integers to a matrix of integer fractions.
for i in 0..<M:
for j in 0..<N:
result[i][j] = a[i][j] // 1
func transformToRref(mat: var Matrix) =
## Transform the given matrix to reduced row echelon form.
var lead = 0
for r in 0..<mat.M:
if lead >= mat.N: return
var i = r
while mat[i][lead] == Zero:
inc i
if i == mat.M:
i = r
inc lead
if lead == mat.N: return
swap mat[i], mat[r]
if (let d = mat[r][lead]; d) != Zero:
for item in mat[r].mitems:
item /= d
for i in 0..<mat.M:
if i != r:
let m = mat[i][lead]
for c in 0..<mat.N:
mat[i][c] -= mat[r][c] * m
inc lead
proc `$`(mat: Matrix): string =
## Display a matrix.
for row in mat:
var line = ""
for val in row:
line.addSep(" ", 0)
line.add val.toFloat.formatFloat(ffDecimal, 2).align(7)
echo line
#———————————————————————————————————————————————————————————————————————————————————————————————————
template runTest(mat: Matrix) =
## Run a test using matrix "mat".
echo "Original matrix:"
echo mat
echo "Reduced row echelon form:"
mat.transformToRref()
echo mat
echo ""
var m1 = [[ 1, 2, -1, -4],
[ 2, 3, -1, -11],
[-2, 0, -3, 22]].toMatrix()
var m2 = [[2, 0, -1, 0, 0],
[1, 0, 0, -1, 0],
[3, 0, 0, -2, -1],
[0, 1, 0, 0, -2],
[0, 1, -1, 0, 0]].toMatrix()
var m3 = [[1, 2, 3, 4, 3, 1],
[2, 4, 6, 2, 6, 2],
[3, 6, 18, 9, 9, -6],
[4, 8, 12, 10, 12, 4],
[5, 10, 24, 11, 15, -4]].toMatrix()
var m4 = [[0, 1],
[1, 2],
[0, 5]].toMatrix()
runTest(m1)
runTest(m2)
runTest(m3)
runTest(m4)</syntaxhighlight>
{{out}}
<pre>Original matrix:
1.00 2.00 -1.00 -4.00
2.00 3.00 -1.00 -11.00
-2.00 0.00 -3.00 22.00
Reduced row echelon form:
1.00 0.00 0.00 -8.00
0.00 1.00 0.00 1.00
0.00 0.00 1.00 -2.00
Original matrix:
2.00 0.00 -1.00 0.00 0.00
1.00 0.00 0.00 -1.00 0.00
3.00 0.00 0.00 -2.00 -1.00
0.00 1.00 0.00 0.00 -2.00
0.00 1.00 -1.00 0.00 0.00
Reduced row echelon form:
1.00 0.00 0.00 0.00 -1.00
0.00 1.00 0.00 0.00 -2.00
0.00 0.00 1.00 0.00 -2.00
0.00 0.00 0.00 1.00 -1.00
0.00 0.00 0.00 0.00 0.00
Original matrix:
1.00 2.00 3.00 4.00 3.00 1.00
2.00 4.00 6.00 2.00 6.00 2.00
3.00 6.00 18.00 9.00 9.00 -6.00
4.00 8.00 12.00 10.00 12.00 4.00
5.00 10.00 24.00 11.00 15.00 -4.00
Reduced row echelon form:
1.00 2.00 0.00 0.00 3.00 4.00
0.00 0.00 1.00 0.00 0.00 -1.00
0.00 0.00 0.00 1.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00
Original matrix:
0.00 1.00
1.00 2.00
0.00 5.00
Reduced row echelon form:
1.00 0.00
0.00 1.00
0.00 0.00</pre>
===Using floats===
When using floats, we have to be careful when doing comparisons. The previous program adapted to use floats instead of rationals may give wrong results. This would be the case with the second matrix. To get the right result, we have to do a comparison to an epsilon rather than zero. Here is the program modified to work with floats:
<syntaxhighlight lang="nim">import strutils, strformat
const Eps = 1e-10
type Matrix[M, N: static Positive] = array[M, array[N, float]]
func toMatrix[M, N: static Positive](a: array[M, array[N, int]]): Matrix[M, N] =
## Convert a matrix of integers to a matrix of floats.
for i in 0..<M:
for j in 0..<N:
result[i][j] = a[i][j].toFloat
func transformToRref(mat: var Matrix) =
## Transform the given matrix to reduced row echelon form.
var lead = 0
for r in 0..<mat.M:
if lead >= mat.N: return
var i = r
while mat[i][lead] == 0:
inc i
if i == mat.M:
i = r
inc lead
if lead == mat.N: return
swap mat[i], mat[r]
let d = mat[r][lead]
if abs(d) > Eps: # Checking "d != 0" will give wrong results in some cases.
for item in mat[r].mitems:
item /= d
for i in 0..<mat.M:
if i != r:
let m = mat[i][lead]
for c in 0..<mat.N:
mat[i][c] -= mat[r][c] * m
inc lead
proc `$`(mat: Matrix): string =
## Display a matrix.
for row in mat:
var line = ""
for val in row:
line.addSep(" ", 0)
line.add &"{val:7.2f}"
echo line
#———————————————————————————————————————————————————————————————————————————————————————————————————
template runTest(mat: Matrix) =
## Run a test using matrix "mat".
echo "Original matrix:"
echo mat
echo "Reduced row echelon form:"
mat.transformToRref()
echo mat
echo ""
var m1 = [[ 1, 2, -1, -4],
[ 2, 3, -1, -11],
[-2, 0, -3, 22]].toMatrix()
var m2 = [[2, 0, -1, 0, 0],
[1, 0, 0, -1, 0],
[3, 0, 0, -2, -1],
[0, 1, 0, 0, -2],
[0, 1, -1, 0, 0]].toMatrix()
var m3 = [[1, 2, 3, 4, 3, 1],
[2, 4, 6, 2, 6, 2],
[3, 6, 18, 9, 9, -6],
[4, 8, 12, 10, 12, 4],
[5, 10, 24, 11, 15, -4]].toMatrix()
var m4 = [[0, 1],
[1, 2],
[0, 5]].toMatrix()
runTest(m1)
runTest(m2)
runTest(m3)
runTest(m4)</syntaxhighlight>
{{Out}}
Same result as that of the program working with rationals (at least for the matrices used here).
=={{header|Objeck}}==
<
class RowEchelon {
function : Main(args : String[]) ~ Nil {
Line 2,484 ⟶ 3,905:
}
}
</syntaxhighlight>
=={{header|OCaml}}==
<
let tmp = m.(i) in
m.(i) <- m.(j);
Line 2,537 ⟶ 3,958:
) row;
print_newline()
) m</
Another implementation:
<
let nr, nc = Array.length m, Array.length m.(0) in
let add r s k =
Line 2,567 ⟶ 3,988:
print_newline();
rref mat;
show mat</
=={{header|Octave}}==
<
refA = rref(A);
disp(refA);</
=={{header|PARI/GP}}==
PARI has a built-in matrix type, but no commands for row-echelon form. This
<
{
my(s=matsize(M),t=s[1]);
for(i=1,s[2],
if(M[t,i]==0, next);
M[t,] /= M[t,i];
for(j=1,t-1,
M[j,] -= M[j,i]*M[t,]
);
for(j=t+1,s[1],
M[j,] -= M[j,i]*M[t,]
);
if(t--<1,break)
);
M;
}
addhelp(matrref, "matrref(M): Returns the reduced row-echelon form of the matrix M.");</syntaxhighlight>
A faster, dimension-limited one can be constructed from the built-in <code>matsolve</code> command:
<syntaxhighlight lang="parigp">rref(M)={
my(d=matsize(M));
if(d[1]+1 != d[2], error("Bad size in rref"), d=d[1]);
concat(matid(d), matsolve(matrix(d,d,x,y,M[x,y]), M[,d+1]))
};</
Example:
<
{{out}}
<pre>%1 =
Line 2,594 ⟶ 4,034:
{{trans|Python}}
Note that the function defined here takes an array reference, which is modified in place.
<
{our @m; local *m = shift;
@m or return;
Line 2,630 ⟶ 4,070:
rref(\@m);
print display(\@m);</
{{out}}
<pre> 1 0 0 -8
Line 2,638 ⟶ 4,078:
=={{header|Phix}}==
{{Trans|Euphoria}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">ToReducedRowEchelonForm</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">M</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lead</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">rowCount</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">M</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">columnCount</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">M</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]),</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">rowCount</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">lead</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">columnCount</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">M</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">lead</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">rowCount</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #000000;">lead</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">lead</span><span style="color: #0000FF;">=</span><span style="color: #000000;">columnCount</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">mr</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_div</span><span style="color: #0000FF;">(</span><span style="color: #000000;">M</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">M</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">lead</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">M</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">M</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">M</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mr</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">rowCount</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">r</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">M</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">M</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">M</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">lead</span><span style="color: #0000FF;">],</span><span style="color: #000000;">M</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">]))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">lead</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">M</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">?</span> <span style="color: #000000;">ToReducedRowEchelonForm</span><span style="color: #0000FF;">(</span>
<span style="color: #0000FF;">{</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">4</span> <span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">11</span> <span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">22</span> <span style="color: #0000FF;">}</span> <span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,678 ⟶ 4,122:
{{works with|PHP|5.x}}
{{trans|Java}}
<
function rref($matrix)
Line 2,724 ⟶ 4,168:
return $matrix;
}
?></
=={{header|PicoLisp}}==
<
(let (Lead 1 Cols (length (car Mat)))
(for (X Mat X (cdr X))
Line 2,749 ⟶ 4,193:
(car X) ) ) ) )
(T (> (inc 'Lead) Cols)) ) )
Mat )</
{{out}}
<pre>(reducedRowEchelonForm
Line 2,757 ⟶ 4,201:
=={{header|Python}}==
<
if not M: return
lead = 0
Line 2,791 ⟶ 4,235:
for rw in mtx:
print ', '.join( (str(rv) for rv in rw) )</
=={{header|R}}==
{{trans|Fortran}}
<
pivot <- 1
norow <- nrow(m)
Line 2,827 ⟶ 4,271:
-2, 0, -3, 22), 3, 4, byrow=TRUE)
print(m)
print(rref(m))</
=={{header|Racket}}==
<
#lang racket
(require math)
Line 2,840 ⟶ 4,284:
[2 3 -1 -11]
[-2 0 -3 22]]))
</syntaxhighlight>
{{out}}
<pre>
Line 2,851 ⟶ 4,295:
=={{header|Raku}}==
(formerly Perl 6)
=== Following pseudocode ===
{{trans|Perl}}
<syntaxhighlight lang="raku" line>sub rref (@m) {
my ($lead, $rows, $cols) = 0, @m, @m[0];
for ^$rows -> $r {
return @m unless $lead < $cols
my $i = $r;
until @m[$i;$lead] {
next unless ++$i == $rows
$i = $r;
return @m if ++$lead == $cols
}
@m[$i, $r] = @m[$r, $i] if $r != $i;
for ^$rows -> $n {
next if $n == $r;
@m[$n] »-=» @m[$r] »
}
++$lead;
Line 2,879 ⟶ 4,322:
sub rat-or-int ($num) {
return $num unless $num ~~ Rat;
return $num.narrow if $num.narrow
$num.nude.join: '/';
}
Line 2,931 ⟶ 4,374:
say_it( 'Reduced Row Echelon Form Matrix', rref(@matrix) );
say "\n";
}</
Raku handles rational numbers internally as a ratio of two integers
Line 2,939 ⟶ 4,382:
{{out}}
<pre style="height:70ex">
Original Matrix
1 2 -1 -4
Line 2,949 ⟶ 4,392:
0 1 0 1
0 0 1 -2
Original Matrix
Line 2,961 ⟶ 4,402:
0 1 0 -217/6
0 0 1 -125/6
Original Matrix
Line 2,977 ⟶ 4,416:
0 0 0 0 0 0
0 0 0 0 0 0
Original Matrix
Line 3,019 ⟶ 4,456:
</pre>
=== Row operations, procedural code ===
Re-implemented as elementary matrix row operations. Follow links for background on
[http://unapologetic.wordpress.com/2009/08/27/elementary-row-and-column-operations/ row operations]
and
[http://unapologetic.wordpress.com/2009/09/03/reduced-row-echelon-form/ reduced row echelon form]
<syntaxhighlight lang="raku" line>sub scale-row ( @M, \scale, \r ) { @M[r] = @M[r] »×» scale }
sub
sub
my @M = (
Line 3,041 ⟶ 4,473:
);
my $
my $col = 0;
for @M.keys -> $row {
reduce-row( @M, $row, $col );
clear-column( @M, $row, $col );
}
say @$_».fmt(' %4g') for @M;</syntaxhighlight>
{{out}}
<pre>[ 1 0 0 -8]
[ 0 1 0 1]
[ 0 0 1 -2]</pre>
=== Row operations, object-oriented code ===
The same code as previous section, recast into OO. Also, scale and shear are recast as unscale and unshear, which fit the problem better.
<syntaxhighlight lang="raku" line>class Matrix is Array {
method unscale-row ( @M: \scale, \row ) { @M[row] = @M[row] »/» scale }
method unshear-row ( @M: \scale, \r1, \r2 ) { @M[r1] = @M[r1] »-» @M[r2] »×» scale }
method reduce-row ( @M: \row, \col ) { @M.unscale-row( @M[row;col], row ) }
method clear-column ( @M: \row, \col ) { @M.unshear-row( @M[$_;col], $_, row ) for @M.keys.grep: * != row }
method reduced-row-echelon-form ( @M: ) {
my $column-count = @M[0];
for @M
@M.reduce-row( $row, $col );
}
}
Line 3,099 ⟶ 4,512:
);
$M.reduced-row-echelon-form;
say @$_».fmt(' %4g') for @$M;</syntaxhighlight>
{{out}}
<pre>[ 1 0 0 -8]
[ 0 1 0 1]
[ 0 0 1 -2]</pre>
=={{header|REXX}}==
''Reduced Row Echelon Form'' (a.k.a. ''row canonical form'') of a matrix, with optimization added.
<
cols= 0;
mat.=; mat.1= ' 1 2 -1 -4 '
mat.2= ' 2 3 -1 -11 '
mat.3= ' -2 0 -3 22 '
do r=1 until mat.r==''; _=mat.r /*build @.row.col from (matrix) mat.X*/
do c=1 until _='';
w= max(w, length(@.r.c) + 1)
end /*c*/
cols= max(cols, c)
end /*r*/
rows= r
call showMat 'original matrix' /*display the original
!=
/* ┌──────────────────────◄────────────────◄──── Reduced Row Echelon Form on matrix.*/
do r=1 for rows while cols>! /*begin to perform the heavy lifting. */
j=
do while @.j.!==0; j= j + 1
if j==rows then do; j= r;
end /*while*/
/* [↓] swap rows J,R (but not if same)*/
do _=1 for cols while j\==r; parse value @.r._ @.j._ with @.j._ @._._
end /*_*/
?= @.r.!
do d=1 for cols while ?\=1; @.r.d= @.r.d / ?
end /*d*/ /* [↑] divide row J by @.r.p ──unless≡1*/
Line 3,143 ⟶ 4,552:
end /*s*/
end /*k*/ /* [↑] for the rest of numbers in row.*/
!= !
end /*r*/
Line 3,149 ⟶ 4,558:
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
showMat: parse arg title; say;
say _
{{out|output|text= when using the default (internal) input:}}
<pre>
Line 3,175 ⟶ 4,584:
=={{header|Ring}}==
<
# Project : Reduced row echelon form
Line 3,233 ⟶ 4,642:
lead = lead + 1
next
</syntaxhighlight>
Output:
<pre>
Line 3,239 ⟶ 4,648:
0 1 0 1
0 0 1 -2
</pre>
=={{header|RPL}}==
The <code>RREF</code> built-in intruction is available for HP-48G and newer models.
[[1 2 -1 -4] [2 3 -1 -11] [-2 0 -3 22]] RREF
{{out}}
<pre>
1: [[ 1 0 0 -8 ]
[ 0 1 0 1 ]
[ 0 0 1 -2 ]]
</pre>
=={{header|Ruby}}==
{{works with|Ruby|1.9.3}}
<
def reduced_row_echelon_form(ary)
lead = 0
Line 3,313 ⟶ 4,732:
reduced = reduced_row_echelon_form(mtx)
print_matrix reduced
print_matrix convert_to(reduced, :to_f)</
{{out}}
Line 3,327 ⟶ 4,746:
0.0 1.0 0.0 1.6666666666666667
0.0 0.0 1.0 1.0
</pre>
=={{header|Rust}}==
{{trans|FORTRAN}}
I have tried to avoid state mutation with respect to the input matrix and adopt as functional a style as possible in this translation, so for larger matrices one may want to consider memory usage implications.
<syntaxhighlight lang="rust">
fn main() {
let mut matrix_to_reduce: Vec<Vec<f64>> = vec![vec![1.0, 2.0 , -1.0, -4.0],
vec![2.0, 3.0, -1.0, -11.0],
vec![-2.0, 0.0, -3.0, 22.0]];
let mut r_mat_to_red = &mut matrix_to_reduce;
let rr_mat_to_red = &mut r_mat_to_red;
println!("Matrix to reduce:\n{:?}", rr_mat_to_red);
let reduced_matrix = reduced_row_echelon_form(rr_mat_to_red);
println!("Reduced matrix:\n{:?}", reduced_matrix);
}
fn reduced_row_echelon_form(matrix: &mut Vec<Vec<f64>>) -> Vec<Vec<f64>> {
let mut matrix_out: Vec<Vec<f64>> = matrix.to_vec();
let mut pivot = 0;
let row_count = matrix_out.len();
let column_count = matrix_out[0].len();
'outer: for r in 0..row_count {
if column_count <= pivot {
break;
}
let mut i = r;
while matrix_out[i][pivot] == 0.0 {
i = i+1;
if i == row_count {
i = r;
pivot = pivot + 1;
if column_count == pivot {
pivot = pivot - 1;
break 'outer;
}
}
}
for j in 0..row_count {
let temp = matrix_out[r][j];
matrix_out[r][j] = matrix_out[i][j];
matrix_out[i][j] = temp;
}
let divisor = matrix_out[r][pivot];
if divisor != 0.0 {
for j in 0..column_count {
matrix_out[r][j] = matrix_out[r][j] / divisor;
}
}
for j in 0..row_count {
if j != r {
let hold = matrix_out[j][pivot];
for k in 0..column_count {
matrix_out[j][k] = matrix_out[j][k] - ( hold * matrix_out[r][k]);
}
}
}
pivot = pivot + 1;
}
matrix_out
}
</syntaxhighlight>
Output:
<pre>
Matrix to reduce:
[[1.0, 2.0, -1.0, -4.0], [2.0, 3.0, -1.0, -11.0], [-2.0, 0.0, -3.0, 22.0]]
Reduced matrix:
[[1.0, 0.0, 0.0, -8.0], [-0.0, 1.0, 0.0, 1.0], [-0.0, -0.0, 1.0, -2.0]]
</pre>
=={{header|Sage}}==
{{works with|Sage|4.6.2}}
<
sage: m.rref()
[ 1 0 0 -8]
[ 0 1 0 1]
[ 0 0 1 -2] </
=={{header|Scheme}}==
{{Works with|Scheme|R<math>^5</math>RS}}
<
(define (clean-down matrix from-row column)
(cons (car matrix)
Line 3,386 ⟶ 4,875:
indices)
indices)
indices)))</
Example:
<
(list (list 1 2 -1 -4) (list 2 3 -1 -11) (list -2 0 -3 22)))
(display (reduced-row-echelon-form matrix))
(newline)</
{{out}}
<syntaxhighlight lang="text">((1 0 0 -8) (0 1 0 1) (0 0 1 -2))</
=={{header|Seed7}}==
<
const proc: toReducedRowEchelonForm (inout matrix: mat) is func
Line 3,450 ⟶ 4,939:
end for;
end for;
end func;</
Original source: [http://seed7.sourceforge.net/algorith/math.htm#toReducedRowEchelonForm]
=={{header|Sidef}}==
{{trans|
<
var (j, rows, cols) = (0, M.len, M[0].len)
Line 3,513 ⟶ 5,002:
say_it('Reduced Row Echelon Form Matrix', rref(matrix));
say '';
}</
{{out}}
<pre>
Line 3,554 ⟶ 5,043:
=={{header|Swift}}==
<syntaxhighlight lang="swift">
var lead = 0
for r in 0..<rows {
Line 3,591 ⟶ 5,080:
lead += 1
}
</syntaxhighlight>
=={{header|Tcl}}==
Using utility procs defined at [[Matrix Transpose#Tcl]]
<
namespace path {::tcl::mathop ::tcl::mathfunc}
Line 3,643 ⟶ 5,132:
set m {{1 2 -1 -4} {2 3 -1 -11} {-2 0 -3 22}}
print_matrix $m
print_matrix [toRREF $m]</
{{out}}
<pre> 1 2 -1 -4
Line 3,654 ⟶ 5,143:
=={{header|TI-83 BASIC}}==
Builtin function: rref()
<
{{out}}
<pre>
Line 3,663 ⟶ 5,152:
=={{header|TI-89 BASIC}}==
<
Output (in prettyprint mode): <math>\begin{bmatrix} 1&0&0&-8 \\ 0&1&0&1 \\ 0&0&1&-2 \end{bmatrix}</math>
Line 3,684 ⟶ 5,173:
These are all combined in the main rref function.
<
#import flo
Line 3,700 ⟶ 5,189:
<1.,2.,-1.,-4.>,
<2.,3.,-1.,-11.>,
<-2.,0.,-3.,22.>></
{{out}}
<pre>
Line 3,711 ⟶ 5,200:
This solution is applicable only if the input
is a non-singular augmented square matrix.
<
rref = @ySzSX msolve; ^plrNCTS\~& ~&iiDlSzyCK9+ :/1.+ 0.!*t</
=={{header|VBA}}==
{{trans|Phix}}<
Dim lead As Integer: lead = 0
Dim rowCount As Integer: rowCount = UBound(M)
Line 3,767 ⟶ 5,256:
Debug.Print Join(r(i), vbTab)
Next i
End Sub</
<pre>1 0 0 -8
0 1 0 1
Line 3,774 ⟶ 5,263:
=={{header|Visual FoxPro}}==
Translation of Fortran.
<
CLOSE DATABASES ALL
LOCAL lnRows As Integer, lnCols As Integer, lcSafety As String
Line 3,865 ⟶ 5,354:
ACOPY(m1, m2, e1, n, e2)
ENDPROC
</syntaxhighlight>
{{out}}
<pre>
Line 3,873 ⟶ 5,362:
0.000000 0.000000 1.000000 -2.000000
</pre>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-matrix}}
The above module has a method for this built in as it's needed to implement matrix inversion using the Gauss-Jordan method. However, as in the example here, it's not just restricted to square matrices.
<syntaxhighlight lang="wren">import "./matrix" for Matrix
import "./fmt" for Fmt
var m = Matrix.new([
[ 1, 2, -1, -4],
[ 2, 3, -1, -11],
[-2, 0, -3, 22]
])
System.print("Original:\n")
Fmt.mprint(m, 3, 0)
System.print("\nRREF:\n")
m.toReducedRowEchelonForm
Fmt.mprint(m, 3, 0)</syntaxhighlight>
{{out}}
<pre>
Original:
| 1 2 -1 -4|
| 2 3 -1 -11|
| -2 0 -3 22|
RREF:
| 1 0 0 -8|
| 0 1 0 1|
| 0 0 1 -2|
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">proc ReducedRowEchelonForm(M, Rows, Cols);
\Replace M with its reduced row echelon form
real M; int Rows, Cols;
int Lead, R, C, I;
real RLead, ILead, T;
[Lead:= 0;
for R:= 0 to Rows-1 do
[if Lead >= Cols then return;
I:= R;
while M(I, Lead) = 0. do
[I:= I+1;
if I = Rows-1 then
[I:= R;
Lead:= Lead+1;
if Lead = Cols-1 then return;
];
];
\Swap rows I and R
T:= M(I); M(I):= M(R); M(R):= T;
if M(R, Lead) # 0. then
\Divide row R by M[R, Lead]
[RLead:= M(R, Lead);
for C:= 0 to Cols-1 do
M(R, C):= M(R, C) / RLead;
];
for I:= 0 to Rows-1 do
[if I # R then
\Subtract M[I, Lead] multiplied by row R from row I
[ILead:= M(I, Lead);
for C:= 0 to Cols-1 do
M(I, C):= M(I, C) - ILead * M(R, C);
];
];
Lead:= Lead+1;
];
];
real M;
int R, C;
[M:= [ [ 1., 2., -1., -4.],
[ 2., 3., -1.,-11.],
[-2., 0., -3., 22.] ];
ReducedRowEchelonForm(M, 3, 4);
Format(4,1);
for R:= 0 to 3-1 do
[for C:= 0 to 4-1 do
RlOut(0, M(R,C));
CrLf(0);
];
]</syntaxhighlight>
{{out}}
<pre>
1.0 0.0 0.0 -8.0
0.0 1.0 0.0 1.0
0.0 0.0 1.0 -2.0
</pre>
=={{header|Yabasic}}==
<syntaxhighlight lang="yabasic">// Rosetta Code problem: https://rosettacode.org/wiki/Reduced_row_echelon_form
// by Jjuanhdez, 06/2022
dim matrix (3, 4)
matrix(1, 1) = 1 : matrix(1, 2) = 2 : matrix(1, 3) = -1 : matrix(1, 4) = -4
matrix(2, 1) = 2 : matrix(2, 2) = 3 : matrix(2, 3) = -1 : matrix(2, 4) = -11
matrix(3, 1) = -2 : matrix(3, 2) = 0 : matrix(3, 3) = -3 : matrix(3, 4) = 22
RREF (matrix())
for row = 1 to 3
for col = 1 to 4
if matrix(row, col) = 0 then
print "0", chr$(9);
else
print matrix(row, col), chr$(9);
end if
next
print
next
end
sub RREF(x())
local nrows, ncols, lead, r, i, j, n
nrows = arraysize(matrix(), 1) //3
ncols = arraysize(matrix(), 2) //4
lead = 1
for r = 1 to nrows
if lead >= ncols break
i = r
while matrix(i, lead) = 0
i = i + 1
if i = nrows then
i = r
lead = lead + 1
if lead = ncols break 2
end if
wend
for j = 1 to ncols
temp = matrix(i, j)
matrix(i, j) = matrix(r, j)
matrix(r, j) = temp
next
n = matrix(r, lead)
if n <> 0 then
for j = 1 to ncols
matrix(r, j) = matrix(r, j) / n
next
end if
for i = 1 to nrows
if i <> r then
n = matrix(i, lead)
for j = 1 to ncols
matrix(i, j) = matrix(i, j) - matrix(r, j) * n
next
end if
next
lead = lead + 1
next
end sub</syntaxhighlight>
=={{header|zkl}}==
The "best" way is to use the GNU Scientific Library:
<
fcn toReducedRowEchelonForm(M){ // in place
lead,rows,columns := 0,M.rows,M.cols;
Line 3,895 ⟶ 5,540:
}
M
}</
<
2, 3, -1, -11,
-2, 0, -3, 22);
toReducedRowEchelonForm(A).format(5,1).println();</
{{out}}
<pre>
Line 3,908 ⟶ 5,553:
Or, using lists of lists and direct implementation of the pseudo-code given,
lots of generating new rows rather than modifying the rows themselves.
<
lead,rowCount,columnCount := 0,m.len(),m[1].len();
foreach r in (rowCount){
Line 3,929 ⟶ 5,574:
}//foreach
m
}</
<
T( 2, 3, -1, -11,),
T(-2, 0, -3, 22,));
Line 3,938 ⟶ 5,583:
fcn printM(m){ m.pump(Console.println,rowFmt) }
fcn rowFmt(row){ ("%4d "*row.len()).fmt(row.xplode()) }</
{{out}}
<pre>
|