newton_john.h File Reference

Newton-John table based algorithms. More...

#include <m4rie/gf2e.h>
#include <m4rie/mzed.h>
#include <m4rie/mzd_slice.h>

Go to the source code of this file.

Data Structures
struct	njt_mzed_t
	Newton-John table. More...

Functions
njt_mzed_t *	njt_mzed_init (const gf2e *ff, const rci_t ncols)
	Allocate Newton-John table of dimension gf2e::degree<<1 * ncols. More...
void	njt_mzed_free (njt_mzed_t *t)
	Free Newton-John table. More...
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]. More...
mzed_t *	mzed_mul_newton_john (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\(C = A \cdot B\) using Newton-John tables. More...
mzed_t *	mzed_addmul_newton_john (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\(C = C + A \cdot B\) using Newton-John tables. More...
mzed_t *	_mzed_mul_newton_john0 (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\(C = C + A \cdot B\) using Newton-John tables. More...
mzed_t *	_mzed_mul_newton_john (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\(C = C + A \cdot B\) using Newton-John tables. More...
rci_t	mzed_echelonize_newton_john (mzed_t *A, int full)
	Reduce matrix A to row echelon form using Gauss-Newton-John elimination. More...
mzed_t *	mzed_invert_newton_john (mzed_t *B, const mzed_t *A)
	Invert the matrix A using Gauss-Newton-John elimination. More...
void	mzed_trsm_lower_left_newton_john (const mzed_t *L, mzed_t *B)
	\(B = L^{-1} \cdot B\) using Newton-John tables. More...
void	mzd_slice_trsm_lower_left_newton_john (const mzd_slice_t *L, mzd_slice_t *B)
	\(B = L^{-1} \cdot B\) using Newton-John tables. More...
void	mzed_trsm_upper_left_newton_john (const mzed_t *U, mzed_t *B)
	\(B = U^{-1} \cdot B\) using Newton-John tables. More...
void	mzd_slice_trsm_upper_left_newton_john (const mzd_slice_t *U, mzd_slice_t *B)
	\(B = U^{-1} \cdot B\) using Newton-John tables. More...
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.
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 from T to the row i. More...
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. More...
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. More...
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. More...
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. More...
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. More...

Detailed Description

Newton-John table based algorithms.

Note

These tables were formally known as Travolta tables.

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

mzed_t* mzed_invert_newton_john	(	mzed_t *	B,
		const mzed_t *	A
	)

Invert the matrix A using Gauss-Newton-John elimination.

Parameters

B	Preallocated space for inversion matrix, may be NULL for automatic creation.
A	Matrix to be inverted.

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

Parameters

T	Preallocated Newton-John table or NULL.
A	Matrix.
r	Row index.
c	Column index.

void njt_mzed_free

(

njt_mzed_t *

t

)

Free Newton-John table.

Parameters

t

Table

njt_mzed_t* njt_mzed_init	(	const gf2e *	ff,
		const rci_t	ncols
	)

Allocate Newton-John table of dimension gf2e::degree<<1 * ncols.

Parameters

ff	Finite field.
ncols	Integer > 0.