M4RI  1.0.1
Macros | Functions
strassen.h File Reference

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

#include <math.h>
#include "mzd.h"
#include "brilliantrussian.h"

Go to the source code of this file.

Macros

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

Functions

mzd_tmzd_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.
mzd_tmzd_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.
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.
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.
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.
mzd_t_mzd_addmul_weird_weird (mzd_t *C, mzd_t const *A, mzd_t const *B)
mzd_t_mzd_addmul_weird_even (mzd_t *C, mzd_t const *A, mzd_t const *B, int cutoff)
mzd_t_mzd_addmul_even_weird (mzd_t *C, mzd_t const *A, mzd_t const *B, int cutoff)

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_L2_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:
CPreallocated product matrix, may be NULL for automatic creation.
AInput matrix A
BInput matrix B
cutoffMinimal 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:
CPreallocated product matrix, may be NULL for automatic creation.
AInput matrix A
BInput matrix B
cutoffMinimal 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_addmul_even_weird ( mzd_t C,
mzd_t const *  A,
mzd_t const *  B,
int  cutoff 
)

C = A*B + C for A with offset != 0 and B with offset == 0.

This is scratch code.

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

C = A*B + C for A with offset == 0 and B with offset != 0.

This is scratch code.

mzd_t* _mzd_addmul_weird_weird ( mzd_t C,
mzd_t const *  A,
mzd_t const *  B 
)

C = A*B + C for matrices with offsets != 0

This is scratch code.

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:
CPreallocated product matrix, may be NULL for automatic creation.
AInput matrix A
BInput matrix B
cutoffMinimal 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.
   \xrefitem todo 11.
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:
Cproduct matrix
AInput matrix A
BInput matrix B
cutoffMinimal 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:
CPreallocated product matrix, may be NULL for automatic creation.
AInput matrix A
BInput matrix B
cutoffMinimal dimension for Strassen recursion.
Examples:
testsuite/bench_elimination.c, testsuite/test_multiplication.c, and testsuite/test_ple.c.