M4RIE  0.20120415
 All Data Structures Files Functions Variables Defines
Functions
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 \).
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 \).
static rci_t mzd_slice_ple (mzd_slice_t *A, mzp_t *P, mzp_t *Q)
 PLE decomposition: \( L \cdot E = P \cdot A \).
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\).
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\).
rci_t _mzed_ple (mzed_t *A, mzp_t *P, mzp_t *Q, rci_t cutoff)
 PLE decomposition: \( L \cdot E = P \cdot A \).
static rci_t mzed_ple (mzed_t *A, mzp_t *P, mzp_t *Q)
 PLE decomposition: \( L \cdot E = P \cdot A \).

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:
AMatrix
PPermutation vector of length A->nrows
QPermutation vector of length A->ncols
cutoffInteger
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:
AMatrix
PPermutation vector of length A->nrows
QPermutation vector of length A->ncols
cutoffCrossover 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:
AMatrix
PPermutation vector of length A->nrows
QPermutation vector of length A->ncols
cutoffInteger >= 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 
) [inline, static]

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:
AMatrix
PPermutation vector of length A->nrows
QPermutation 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 
) [inline, static]

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:
AMatrix
PPermutation vector of length A->nrows
QPermutation vector of length A->ncols
static rci_t mzed_ple ( mzed_t A,
mzp_t *  P,
mzp_t *  Q 
) [inline, static]

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:
AMatrix
PPermutation vector of length A->nrows
QPermutation 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:
AMatrix
PPermutation vector of length A->nrows
QPermutation vector of length A->ncols
See also:
mzed_ple_newton_john() mzed_ple()