M4RI
1.0.1
|
PLS and PLUQ factorization using Gray codes. More...
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). |
PLS and PLUQ factorization using Gray codes.
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.
A | Matrix. |
P | Preallocated row permutation. |
Q | Preallocated column permutation. |
k | Size of Gray code tables. |
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.
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. |
knar | rank of the considered submatrix |
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.
A | Matrix. |
P | Preallocated row permutation. |
Q | Preallocated column permutation. |
k | Size of Gray code tables. |