header
SparseMatrixMultiply

Tag:
Edit edit   Starstar

Program Information

Name: SparseMatrixMultiply
Domain: Numerical program
Functionality: Conducting the multiplication of two sparse matrices
Input: A: One n*p matrix(Type: Matrix) B:One p*m matrix(Type: Matrix)
Output: C: One n*m matrix = A * B(Type: Matrix)

Reference

 How Effectively Does Metamorphic Testing Alleviate the Oracle Problem? http://dx.doi.org/10.1109/TSE.2013.46 

MR Information

MR1------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f_{i,h}=A^s_{i,p+1-h}$ $B^f_{h,j}=B^s_{p+1-h,j}$ $A^f_{i,h},A^s_{i,p+1-h},B^f_{h,j},B^s_{p+1-h,j}$, are the elements of $A^f,A^s,B^f,B^s$, respectively.
Output relation: C^f = C^s
Pattern:

MR2------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f_{i,h} = x_i \times A^s_{i,h}$, where $x_i$ is a random real number(i = 1,2,……,n). $B^f = B^s$
Output relation: $C^f_{i,j} = x_i \times C^s_{i,j}$
Pattern:

MR3------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f = (A^s)^T$ $B^f = (B^s)^T$, where $M^T$ is the transposition of the matrix M.
Output relation: $C^f = C^s$
Pattern:

MR4------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f_{(n+p) \times p}$,where the upper $n \times p$ part is exactly the same as $A^s$ ,and the lower $p \times p$ is identical to $I_p$ (a unit $p\times p$ matrix). $B^f_{p \times (m+p)}$,where the leftmost $p \times m$ part is exactly the same as $B^s$ ,and the rightmost $p \times p$ is identical to $I_p$.
Output relation: (1)The upper-left $n \times m$ part of $C^f = C^s$. (2)The upper-right $n \times p$ part of $C^f = A^s$. (3)The lower-left $p \times m$ part of $C^f = B^s$. (4)The lower-right $p \times p$ part of $C^f = I_p$.
Pattern:

MR5------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f$ = Swapping the $i_{1}$th row and the $i_{2}$th row in $A^s$. $B^f = B^s$
Output relation: $C^f$ = The matrix where the $i_{1}$th row and the $i_{2}$th row of $C^s$ are swapped.
Pattern:

MR6------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f= A^s$ $B^f$ = Swapping the $j_{1}$th column and the $j_{2}$th column in $B^s$
Output relation: $C^f$ = The matrix where the $j_{1}$th column and the $j_{2}$th column of $C^s$ are swapped.
Pattern:

MR7------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f = x \times A^s$ $B^f = y \times B^s$, where x is a real number and y is a real number ,too.
Output relation: $C^f = ab \times C^s$
Pattern:

MR8------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f = A^s$ $B^f$ = Setting all elements on the jth column of $B^s$ to 0 while keeping all other elements of $B^s$ unchanged.
Output relation: All the elements on the jth column of $C^f$ are all zero,while the other elements are identical to the corresponding elements of $C^s$.
Pattern:

MR9------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f = A^s$ $B^f$ = The jth column of $B^s$.
Output relation: $C^f$ = The jth column of $C^s$.
Pattern:

MR10------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^{f_1},A^{f_2},B^f$
Follow-up output: $C^{f_1},C^{f_2}$
Input relation: $A^{f_1}+A^{f_2}=A^s$ $B^f = B^s$ $C^{f_1} = A^{f_1} \times B^f$ $C^{f_2} = A^{f_2} \times B^f$
Output relation: $C^{f_1} + C^{f_2} = C^s$.
Pattern:

MR11------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^{f_1},B^{f_2}$
Follow-up output: $C^{f_1},C^{f_2}$
Input relation: $A^f = A^s$ $B^{f_1}_{p \times m_1}$ = The leftmost $p\times m_1$ part of $B^s$ $B^{f_2}_{p \times m_2}$ = The rightmost $p \times m_2$ part of $B^s$ ,and $m = m_1+m_2$ $C^{f_1} = A^f \times B^{f_1}$ $C^{f_2} = A^f \times B^{f_2}$
Output relation: $C^{f_1}_{p \times m_1}$ =The leftmost $p\times m_1$ part of $C^s$. $C^{f_2}_{p \times m_2}$ = The rightmost $p \times m_2$ part of $C^s$.
Pattern:

MR12------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^{f_1},B^{f_2}$
Follow-up output: $C^{f_1},C^{f_2}$
Input relation: $A^{f_1}_{n_1 \times p}$ = The upper $n_1 \times p$ part of $A^s$. $A^{f_2}_{n_2 \times p}$ = The lower $n_2 \times p$ part of $A^s$, $n = n_1+n_2$. $B^f = B^s$ $C^{f_1} = A^{f_1} \times B^f$ $C^{f_2} = A^{f_2} \times B^f$
Output relation: The $n_1\times p$ matrix $C^{f_1}$ = The upper $n_1\times p$ part of $C^s$. The $n_2\times p$ matrix Cf2 = The lower $n_2\times p$ part of $C^s$.
Pattern:

MR13------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f_{n \times (p+q)}$ = Adding $n \times q$ zeros to the right of $A^s$. $B^f_{(p+q) \times m}$ = Adding $q \times m$ zeros to the bottom of $B^s$.
Output relation: $C^f = C^s$
Pattern:

MR14------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f_{(n+q_{1}) \times p}$ = Adding $q_{1} \times p$ zeros to the bottom of $A^s$. $B^f_{p \times (m+q_{2})}$ = Adding $p \times q_{2}$ zeros to the right of $B^s$.
Output relation: The upper-left $n \times m$ part of $C^f_{(n+q_{1}) \times (m+q_{2})}$ = $C^s$ ,while the elements in the other parts are all zeros.
Pattern:

MR15------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f$ = Setting all elements on the ith row of $A^s$ to 0 while keeping all other elements of $A^s$ unchanged. $B^f = B^s$.
Output relation: The elements on the ith row of $C^f$ are all zeros, while all the other elements are identical to the corresponding elements of $C^s$
Pattern:

MR16------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f$ = Randomly select two rows, the $i_{1}$th row and the $i_{2}$th row, for each element $A^s_{i_{1},j}$ on the $i_{1}$th row of $A^s$, change it to $A^f_{i_{1},j}$ = $A^s_{i_{1},j}$ + $x \times A^s_{i_{2},j}$,where x is a real number; while the elements on all other rows remain unchanged. $B^f = B^s$.
Output relation: $C^f_{i_{1},j} = C^s_{i_{1},j}j + x \times C^s_{i_{2},j} $; while all the other elements not on the $i_{1}$th row of $C^f$ are identical to the corresponding elements in $C^s$.
Pattern:

MR17------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f$ = Deleting (i,h,a) from $A^s$. $B^f$ = Deleting (h,j,b) from $B^s$. (i,h,a) and (h,j,b) are two tuples of A and B(that is, the element on the ith row and the hth column is a 0, (h,j,b) is the same.)
Output relation: $C^f_{i,j} = C^s_{i,j} - ab$
Pattern:

MR18------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f$ = Adding a tuple (i,h,a) to $A^s$. $B^f$ = Adding a tuple (h,j,b) to $B^s$. For $A^s$ ,there does not exist a tuple with $irn_k$ = i and $jcn_k$ = h(that is, the element on the ith row and the hth column id 0), and for $B^s$, there does not exist a tuple with $irn_k$ = h and $jcn_k$ = j.
Output relation: $C^f_{i,j} = C^s_{i,j} + ab$
Pattern:

MR19------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f$ = Changing the order of the tuple $(irn_k,jcn_k,val_k)$ of the $A^s$. $B^f$ = Changing the order of the tuple $(irn_k,jcn_k,val_k)$ of the $B^s$.
Output relation: $C^f = C^s$
Pattern:

MR20------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f$ = Changing a1 to a2 of $A^s$, for $A^s$, there exists a tuple $(i,h,a_{1})$. $B^f$ = Changing b1 to b2 of $B^s$, for $B^s$, there exists a tuple $(i,h,b_{1})$.
Output relation: $C^f_{i,j} = C^s_{i,j} + a_{2} \times b_{2} - a_{1} \times b_{1}$
Pattern:

MR21------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f$ = Replacing $(i_{1},h,a)$ by $(i_{2},h,a)$ in $A^s$, for $A^s$, there exists a tuple $(i_{1},h,a)$ but there does not exists a tuple with $irn_k = i_{2}$ and $jcn_k = h$. $B^f$ = Replacing $(h,j_{1},b)$ by $(h,j_{2},b)$ in $B^s$, for $B^s$, there exists a tuple $(h,j_{1},b)$ but there does not exists a tuple with $irn_k = h$ and $jcn_k = j_{2}$.
Output relation: $C^f_{i_{1},j_{1}}=C^s_{i_{1},j_{1}}-a \times b$ and $C^f_{i_{2},j_{2}}=C^s_{i_{2},j_{2}}-a \times b$
Pattern:

MR22------

Description:
Property:
Source input: $A^s,B^s$
Source output: $C^s$
Follow-up input: $A^f,B^f$
Follow-up output: $C^f$
Input relation: $A^f$ = Replacing $(i,h_{1},a)$ by $(i,h_{2},a)$ in $A^s$, for $A^s$, there exists a tuple $(i,h_{1},a)$ but there does not exists a tuple with $irn_k = i$ and $jcn_k = h_{2}$. $B^f$ = Replacing $(h_{1},j,b)$ by $(h_{2},j,b)$ in $B^s$, for $B^s$, there exists a tuple $(h_{1},j,b)$ but there does not exists a tuple with $irn_k = h_{2}$ and $jcn_k = j$.
Output relation: $C^f_{i,j} = C^s_{i,j}$
Pattern:
Insert title here