Greased Matrices

Detailed Description

A greased matrix is a matrix over a finite field, which has been optimized for fast row operations. The optimization ("grease") is achieved by precomputing linear combinations of blocks of rows.

The number of rows per block, also called grease level, is restricted to the range 1...16. Grease level 3, for example, means that the rows of the matrix are divided in blocks of three rows, and for each block, all linear combinations of the three rows are calculated once. Multiplying a single vector by the matrix can then be carried out with only n/3 row operations.

On the other hand, the greased matrix needs more memory. For grease level 8 with GF(2), the memory needed is increased by a factor of 32.

Data Structures
struct	GrExtractionTable_t
	Extraction table for greasing. More...
struct	GreasedMatrix_t
	A greased matrix. More...

Functions
void	GrMapRow (PTR v, GreasedMatrix_t *M, PTR w)
	Multiply a vector by a greased matrix. More...
int	GrMatIsValid (const GreasedMatrix_t *mat)
	Check a greased matrix. More...
int	GrMatFree (GreasedMatrix_t *mat)
	Free a greased matrix. More...
GreasedMatrix_t *	GrMatAlloc (const Matrix_t *M, int gr_rows)
	Create a greased matrix. More...
const GrExtractionTable_t *	GrGetExtractionTable (int fl, int grrows)
	Calculate extraction table for grease. More...

Function Documentation

const GrExtractionTable_t * GrGetExtractionTable	(	int	fl,
		int	grrows
	)

Calculate extraction table for grease.

This function calculates the extraction table for greased matrix operations for a particular combination of field order and grease level. The grease level must be in the range 1...16. To avoid frequent table recalculations, tables are stored in a cache.

Parameters

fl	Field order.
grrows	Grease level, number of rows per block.

Returns

Pointer to the extraction table, or NULL on error.

void GrMapRow	(	PTR	v,
		GreasedMatrix_t *	M,
		PTR	w
	)

Multiply a vector by a greased matrix.

This function calculates the matrix product of the vector v with the matrix M and write the result to w. The length of v must coincide with the number of rows of M. The result w is as long as the length of a row of M. Unlike FfMapRow(), this function sets field and row length correctly!

Parameters

v	The vector.
M	Pointer to the matrix.
w	The result, vM.

GreasedMatrix_t * GrMatAlloc	(	const Matrix_t *	M,
		int	gr_rows
	)

Create a greased matrix.

This function creates a greased matrix from an existing normal matrix. Basically, this means that linear combinations of the rows of mat are calculated and stored in a buffer. The number of precalculated rows depends on the field order and the grease level. The original matrix is unchanged, and the caller is responsible for deleting it. gr_nrows is the grease level, or block size, and must be in the range 0...16. A grease level of 0 means that greasing is switched off.

To destroy a greased matrix, use GrMatFree().

Parameters

M	The normal matrix.
gr_rows	Grease level (number of rows per block).

Returns

Pointer to the greased matrix or 0 on error.

int GrMatFree

(

GreasedMatrix_t *

mat

)

Free a greased matrix.

0 on success, -1 on error. This function frees a greased matrix, releasing all internally allocated memory. Note that some data structures (the extraction tables) are kept in a cache and are never freed until the process terminates.

Parameters

mat	The matrix to be freed.

Returns

0 on success, -1 on error.

int GrMatIsValid

(

const GreasedMatrix_t *

mat

)

Check a greased matrix.

This function checks if the argument |mat| is a pointer to a valid greased matrix. If the matrix is o.k., the function returns 1. Otherwise, an error is signalled and, if the error handler does not terminate the program, the function returns 0.

Parameters

mat	Pointer to the matrix.

Returns

1 if mat points to a valid greased matrix, 0 otherwise.