Detailed Description

A matrix window is a rectangular part of a matrix. As an implementation detail, each row of the window must be formed by longs. Hence, not all upper left corners are allowed and not all row sizes are possible.

Matrix windows are used in the asymptoticall fast Strassen-Winograd multiplication algorithm, that is a divide-and-conquer algorithm. In order to avoid the allocation of additional matrices (thus, in order to be efficient), intermediate results are stored in the same matrix that will eventuall contain the final result of the multiplication.

We use the memory efficient schedule of Douglas-Heroux-Slishman-Smith described in [BDPZ09].

Data Structures
struct	MatrixWindow_t
	Matrix Window. More...

Functions
void	StrassenSetCutoff (size_t size)
	Set the cutoff for Winograd-Strassen multiplication. More...

MatrixWindow_t *	WindowAlloc (int fl, int nor, size_t rowsize)
	Allocation and null initialisation of a matrix window. More...

void	WindowFree (MatrixWindow_t *m)
	Release the memory used by this window. More...

void	WindowClear (MatrixWindow_t *A)
	Overwrite the window by zeroes, but let the rest of the ambient matrix untouched. More...

void	FfAddMapRowWindow (PTR row, PTR matrix, int nor, PTR result, size_t rowsize)
	Multiply a vector by a matrix window. More...

MatrixWindow_t *	WindowSum (MatrixWindow_t dest, MatrixWindow_t left, MatrixWindow_t *right)
	Add two matrix windows left and right and put the result into dest. More...

MatrixWindow_t *	WindowDif (MatrixWindow_t dest, MatrixWindow_t left, MatrixWindow_t *right)
	Subtract two matrix windows left and right and put the result into dest. More...

MatrixWindow_t *	WindowAddMul (MatrixWindow_t dest, MatrixWindow_t left, MatrixWindow_t *right)
	Add left * right to dest. More...

void	MatrixToWindow (MatrixWindow_t out, const Matrix_t M, long nor, long rowsize, PTR p)
	Create a window of a matrix. More...

int	StrassenStep (MatrixWindow_t dest_win, MatrixWindow_t A_win, MatrixWindow_t *B_win)
	Multiply matrix windows. More...

Function Documentation

void FfAddMapRowWindow	(	PTR	row,
		PTR	matrix,
		int	nor,
		PTR	result,
		size_t	rowsize
	)

Multiply a vector by a matrix window.

This function multiplies the vector row from the right by the matrix window pointed at by matrix and adds the result into result. The number of columns in both matrix and result is determined by rowsize.

Attention: result and row must not overlap. Otherwise the result is undefined!

Parameters

	row	The source vector, formed by nor columns.
	matrix	A pointer to a mark in a matrix, defining a window in a matrix whose rowsize is FfCurrRowSize. ( nor by (rowsizesizeof(long)MPB)) of a matrix whose
	nor	Number of rows or the matrix window.
[out]	result	The vector which row * matrix is added to. It has rowsize * sizeof(long) * MPB columns.
	rowsize	Number of longs forming a row of matrix.

void MatrixToWindow	(	MatrixWindow_t *	out,
		const Matrix_t *	M,
		long	nor,
		long	rowsize,
		PTR	p
	)

inline

Create a window of a matrix.

Parameters

out	An allocated matrix window whose data fields will be filled with new data.
M	matrix.
nor	Number of rows of the window.
rowsize	Rowsize of the window, which must correspond to a block of longs in memory.
p	Pointer to the upper left corner of the window

void StrassenSetCutoff ( size_t size )

Set the cutoff for Winograd-Strassen multiplication.

The divide-and-conquer approach is only done for matrices with at least "cutoff*MPB*sizeof(long)" rows which are formed by at least "cutoff" longs. That rule means that the "critical matrices" are roughly square.

If size is zero, the default cutoff "sizeof(long)/2" is used.

Parameters

size	New cutoff.

int StrassenStep	(	MatrixWindow_t *	dest_win,
		MatrixWindow_t *	A_win,
		MatrixWindow_t *	B_win
	)

Multiply matrix windows.

This function multiplies A_win from the right by B_win and writes the result into dest_win.

Attention: dest must be initialised to zero!

The matrix windows must be compatible for multiplication, i.e. they must be over the same field, and the number of columns of A_win must be equal to the number of rows of B_win.

Moreover, it is assumed that dest_win is allocated in the right dimensions. Since parts of dest_win are used to store temporary results, it is essential that dest_win initially is zero.

Parameters

[out]	dest_win	Result.
	A_win	Left factor.
	B_win	Right factor

Returns: The function returns 0 on success and a nonzero value on error.

Note that the rowsize is given in the unit "long". Generally we have trailing padding empty bytes. We have to cut so that two full blocks fit into the non-padded area. This is what we do:

We halve the number of rows of A (rounded down).
We halve the rowsize of B (rounded down) , since padding doesn't matter here.
We determine how many FULL longs fit into a row (of A) of B->Nor items. Half of it (rounded down) gives the rowsize of A's submatrices.
From that rowsize, we obtain the corresponding number of rows of B's submatrices.

MatrixWindow_t* WindowAddMul	(	MatrixWindow_t *	dest,
		MatrixWindow_t *	left,
		MatrixWindow_t *	right
	)

Add left * right to dest.

It is assumed that dest->Matrix is allocated with the correct field and dimensions as well, so that we can write the result into it. Moreover, the chunk of memory pointed at by dest must be disjoint from the chunks for left and right! Compatibility of dimensions is not tested

Parameters

[out]	dest	Matrix window which the product of left and right is added to.
	left	Matrix window.
	right	Matrix window.

Returns: dest, there is no error return value.

MatrixWindow_t* WindowAlloc	(	int	fl,
		int	nor,
		size_t	rowsize
	)

Allocation and null initialisation of a matrix window.

Note that the rowsize is given in long, not in byte. The reason is functions such as FfAddRowPartial() or FfAddMapRowWindow() are internally operating on longs. By consequence, in the Strassen-Winograd multiplication algorithm, we have to divide our matrix rows into longs, not into bytes.

Parameters

fl	Field size.
nor	Number of rows.
rowsize	Rows are formed by rowsize longs in memory.

Returns: Matrix window, with pointer in the upper left corner, initialised to zero.

void WindowClear ( MatrixWindow_t * A )

Overwrite the window by zeroes, but let the rest of the ambient matrix untouched.

Parameters

A	The matrix window to be zeroed out.

MatrixWindow_t* WindowDif	(	MatrixWindow_t *	dest,
		MatrixWindow_t *	left,
		MatrixWindow_t *	right
	)

Subtract two matrix windows left and right and put the result into dest.

left and right must be distinct, but one of them may coincide with dest

Parameters

[out]	dest	Matrix window which the results is to be assigned to.
	left	Matrix window.
	right	Matrix window.

Returns: Either dest or the NULL pointer on error (the only error may occur in a compatibility check).

void WindowFree ( MatrixWindow_t * m )

Release the memory used by this window.

Attention: Only to be used if the surrounding matrix can be destroyed! Otherwise, just do free(m)!

Parameters

m	Matrix window to be freed.

MatrixWindow_t* WindowSum	(	MatrixWindow_t *	dest,
		MatrixWindow_t *	left,
		MatrixWindow_t *	right
	)

Add two matrix windows left and right and put the result into dest.

left and right must be distinct, but one of them may coincide with dest

Parameters

[out]	dest	Matrix window which the results is to be assigned to.
	left	Matrix window.
	right	Matrix window.

Returns: Either dest or the NULL pointer on error (the only error may occur in a compatibility check).

Detailed Description

Data Structures

Functions

Function Documentation