What is the LELA F4 matrix format?

[Bjarke Roune]

What is the format for F4 matrices that the LELA
FaugereLachartre code expects?



Echelonize has a special option for F4 matrices. The tutorial states:

METHOD_FAUGERE_LACHARTRE,
  method based on the algorithm of Faugère and Lachartre. Only
  available for matrices of the form coming from the F4
  algorithm.

The code for echelonize is in lela/solutions/echelon-form.h
When using the FaugereLachartre option, it calls code from
the file lela/algorithms/faugere-lachartre.h and .tcc
In the .tcc file there is code for parsing the matrix and
that code will throw a WrongMatrixFormat if it does not
like the matrix. This code is complex and it would help
me to read it if I knew the expected format. I haven't
found a description of the F4 matrix format in the online
LELA tutorial or in comments in these files. I'm already
familiar with F4 and the FaugereLachartre algorithm.

[Bradford Hovinen]

Hello Bjarke,

The requirement is the rows of the matrix be sorted in order of
increasing (column)-position of the leading nonzero entry. So the
following would be allowed:

1 1 0
0 0 1

but the following would not:

1 1 0
0 0 1
0 1 0

In the latter case the rows must be resorted.

Best regards,

-Bradford Hovinen

2012/9/11 Bjarke Roune <bjarke...@gmail.com>:

[Bjarke Roune]

Hi Bardford,

The comment for FaugereLachartre::echelonize states:

  @param only_D Whether to return only the rows of the lower block (default false)

I'm trying to reconcile this with your response, let me see if I understand correctly.I think you are saying that if my ABCD decomposition as

  A/B
  //////
  C/D

is

  10/51
  02/61
  ////////
  34/70

where / is just a matrix separator (| looked too much like 1).

Then I should encode these 4 matrices into the matrix

  1051
  3470
  0261

and LELA will then split this apart into the same matrices A,B,C,D I started with?

The lower block in this case will then be 3470 (as its initial value), even though in the input matrix it is the middle row?

Thanks
Bjarke Hammersholt Roune

[Bradford Hovinen]

Hello Bjarke,

Not quite. The decomposition into A, B, C, and D occurs within the
library. The precondition is that that the matrix have the
aforementioned form. However, the decomposed matrix, so presented,
need not have that form any longer (and in nearly all cases will not).
The decomposition guarantees that A is upper triangular with a nonzero
diagonal while B, C, and D are arbitrary. The algorithm then replaces
D with its Schur complement and computes the row-echelon form of D. If
the flag only_D is set, then only the row-echelon form of D is
returned. This suffices for many applications and reduces the overhead
considerably, hence the option.

Best regards,

-Bradford

2012/9/11 Bjarke Roune <bjarke...@gmail.com>:

[Bjarke Roune]

Hi Bradford,

> The decomposition guarantees that A is upper triangular with a nonzero
> diagonal while B, C, and D are arbitrary.
>

The columns in the B/D part of the matrix must have the same ordering among them as they originally did in order for row reduction of D to match polynomial reduction, so I am guessing that LELA does impose this constraint? That would answer another question I had, which is how to tell how LELA rearranged the columns, since I think the Splicer object has this information and it is not returned from echelonize - only the columns in D matter, and those would then have the same order among them as originally.

> The algorithm then replaces
> D with its Schur complement and computes the row-echelon form of D.
> If the flag only_D is set, then only the row-echelon form of D is
> returned. This suffices for many applications and reduces the overhead
> considerably, hence the option.
>

I hadn't heard of Schur complement before, so I read up on it - it was interesting, so thanks for putting me on the trail of that. If I'm understanding things correctly, in order to match what Faugere-Lachartre does, you'd want to output D-C*inv(A)*B, which according to PlanetMath is the Schur complement of A. Is that right?

  http://planetmath.org/SchurComplement.html

Cheers
Bjarke

[Bradford Hovinen]

Hello Bjarke,

Yes, LELA does keep track of the correct column-ordering. Before the
output is returned, the columns are returned to their original order.

We return the row-echelon form of D-C*A^-1*B (with columns
appropriately permuted).

-Bradford

2012/9/11 Bjarke Roune <bjarke...@gmail.com>: