Mercurial > hg > octave-avbm
changeset 9695:9fba7e1da785
correct algorithm for perm matrix det (sign)
author | Jaroslav Hajek <highegg@gmail.com> |
---|---|
date | Mon, 05 Oct 2009 17:03:13 +0200 |
parents | 50db3c5175b5 |
children | 01a1fd9167e0 |
files | liboctave/ChangeLog liboctave/PermMatrix.cc |
diffstat | 2 files changed, 26 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- a/liboctave/ChangeLog +++ b/liboctave/ChangeLog @@ -1,3 +1,8 @@ +2009-10-05 Jaroslav Hajek <highegg@gmail.com> + + * PermMatrix.cc (PermMatrix::determinant): Implement a (hopefully) + working algorithm. + 2009-10-05 Jaroslav Hajek <highegg@gmail.com> * dim-vector.h (operator ==): Include fast case.
--- a/liboctave/PermMatrix.cc +++ b/liboctave/PermMatrix.cc @@ -28,6 +28,7 @@ #include "idx-vector.h" #include "error.h" #include "Array-util.h" +#include "oct-locbuf.h" static void gripe_invalid_permutation (void) @@ -100,16 +101,30 @@ octave_idx_type PermMatrix::determinant (void) const { - Array<octave_idx_type> pa = *this; - octave_idx_type len = pa.length (), *p = pa.fortran_vec (); - bool neg = false; + // Determine the sign of a permutation in linear time. + // Is this widely known? + + octave_idx_type len = perm_length (); + const octave_idx_type *pa = data (); + + OCTAVE_LOCAL_BUFFER (octave_idx_type, p, len); + OCTAVE_LOCAL_BUFFER (octave_idx_type, q, len); + for (octave_idx_type i = 0; i < len; i++) { - octave_idx_type j = p[i]; + p[i] = pa[i]; + q[p[i]] = i; + } + + bool neg = false; + + for (octave_idx_type i = 0; i < len; i++) + { + octave_idx_type j = p[i], k = q[i]; if (j != i) { - p[i] = p[j]; - p[j] = j; + p[k] = p[i]; + q[j] = q[i]; neg = ! neg; } }