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

#include <m4ri/mzd.h>
#include <m4ri/mzp.h>

Data Structures
struct	ple_table_t
	PLE Elimination Tables. More...

Functions
ple_table_t *	ple_table_init (int k, rci_t ncols)

void	ple_table_free (ple_table_t *T)
	Delete table T. More...

rci_t	_mzd_ple_russian (mzd_t A, mzp_t P, mzp_t *Q, int k)
	PLE matrix decomposition of A using Gray codes. More...

rci_t	_mzd_pluq_russian (mzd_t A, mzp_t P, mzp_t *Q, int k)
	PLUQ matrix decomposition of A using Gray codes. More...

int	_mzd_ple_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). More...

mzd_t *	_mzd_ple_to_e (mzd_t E, mzd_t const A, rci_t r, rci_t c, int k, rci_t *offsets)
	Extract the k x A::ncols echelon form submatrix of A starting at row r and column c. More...

void	_mzd_process_rows_ple_2 (mzd_t M, rci_t startrow, rci_t stoprow, rci_t startcol, int const k, const ple_table_t **T)
	add rows T[0],T[1] to M between startrow and stoprow, starting at startcol. More...

void	_mzd_process_rows_ple_3 (mzd_t M, rci_t startrow, rci_t stoprow, rci_t startcol, int const k, const ple_table_t **T)
	add rows T[0],T[1],T[2] to M between startrow and stoprow, starting at startcol. More...

void	_mzd_process_rows_ple_4 (mzd_t M, rci_t startrow, rci_t stoprow, rci_t startcol, int const k, const ple_table_t **T)
	add rows T[0],T[1],T[2],T[3] to M between startrow and stoprow, starting at startcol. More...

void	_mzd_process_rows_ple_5 (mzd_t M, rci_t startrow, rci_t stoprow, rci_t startcol, int const k, const ple_table_t **T)
	add rows T[0],T[1],T[2],T[3],T[4] to M between startrow and stoprow, starting at startcol. More...

void	_mzd_process_rows_ple_6 (mzd_t M, rci_t startrow, rci_t stoprow, rci_t startcol, int const k, const ple_table_t **T)
	add rows T[0],T[1],T[2],T[3],T[4],T[5] to M between startrow and stoprow, starting at startcol. More...

Detailed Description

PLE and PLUQ factorization using Gray codes.

Author: Martin Albrecht marti.nosp@m.nral.nosp@m.brech.nosp@m.t@go.nosp@m.oglem.nosp@m.ail..nosp@m.com

Function Documentation

rci_t _mzd_ple_russian	(	mzd_t *	A,
		mzp_t *	P,
		mzp_t *	Q,
		int	k
	)

PLE matrix decomposition of A using Gray codes.

Returns (P,L,E,Q) satisfying PLE = 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 E = UQ for U r x n upper triangular and Q is a n x n permutation matrix. The matrix L and E are stored in place over A.

Parameters

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

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                        |
|      |                             |
|      |                             |
|      |                             |
|      |                             |
|      |                             |
--------------------------------------

update A10
extract U from A0 = (A00 | A10)
generate multiplication and inversion tables T amd E from U
update A1 = (A01 | A11)
update A2 = (A02 | A12)

Examples:: testsuite/test_ple.c.

int _mzd_ple_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

mzd_t* _mzd_ple_to_e	(	mzd_t *	E,
		mzd_t const *	A,
		rci_t	r,
		rci_t	c,
		int	k,
		rci_t *	offsets
	)

Extract the k x A::ncols echelon form submatrix of A starting at row r and column c.

Parameters

E	Storage for k x A::ncols matrix.
A	Source matrix.
r	Row index.
c	Column index.
k	Rank of E.
k	Map from i to column of i-th pivot.
offsets	Encodes which columns contain pivots

rci_t _mzd_pluq_russian	(	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.

Returns: Rank of A.

Examples:: testsuite/bench_elimination.c.

void _mzd_process_rows_ple_2	(	mzd_t *	M,
		rci_t	startrow,
		rci_t	stoprow,
		rci_t	startcol,
		int const *	k,
		const ple_table_t **	T
	)

add rows T[0],T[1] to M between startrow and stoprow, starting at startcol.

Parameters

M	Matrix
startrow	Start processing in this row
stoprow	Stop processing in this row
startcol	Start processing in this column
k	Number of bits to read in each table
T	PLE Table with 2^k[i] rows

void _mzd_process_rows_ple_3	(	mzd_t *	M,
		rci_t	startrow,
		rci_t	stoprow,
		rci_t	startcol,
		int const *	k,
		const ple_table_t **	T
	)

add rows T[0],T[1],T[2] to M between startrow and stoprow, starting at startcol.

Parameters

M	Matrix
startrow	Start processing in this row
stoprow	Stop processing in this row
startcol	Start processing in this column
k	Number of bits to read in each table
T	PLE Table with 2^k[i] rows

void _mzd_process_rows_ple_4	(	mzd_t *	M,
		rci_t	startrow,
		rci_t	stoprow,
		rci_t	startcol,
		int const *	k,
		const ple_table_t **	T
	)

add rows T[0],T[1],T[2],T[3] to M between startrow and stoprow, starting at startcol.

Parameters

M	Matrix
startrow	Start processing in this row
stoprow	Stop processing in this row
startcol	Start processing in this column
k	Number of bits to read in each table
T	PLE Table with 2^k[i] rows

void _mzd_process_rows_ple_5	(	mzd_t *	M,
		rci_t	startrow,
		rci_t	stoprow,
		rci_t	startcol,
		int const *	k,
		const ple_table_t **	T
	)

add rows T[0],T[1],T[2],T[3],T[4] to M between startrow and stoprow, starting at startcol.

Parameters

M	Matrix
startrow	Start processing in this row
stoprow	Stop processing in this row
startcol	Start processing in this column
k	Number of bits to read in each table
T	PLE Table with 2^k[i] rows

void _mzd_process_rows_ple_6	(	mzd_t *	M,
		rci_t	startrow,
		rci_t	stoprow,
		rci_t	startcol,
		int const *	k,
		const ple_table_t **	T
	)

add rows T[0],T[1],T[2],T[3],T[4],T[5] to M between startrow and stoprow, starting at startcol.

Parameters

M	Matrix
startrow	Start processing in this row
stoprow	Stop processing in this row
startcol	Start processing in this column
k	Number of bits to read in each table
T	PLE Table with 2^k[i] rows

void ple_table_free ( ple_table_t * T )

Delete table T.

Parameters

T	PLE table.

ple_table_t* ple_table_init	(	int	k,
		rci_t	ncols
	)

Create new table with 2^k rows and ncols.

Parameters

k	log2 of the number of rows (0 < k <= 8).
ncols	Number of columns.

Data Structures

Functions

Detailed Description

Function Documentation