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:

A	Matrix.
P	Preallocated row permutation.
Q	Preallocated column permutation.
k	Size 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:

A	Matrix.
start_row	Row Offset.
stop_row	Up to which row the matrix should be processed (exclusive).
start_col	Column Offset.
k	Size of Gray code tables.
P	Preallocated row permutation.
Q	Preallocated column permutation.
pivots	which column holds the i-th pivot
done	Preallocated temporary buffer.
done_row	Stores the last row which is already reduced processed after function execution.
splitblock	First block which is not considered by this function.

Return values:

knar	rank 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:

A	Matrix.
P	Preallocated row permutation.
Q	Preallocated column permutation.
k	Size of Gray code tables.

Ignores offset atrtribute of packedmatrix.

Returns:

Rank of A.

Examples:

testsuite/bench_elimination.c.