strassen.h File Reference

Matrix operations using Strassen's formulas including Winograd's improvements. More...

#include <math.h>
#include <m4ri/mzd.h>
#include <m4ri/brilliantrussian.h>

Go to the source code of this file.

Macros
#define	__M4RI_STRASSEN_MUL_CUTOFF   MIN(((int)sqrt((double)(4 * __M4RI_CPU_L3_CACHE))), 4096)

Functions
mzd_t *	mzd_mul (mzd_t *C, mzd_t const *A, mzd_t const *B, int cutoff)
	Matrix multiplication via the Strassen-Winograd matrix multiplication algorithm, i.e. compute C = AB. More...
mzd_t *	mzd_addmul (mzd_t *C, mzd_t const *A, mzd_t const *B, int cutoff)
	Matrix multiplication and in-place addition via the Strassen-Winograd matrix multiplication algorithm, i.e. compute C = C+ AB. More...
mzd_t *	_mzd_mul_even (mzd_t *C, mzd_t const *A, mzd_t const *B, int cutoff)
	Matrix multiplication via the Strassen-Winograd matrix multiplication algorithm, i.e. compute C = AB. More...
mzd_t *	_mzd_addmul_even (mzd_t *C, mzd_t const *A, mzd_t const *B, int cutoff)
	Matrix multiplication and in-place addition via the Strassen-Winograd matrix multiplication algorithm, i.e. compute C = C+ AB. More...
mzd_t *	_mzd_addmul (mzd_t *C, mzd_t const *A, mzd_t const *B, int cutoff)
	Matrix multiplication and in-place addition via the Strassen-Winograd matrix multiplication algorithm, i.e. compute C = C + AB. More...

Detailed Description

Matrix operations using Strassen's formulas including Winograd's improvements.

Author

Gregory Bard bard@.nosp@m.ford.nosp@m.ham.e.nosp@m.du

Martin Albrecht M.R.A.nosp@m.lbre.nosp@m.cht@r.nosp@m.hul..nosp@m.ac.uk

Macro Definition Documentation

#define __M4RI_STRASSEN_MUL_CUTOFF   MIN(((int)sqrt((double)(4 * __M4RI_CPU_L3_CACHE))), 4096)

The default cutoff for Strassen-Winograd multiplication. It should hold hold that 2 * (n^2)/8 fits into the L2 cache.

Function Documentation

mzd_t* _mzd_addmul	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B,
		int	cutoff
	)

Matrix multiplication and in-place addition via the Strassen-Winograd matrix multiplication algorithm, i.e. compute C = C + AB.

The matrices A and B are respectively m x k and k x n, and can be not aligned on the m4ri_radix grid.

Parameters

C	Preallocated product matrix, may be NULL for automatic creation.
A	Input matrix A
B	Input matrix B
cutoff	Minimal dimension for Strassen recursion.

Assumes that B and C are aligned in the same manner (as in a Schur complement)

mzd_t* _mzd_addmul_even	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B,
		int	cutoff
	)

Matrix multiplication and in-place addition via the Strassen-Winograd matrix multiplication algorithm, i.e. compute C = C+ AB.

This is the actual implementation. Any matrix where either the number of rows or the number of columns is smaller than cutoff is processed using the M4RM algorithm.

Parameters

C	Preallocated product matrix, may be NULL for automatic creation.
A	Input matrix A
B	Input matrix B
cutoff	Minimal dimension for Strassen recursion.

Note

This implementation is heavily inspired by the function strassen_window_multiply_c in Sage 3.0; For reference see http://www.sagemath.org

Todo:

make sure not to overwrite crap after ncols and before width * m4ri_radix

Note

See Marco Bodrato; "A Strassen-like Matrix Multiplication Suited for Squaring and Highest Power Computation"; http://bodrato.it/papres/#CIVV2008 for reference on the used sequence of operations.

mzd_t* _mzd_mul_even	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B,
		int	cutoff
	)

Matrix multiplication via the Strassen-Winograd matrix multiplication algorithm, i.e. compute C = AB.

This is the actual implementation. Any matrix where either the number of rows or the number of columns is smaller than cutoff is processed using the M4RM algorithm.

Parameters

C	Preallocated product matrix, may be NULL for automatic creation.
A	Input matrix A
B	Input matrix B
cutoff	Minimal dimension for Strassen recursion.

Note

This implementation is heavily inspired by the function strassen_window_multiply_c in Sage 3.0; For reference see http://www.sagemath.org

Note

See Marco Bodrato; "A Strassen-like Matrix Multiplication Suited for Squaring and Highest Power Computation"; http://bodrato.it/papres/#CIVV2008 for reference on the used sequence of operations.

Todo:

ideally we would use the same Wmk throughout the function but some called function doesn't like that and we end up with a wrong result if we use virtual Wmk matrices. Ideally, this should be fixed not worked around. The check whether the bug has been fixed, use only one Wmk and check if mzd_mul(4096, 3528, 4096, 2124) still returns the correct answer.

mzd_t* mzd_addmul	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B,
		int	cutoff
	)

Matrix multiplication and in-place addition via the Strassen-Winograd matrix multiplication algorithm, i.e. compute C = C+ AB.

This is the wrapper function including bounds checks. See _mzd_addmul_even for implementation details.

Parameters

C	product matrix
A	Input matrix A
B	Input matrix B
cutoff	Minimal dimension for Strassen recursion.

Examples:

testsuite/test_multiplication.c, and testsuite/test_ple.c.

mzd_t* mzd_mul	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B,
		int	cutoff
	)

Matrix multiplication via the Strassen-Winograd matrix multiplication algorithm, i.e. compute C = AB.

This is the wrapper function including bounds checks. See _mzd_mul_even for implementation details.

Parameters

C	Preallocated product matrix, may be NULL for automatic creation.
A	Input matrix A
B	Input matrix B
cutoff	Minimal dimension for Strassen recursion.

Examples:

testsuite/bench_elimination.c, testsuite/test_multiplication.c, and testsuite/test_ple.c.