Echelonizing only a (contiguous) part of a matrix

[Vladimir Dzyuba]

Dear all,

Is it possible to echelonize just a part of the matrix?

(If I have to be more specific, the lower or upper right corner.)

I tried creating and echelonizing a window, 

something along the lines of (pseudocode alert):

```

m = mzd_init(n_rows, n_columns);

mzd_randomize(m);

w = mzd_init_window(m, rl, cl, n_rows, n_columns);

mzd_echelonize(w, 1);

mzd_free_window(w);

println(m);

```

But that only seems to work when `rl = cl = 0`.

(I might have bugs though.)

***

To avoid the XY problem, what I’m trying to do is

to implement a constraint propagator for

a system of parity constraints as a part of a larger problem.

Variables can get assigned by other constraints as well,

so 1s concentrate in a continuously shrinking part of the matrix.

Currently, I’m just copying the relevant part of the matrix

to a freshly created smaller matrix and echelonize the latter.

It actually works pretty well performance-wise, but

I was wondering whether there was a more straightforward way.

***

Thank you in advance!

(And thanks for the great library!)

--

Best,

Vladimir

[Martin R. Albrecht]

Hi there,

this kind of thing should work, at least for lower level functions. Did
you try mzd_echelonize_pluq() or mzd_echelonize_m4ri() directly?

At least _mzd_ple() should do the trick, as we’re calling it recursively
on windows internally.

Happy to dig deeper if this doesn’t solve your problem.

Note that cl must be a multiple of 64 in any case.

Cheers,
Martin

--

_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_jab: martinr...@jabber.ccc.de
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF

[Martin R. Albrecht]

PS: https://bitbucket.org/malb/m4ri/issues/62/mzd_echlonize-on-matrix-windows

[Vladimir Dzyuba]

Indeed, I missed the "multiple of 64" requirement, my apologies (same for the late reply).

In my application it doesn't matter much though, because leftmost columns get zeroed out first, so it doesn't affect echelonization.
Nevertheless, for posterity, it is impossible to echelonize an arbitrary part of an arbitrary GF2 matrix, correct?

Thanks for the help!

[Martin R. Albrecht]

Hi there,

yep, to do that you’d have to copy the submatrix out and back in as you reported.

Cheers,
Martin

Vladimir Dzyuba writes:

> Indeed, I missed the "multiple of 64" requirement, my apologies (same for
> the late reply).
>
> In my application it doesn't matter much though, because leftmost columns
> get zeroed out first, so it doesn't affect echelonization.

> Nevertheless, for posterity, it is impossible to echelonize an *arbitrary*
> part of an *arbitrary* GF2 matrix, correct?

>> _jab: martinr...@jabber.ccc.de <javascript:>

[Vladimir Dzyuba]

Another question: there are certain matrices that produce segmentation faults when I try to partially echelonize them in a particular way.

I've got one example (see the attached code and its output), but it's not too rare actually, so I can harvest more, if necessary.

I compiled it with GCC 4.8 (gcc-4.8 -std=gnu99 -I. test.c m4ri/*.o -o test) on Mac OS X 10.9.5.

I'm not good at debugging C programs at all, but I saw mzd_process_rows mentioned in some error message (I primarily use M4RI from Java via JNI/SWIG).

Is it a known issue? Is the matrix maybe too large (16x229)?

[Martin R. Albrecht]

Hi there,

this is now tracked at

https://bitbucket.org/malb/m4ri/issues/63/matrix-windows-with-column-128-64

I added an explanation & workaround there.

Cheers,
Martin

PS: The matrix is tiny, we tend to count in multiples of thousands for
rows and columns when we talk about sizes :)

Vladimir Dzyuba writes:
> Another question: there are certain matrices that produce segmentation

> faults when I try to *partially* echelonize them in a particular way.