M4RIE 0.20111004
Loading...
Searching...
No Matches
newton_john.h
Go to the documentation of this file.
1
11#ifndef M4RIE_NEWTON_JOHN_H
12#define M4RIE_NEWTON_JOHN_H
13
14/******************************************************************************
15*
16* M4RIE: Linear Algebra over GF(2^e)
17*
18* Copyright (C) 2010,2011 Martin Albrecht <martinralbrecht@googlemail.com>
19*
20* Distributed under the terms of the GNU General Public License (GEL)
21* version 2 or higher.
22*
23* This code is distributed in the hope that it will be useful,
24* but WITHOUT ANY WARRANTY; without even the implied warranty of
25* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
26* General Public License for more details.
27*
28* The full text of the GPL is available at:
29*
30* http://www.gnu.org/licenses/
31******************************************************************************/
32
33#include <m4rie/gf2e.h>
34#include <m4rie/mzed.h>
35#include <m4rie/mzd_slice.h>
36
41typedef struct {
42 rci_t *L;
46
54njt_mzed_t *njt_mzed_init(const gf2e *ff, const rci_t ncols);
55
63
73njt_mzed_t * mzed_make_table(njt_mzed_t *T, const mzed_t *A, const rci_t r, const rci_t c);
74
87mzed_t *mzed_mul_newton_john(mzed_t *C, const mzed_t *A, const mzed_t *B);
88
101mzed_t *mzed_addmul_newton_john(mzed_t *C, const mzed_t *A, const mzed_t *B);
102
118mzed_t *_mzed_mul_newton_john0(mzed_t *C, const mzed_t *A, const mzed_t *B);
119
134mzed_t *_mzed_mul_newton_john(mzed_t *C, const mzed_t *A, const mzed_t *B);
135
147rci_t mzed_echelonize_newton_john(mzed_t *A, int full);
148
158
169
180
191
202
209rci_t mzed_ple_newton_john(mzed_t *A, mzp_t *P, mzp_t *Q);
210
227static inline void mzed_process_rows(mzed_t *M, const rci_t startrow, const rci_t endrow, rci_t startcol, const njt_mzed_t *T) {
228 mzd_process_rows(M->x, startrow, endrow, startcol*M->w, M->w, T->T->x, T->L);
229}
230
245static inline void mzed_process_rows2(mzed_t *M, const rci_t startrow, const rci_t endrow, const rci_t startcol,
246 const njt_mzed_t *T0, const njt_mzed_t *T1) {
247 mzd_process_rows2(M->x, startrow, endrow, startcol*M->w, 2*M->w, T0->T->x, T0->L, T1->T->x, T1->L);
248}
249
265static inline void mzed_process_rows3(mzed_t *M, const rci_t startrow, const rci_t endrow, const rci_t startcol,
266 const njt_mzed_t *T0, const njt_mzed_t *T1, const njt_mzed_t *T2) {
267 mzd_process_rows3(M->x, startrow, endrow, startcol*M->w, 3*M->w, T0->T->x, T0->L, T1->T->x, T1->L, T2->T->x, T2->L);
268}
269
286static inline void mzed_process_rows4(mzed_t *M, const rci_t startrow, const rci_t endrow, const rci_t startcol,
287 const njt_mzed_t *T0, const njt_mzed_t *T1, const njt_mzed_t *T2, const njt_mzed_t *T3) {
288 mzd_process_rows4(M->x, startrow, endrow, startcol*M->w, 4*M->w, T0->T->x, T0->L, T1->T->x, T1->L, T2->T->x, T2->L, T3->T->x, T3->L);
289}
290
308static inline void mzed_process_rows5(mzed_t *M, const rci_t startrow, const rci_t endrow, const rci_t startcol,
309 const njt_mzed_t *T0, const njt_mzed_t *T1, const njt_mzed_t *T2, const njt_mzed_t *T3, const njt_mzed_t *T4) {
310 mzd_process_rows5(M->x, startrow, endrow, startcol*M->w, 5*M->w, T0->T->x, T0->L, T1->T->x, T1->L, T2->T->x, T2->L, T3->T->x, T3->L, T4->T->x, T4->L);
311}
312
313
332static inline void mzed_process_rows6(mzed_t *M, const rci_t startrow, const rci_t endrow, const rci_t startcol,
333 const njt_mzed_t *T0, const njt_mzed_t *T1, const njt_mzed_t *T2,
334 const njt_mzed_t *T3, const njt_mzed_t *T4, const njt_mzed_t *T5) {
335 mzd_process_rows6(M->x, startrow, endrow, startcol*M->w, 6*M->w, T0->T->x, T0->L, T1->T->x, T1->L, T2->T->x, T2->L, T3->T->x, T3->L, T4->T->x, T4->L, T5->T->x, T5->L);
336}
337
338
339#endif //M4RIE_NEWTON_JOHN_H
rci_t mzed_echelonize_newton_john(mzed_t *A, int full)
Reduce matrix A to row echelon form using Gauss-Newton-John elimination.
Definition newton_john.c:235
mzed_t * _mzed_mul_newton_john(mzed_t *C, const mzed_t *A, const mzed_t *B)
using Newton-John tables.
Definition newton_john.c:412
mzed_t * mzed_mul_newton_john(mzed_t *C, const mzed_t *A, const mzed_t *B)
using Newton-John tables.
Definition newton_john.c:498
mzed_t * mzed_addmul_newton_john(mzed_t *C, const mzed_t *A, const mzed_t *B)
using Newton-John tables.
Definition newton_john.c:503
mzed_t * _mzed_mul_newton_john0(mzed_t *C, const mzed_t *A, const mzed_t *B)
using Newton-John tables.
Definition newton_john.c:399
rci_t mzed_ple_newton_john(mzed_t *A, mzp_t *P, mzp_t *Q)
PLE decomposition: using Newton-John tables.
Definition newton_john.c:349
static void mzed_process_rows(mzed_t *M, const rci_t startrow, const rci_t endrow, rci_t startcol, const njt_mzed_t *T)
The function looks up 6 entries from position i,startcol in each row and adds the appropriate row fro...
Definition newton_john.h:227
static void mzed_process_rows5(mzed_t *M, const rci_t startrow, const rci_t endrow, const rci_t startcol, const njt_mzed_t *T0, const njt_mzed_t *T1, const njt_mzed_t *T2, const njt_mzed_t *T3, const njt_mzed_t *T4)
Same as mzed_process_rows but works with five Newton-John tables in parallel.
Definition newton_john.h:308
static void mzed_process_rows6(mzed_t *M, const rci_t startrow, const rci_t endrow, const rci_t startcol, const njt_mzed_t *T0, const njt_mzed_t *T1, const njt_mzed_t *T2, const njt_mzed_t *T3, const njt_mzed_t *T4, const njt_mzed_t *T5)
Same as mzed_process_rows but works with six Newton-John tables in parallel.
Definition newton_john.h:332
static void mzed_process_rows3(mzed_t *M, const rci_t startrow, const rci_t endrow, const rci_t startcol, const njt_mzed_t *T0, const njt_mzed_t *T1, const njt_mzed_t *T2)
Same as mzed_process_rows but works with three Newton-John tables in parallel.
Definition newton_john.h:265
static void mzed_process_rows2(mzed_t *M, const rci_t startrow, const rci_t endrow, const rci_t startcol, const njt_mzed_t *T0, const njt_mzed_t *T1)
Same as mzed_process_rows but works with two Newton-John tables in parallel.
Definition newton_john.h:245
static void mzed_process_rows4(mzed_t *M, const rci_t startrow, const rci_t endrow, const rci_t startcol, const njt_mzed_t *T0, const njt_mzed_t *T1, const njt_mzed_t *T2, const njt_mzed_t *T3)
Same as mzed_process_rows but works with four Newton-John tables in parallel.
Definition newton_john.h:286
void mzed_trsm_upper_left_newton_john(const mzed_t *U, mzed_t *B)
using Newton-John tables.
Definition newton_john.c:545
void mzed_trsm_lower_left_newton_john(const mzed_t *L, mzed_t *B)
using Newton-John tables.
Definition newton_john.c:523
void mzd_slice_trsm_upper_left_newton_john(const mzd_slice_t *U, mzd_slice_t *B)
using Newton-John tables.
Definition newton_john.c:592
void mzd_slice_trsm_lower_left_newton_john(const mzd_slice_t *L, mzd_slice_t *B)
using Newton-John tables.
Definition newton_john.c:567
Matrices using a bitsliced representation.
Dense matrices over represented as packed matrices.
mzed_t * mzed_invert_newton_john(mzed_t *B, const mzed_t *A)
Invert the matrix A using Gauss-Newton-John elimination.
Definition newton_john.c:508
njt_mzed_t * mzed_make_table(njt_mzed_t *T, const mzed_t *A, const rci_t r, const rci_t c)
Construct Newton-John table T for row r of A, and element A[r,c].
Definition newton_john.c:156
void njt_mzed_free(njt_mzed_t *t)
Free Newton-John table.
Definition newton_john.c:40
njt_mzed_t * njt_mzed_init(const gf2e *ff, const rci_t ncols)
Allocate Newton-John table of dimension gf2e::degree<<1 * ncols.
Definition newton_john.c:32
Definition gf2e.h:62
Dense matrices over represented as slices of matrices over .
Definition mzd_slice.h:56
Dense matrices over represented as packed matrices.
Definition mzed.h:59
wi_t w
Definition mzed.h:64
mzd_t * x
Definition mzed.h:60
Newton-John table.
Definition newton_john.h:41
mzed_t * T
Definition newton_john.h:44
mzed_t * M
Definition newton_john.h:43
rci_t * L
Definition newton_john.h:42