PLE and PLUQ decomposition

Functions
rci_t	mzed_ple_newton_john (mzed_t *A, mzp_t *P, mzp_t *Q)
	PLE decomposition: \(L \cdot E = P\cdot A\) using Newton-John tables.
rci_t	mzed_ple_naive (mzed_t *A, mzp_t *P, mzp_t *Q)
	PLE decomposition: \( L \cdot E = P \cdot A \). More...
rci_t	_mzd_slice_ple (mzd_slice_t *A, mzp_t *P, mzp_t *Q, rci_t cutoff)
	PLE decomposition: \( L \cdot E = P \cdot A \). More...
static rci_t	mzd_slice_ple (mzd_slice_t *A, mzp_t *P, mzp_t *Q)
	PLE decomposition: \( L \cdot E = P \cdot A \). More...
rci_t	_mzd_slice_pluq (mzd_slice_t *A, mzp_t *P, mzp_t *Q, rci_t cutoff)
	PLUQ decomposition: \( L \cdot U \cdot Q = P \cdot A\). More...
static rci_t	mzd_slice_pluq (mzd_slice_t *A, mzp_t *P, mzp_t *Q)
	PLUQ decomposition: \( L \cdot U \cdot Q = P \cdot A\). More...
rci_t	_mzed_ple (mzed_t *A, mzp_t *P, mzp_t *Q, rci_t cutoff)
	PLE decomposition: \( L \cdot E = P \cdot A \). More...
static rci_t	mzed_ple (mzed_t *A, mzp_t *P, mzp_t *Q)
	PLE decomposition: \( L \cdot E = P \cdot A \). More...

Detailed Description

Function Documentation

rci_t _mzd_slice_ple	(	mzd_slice_t *	A,
		mzp_t *	P,
		mzp_t *	Q,
		rci_t	cutoff
	)

PLE decomposition: \( L \cdot E = P \cdot A \).

Modifies A in place to store lower triangular L below (and on) the main diagonal and E – an echelon form of A – above the main diagonal (pivots are stored in Q). P and Q are updated with row and column permutations respectively.

This function uses either asymptotically fast PLE decomposition by reducing it to matrix multiplication or naive cubic PLE decomposition depending on the size of the underlying field. If asymptotically fast PLE decomposition is used, then the algorithm switches to mzed_ple_newton_john if e * ncols * nrows is <= cutoff where e is the exponent of the finite field.

Parameters

A	Matrix
P	Permutation vector of length A->nrows
Q	Permutation vector of length A->ncols
cutoff	Integer

See also

mzed_ple_naive() mzed_ple_newton_john() mzed_ple()

rci_t _mzd_slice_pluq	(	mzd_slice_t *	A,
		mzp_t *	P,
		mzp_t *	Q,
		rci_t	cutoff
	)

PLUQ decomposition: \( L \cdot U \cdot Q = P \cdot A\).

This function implements asymptotically fast PLE decomposition by reducing it to matrix multiplication. From PLE the PLUQ decomposition is then obtained.

Parameters

A	Matrix
P	Permutation vector of length A->nrows
Q	Permutation vector of length A->ncols
cutoff	Crossover to base case if mzed_t::w * mzed_t::ncols * mzed_t::nrows < cutoff.

rci_t _mzed_ple	(	mzed_t *	A,
		mzp_t *	P,
		mzp_t *	Q,
		rci_t	cutoff
	)

PLE decomposition: \( L \cdot E = P \cdot A \).

Modifies A in place to store lower triangular L below (and on) the main diagonal and E – an echelon form of A – above the main diagonal (pivots are stored in Q). P and Q are updated with row and column permutations respectively.

This function uses either asymptotically fast PLE decomposition by reducing it to matrix multiplication or naive cubic PLE decomposition depending on the size of the underlying field. If asymptotically fast PLE decomposition is used, then the algorithm switches to mzed_ple_newton_john if e * ncols * nrows is <= cutoff where e is the exponent of the finite field.

Parameters

A	Matrix
P	Permutation vector of length A->nrows
Q	Permutation vector of length A->ncols
cutoff	Integer >= 0

See also

mzed_ple_naive() mzed_ple_newton_john() _mzed_ple()

static rci_t mzd_slice_ple ( mzd_slice_t *  A, mzp_t *  P, mzp_t *  Q  )

inlinestatic

PLE decomposition: \( L \cdot E = P \cdot A \).

Modifies A in place to store lower triangular L below (and on) the main diagonal and E – an echelon form of A – above the main diagonal (pivots are stored in Q). P and Q are updated with row and column permutations respectively.

This function implements asymptotically fast PLE decomposition by reducing it to matrix multiplication.

Parameters

A	Matrix
P	Permutation vector of length A->nrows
Q	Permutation vector of length A->ncols

See also

mzed_ple_naive() mzed_ple_newton_john() _mzd_slice_ple()

static rci_t mzd_slice_pluq ( mzd_slice_t *  A, mzp_t *  P, mzp_t *  Q  )

inlinestatic

PLUQ decomposition: \( L \cdot U \cdot Q = P \cdot A\).

This function implements asymptotically fast PLE decomposition by reducing it to matrix multiplication. From PLE the PLUQ decomposition is then obtained.

Parameters

A	Matrix
P	Permutation vector of length A->nrows
Q	Permutation vector of length A->ncols

static rci_t mzed_ple ( mzed_t *  A, mzp_t *  P, mzp_t *  Q  )

inlinestatic

PLE decomposition: \( L \cdot E = P \cdot A \).

Modifies A in place to store lower triangular L below (and on) the main diagonal and E – an echelon form of A – above the main diagonal (pivots are stored in Q). P and Q are updated with row and column permutations respectively.

This function uses either asymptotically fast PLE decomposition by reducing it to matrix multiplication or naive cubic PLE decomposition depending on the size of the underlying field.

Parameters

A	Matrix
P	Permutation vector of length A->nrows
Q	Permutation vector of length A->ncols

See also

mzed_ple_naive() mzed_ple_newton_john() _mzed_ple()

rci_t mzed_ple_naive	(	mzed_t *	A,
		mzp_t *	P,
		mzp_t *	Q
	)

PLE decomposition: \( L \cdot E = P \cdot A \).

Modifies A in place to store lower triangular L below (and on) the main diagonal and E – an echelon form of A – above the main diagonal (pivots are stored in Q). P and Q are updated with row and column permutations respectively.

This function uses naive cubic PLE decomposition depending on the size of the underlying field.

Parameters

A	Matrix
P	Permutation vector of length A->nrows
Q	Permutation vector of length A->ncols

See also

mzed_ple_newton_john() mzed_ple()