Talk:Reduced row echelon form: Difference between revisions

== Bug in Common Lisp code ==

There is a bug in find-pivot that causes an infinite loop on some input. Here is a corrected version along with the matrix that results in an infinite loop with the current code. I tested the code with SBCL 1.0.40.0.debian on Ubuntu 10.10 64bit.

<lang lisp>(defun convert-to-row-echelon-form (matrix)

(defun convert-to-row-echelon-form (matrix)

(let* ((dimensions (array-dimensions matrix))

(row-count (first dimensions))

(column-count (second dimensions))

(lead 0))

(labels ((find-pivot (start lead)

(let ((i start))

(loop

:while (zerop (aref matrix i lead))

:do (progn

(incf i)

(when (= i row-count)

(setf i start)

(incf lead)

(when (= lead column-count)

(return-from convert-to-row-echelon-form matrix))))

:finally (return (values i lead)))))

(swap-rows (r1 r2)

(loop

:for c :upfrom 0 :below column-count

:do (rotatef (aref matrix r1 c) (aref matrix r2 c))))

(divide-row (r value)

(loop

:for c :upfrom 0 :below column-count

:do (setf (aref matrix r c)

(/ (aref matrix r c) value)))))

(loop

:for r :upfrom 0 :below row-count

:when (<= column-count lead)

:do (return matrix)

:do (multiple-value-bind (i nlead) (find-pivot r lead)

(setf lead nlead)

(swap-rows i r)

(divide-row r (aref matrix r lead))

(loop

:for i :upfrom 0 :below row-count

:when (/= i r)

:do (let ((scale (aref matrix i lead)))

(loop

:for c :upfrom 0 :below column-count

:do (decf (aref matrix i c)

(* scale (aref matrix r c))))))

(incf lead))

:finally (return matrix)))))

(defvar *M* '(( 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)

( 1 0 0 0 0 0 0 0 1 0 0 0 0 -1 0 0 0 0)

( 0 1 0 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0)

( 0 1 0 0 0 0 0 0 1 0 0 -1 0 0 0 0 0 0)

( 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 -1 0)

( 0 0 1 0 0 0 1 0 0 0 0 0 -1 0 0 0 0 0)

( 0 0 1 0 0 0 0 0 0 1 0 0 0 0 -1 0 0 0)

( 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 -1 0 0)

( 0 0 0 1 0 0 0 0 0 1 0 0 -1 0 0 0 0 0)

( 0 0 0 0 1 0 0 1 0 0 0 0 0 -1 0 0 0 0)

( 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 -1 0)

( 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 -1 0 0)

( 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0)

( 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0)

( 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1)

( 0 0 0 0 0 1 0 0 0 0 1 0 0 0 -1 0 0 0)))

(defvar *M-array* (make-array (list (length *M*) (length (first *M*))) :initial-contents *M*))

(print (convert-to-row-echelon-form *M-array*))

</lang>

[[User:carlohamalainen|Carlo Hamalainen]] 3:30PM, 6 Dec 2010 (GMT+10)