M4RI  1.0.1
Functions
pls_mmpf.h File Reference

PLS and PLUQ factorization using Gray codes. More...

#include "packedmatrix.h"
#include "permutation.h"

Go to the source code of this file.

Functions

rci_t _mzd_pls_mmpf (mzd_t *A, mzp_t *P, mzp_t *Q, int k)
 PLS matrix decomposition of A using Gray codes.
rci_t _mzd_pluq_mmpf (mzd_t *A, mzp_t *P, mzp_t *Q, int k)
 PLUQ matrix decomposition of A using Gray codes.
int _mzd_pls_submatrix (mzd_t *A, rci_t const start_row, rci_t const stop_row, rci_t const start_col, int const k, mzp_t *P, mzp_t *Q, rci_t *pivots, rci_t *done, rci_t *done_row, wi_t const splitblock)
 PLE matrix decomposition of a submatrix for up to k columns starting at (r,c).

Detailed Description

PLS and PLUQ factorization using Gray codes.

Author:
Martin Albrecht <M.R.Albrecht@rhul.ac.uk>

Function Documentation

rci_t _mzd_pls_mmpf ( mzd_t A,
mzp_t P,
mzp_t Q,
int  k 
)

PLS matrix decomposition of A using Gray codes.

Returns (P,L,S,Q) satisfying PLS = A where P is a permutation matrix of dimension m x m, L is m x r unit lower triangular and S is an r x n matrix which is upper triangular except that its columns are permuted, that is S = UQ for U r x n upper triangular and Q is a n x n permutation matrix. The matrix L and S are stored in place over A.

Parameters:
AMatrix.
PPreallocated row permutation.
QPreallocated column permutation.
kSize of Gray code tables.
Ignores offset atrtribute of packedmatrix.
Returns:
Rank of A.

compute good k

initialise permutations as identity

The algorithm proceeds as follows

1. compute PLE factorisation for the knar x knar submatrix A00

       m4ri_radix * splitblock
--------------------------------------
| A00  |  A10                        |
|      |                             |
-------------------------------------- knar
| A01  |  A11                        |
|      |                             | 
-------------------------------------- done_row
| A02  |  A12                        |
|      |                             |
|      |                             |
|      |                             |
|      |                             |
|      |                             |
--------------------------------------

2. update A10

3. extract U from A0 = (A00 | A10)

4. generate multiplication and inversion tables T amd E from U

5. update A1 = (A01 | A11)

6. update A2 = (A02 | A12)

int _mzd_pls_submatrix ( mzd_t A,
rci_t const  start_row,
rci_t const  stop_row,
rci_t const  start_col,
int const  k,
mzp_t P,
mzp_t Q,
rci_t pivots,
rci_t done,
rci_t done_row,
wi_t const  splitblock 
)

PLE matrix decomposition of a submatrix for up to k columns starting at (r,c).

Updates P and Q and modifies A in place. The buffer done afterwards holds how far a particular row was already eliminated.

Parameters:
AMatrix.
start_rowRow Offset.
stop_rowUp to which row the matrix should be processed (exclusive).
start_colColumn Offset.
kSize of Gray code tables.
PPreallocated row permutation.
QPreallocated column permutation.
pivotswhich column holds the i-th pivot
donePreallocated temporary buffer.
done_rowStores the last row which is already reduced processed after function execution.
splitblockFirst block which is not considered by this function.
Return values:
knarrank of the considered submatrix
rci_t _mzd_pluq_mmpf ( mzd_t A,
mzp_t P,
mzp_t Q,
int  k 
)

PLUQ matrix decomposition of A using Gray codes.

Returns (P,L,U,Q) satisfying PLUQ = A where P and Q are two permutation matrices, of dimension respectively m x m and n x n, L is m x r unit lower triangular and U is r x n upper triangular.

Parameters:
AMatrix.
PPreallocated row permutation.
QPreallocated column permutation.
kSize of Gray code tables.
Ignores offset atrtribute of packedmatrix.
Returns:
Rank of A.
Examples:
testsuite/bench_elimination.c.