-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtable-graphblas-notation.tex
82 lines (81 loc) · 15.1 KB
/
table-graphblas-notation.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
\setlength{\tabcolsep}{1.9pt}
%\renewcommand\arraystretch{0.85}
\begin{table}[htbp]
\centering
\begin{tabular}{llr@{}l}
\toprule
\multicolumn{1}{c}{\bf op./method} & \multicolumn{1}{c}{\bf name} & \multicolumn{2}{c}{\bf notation} \\
\midrule
\tt mxm & matrix-matrix multiplication & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A} \grbplustimes \grbm{B}$ \\
\tt vxm & vector-matrix multiplication & $\grbv{\grbv{w}} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{u} \grbplustimes \grbm{A}$ \\
\tt mxv & matrix-vector multiplication & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbm{A} \grbplustimes \grbv{u}$ \\
% \midrule
% \multirow{2}{*}{\tt eWiseAdd} & element-wise addition & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A} \grbplus \grbm{B}$ \\
% & set union of patterns & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{u} \grbplus \grbv{v}$ \\
% \midrule
% \multirow{2}{*}{\tt eWiseMult} & element-wise multiplication & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A} \grbtimes \grbm{B}$ \\
% & set intersection of patterns & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{u} \grbtimes \grbv{v}$ \\
\midrule
\multirow{2}{*}{\tt eWiseAdd} & element-wise addition & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A} \grbewiseadd{\grbgenericop} \grbm{B}$ \\
& set union of patterns & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{u} \grbewiseadd{\grbgenericop} \grbv{v}$ \\
\midrule
\multirow{2}{*}{\tt eWiseMult} & element-wise multiplication & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A} \grbewisemult{\grbgenericop} \grbm{B}$ \\
& set intersection of patterns & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{u} \grbewisemult{\grbgenericop} \grbv{v}$ \\
\midrule
\multirow{4}{*}{\tt extract} & extract submatrix & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A}(\grba{i}, \grba{j})$ \\
& extract column vector & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{A}(:, \grbs{j})$ \\
& extract row vector & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{A}(\grbs{i}, :)$ \\
& extract subvector & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{u}(\grba{i})$ \\
\midrule
\multirow{4}{*}{\tt assign} & assign matrix to submatrix with mask for $\grbm{C}$ & $\grbm{C} \grbmask{\grbm{M}} (\grba{i},\grba{j}) $ & $\grbaccumeq{} \grbm{A}$ \\
& assign scalar to submatrix with mask for $\grbm{C}$ & $\grbm{C} \grbmask{\grbm{M}} (\grba{i},\grba{j}) $ & $\grbaccumeq{} \grbs{s}$ \\
& assign vector to subvector with mask for $\grbv{w}$ & $\grbv{w} \grbmask{\grbv{m}} (\grba{i}) $ & $\grbaccumeq{} \grbv{u}$ \\
& assign scalar to subvector with mask for $\grbv{w}$ & $\grbv{w} \grbmask{\grbv{m}} (\grba{i}) $ & $\grbaccumeq{} \grbs{s}$ \\
\midrule
\multirow{4}{*}{\tt subassign (GxB)} & assign matrix to submatrix with submask for $\grbm{C}(\grba{i},\grba{j})$ & $\grbm{C}(\grba{i},\grba{j}) \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A}$ \\
& assign scalar to submatrix with submask for $\grbm{C}(\grba{i},\grba{j})$ & $\grbm{C}(\grba{i},\grba{j}) \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbs{s}$ \\
& assign vector to subvector with submask for $\grbv{w}(\grba{i})$ & $\grbv{w}(\grba{i}) \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{u}$ \\
& assign scalar to subvector with submask for $\grbv{w}(\grba{i})$ & $\grbv{w}(\grba{i}) \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbs{s}$ \\
\midrule
\multirow{2}{*}{\tt apply} & \multirow{2}{*}{apply unary operator} & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbf{f}{\grbm{A}}$ \\
& & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbf{f}{\grbv{u}}$ \\
\midrule
\multirow{2}{*}{\tt select} & \multirow{2}{*}{apply select operator} & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A}\grbselect{\grbf{f}{\grbm{A}, \grbs{k}}}$ \\
& & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{u}\grbselect{\grbf{f}{\grbv{u}, \grbs{k}}}$ \\
\midrule
\multirow{3}{*}{\tt reduce} & reduce matrix to column vector & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbreduce{\grbplus}{\grbs{j}}{\grbm{A}}{:,\grbs{j}}$ \\
& reduce matrix to scalar & $\grbs{s} $ & $\grbaccumeq{} \grbreduce{\grbplus}{\grbs{i}\grbs{j}}{\grbm{A}}{\grbs{i},\grbs{j}}$ \\
& reduce vector to scalar & $\grbs{s} $ & $\grbaccumeq{} \grbreduce{\grbplus}{\grbs{i}}{\grbm{u}}{\grbs{i}}$ \\
\midrule
\multirow{1}{*}{\tt transpose} & transpose & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A}\grbt$ \\
\midrule
\tt kronecker & Kronecker multiplication & $\grbm{C} \grbmask{\grbm{M}}$ & $\grbaccumeq{} \grbkron{\grbm{A}, \grbm{B}}$ \\
\midrule\midrule % operations above, methods below
\multirow{2}{*}{\tt new} & new matrix & \multicolumn{2}{l}{$\grbnewmatrix{\grbm{A}}{\grbplaceholder{TYPE}}{\grbplaceholder{PRECISION}}{n}{m}$} \\
& new vector & \multicolumn{2}{l}{$\grbnewvector{\grbv{u}}{\grbplaceholder{TYPE}}{\grbplaceholder{PRECISION}}{n}$} \\
\midrule
\multirow{2}{*}{\tt build} & matrix from tuples & $\grbm{C}\ $ & $\grbassign \left\{ \grba{i}, \grba{j}, \grba{x} \right\} $ \\
& vector from tuples & $\grbv{w}\ $ & $\grbassign \left\{ \grba{i}, \grba{x} \right\} $ \\
\midrule
\multirow{2}{*}{\tt extractTuples} & \multirow{2}{*}{extract index/value arrays} & $ \left\{ \grba{i}, \grba{j}, \grba{x} \right\} $ & $\grbassign \grbm{A} $ \\
& & $ \left\{ \grba{i}, \grba{x} \right\} $ & $\grbassign \grbv{u} $ \\
\midrule
\multirow{2}{*}{\tt dup} & duplicate matrix & $\grbm{C} $ & $\grbassign \grbm{A}$ \\
& duplicate vector & $\grbv{w} $ & $\grbassign \grbv{u}$ \\
\midrule
\multirow{2}{*}{\tt extractElement} & \multirow{2}{*}{extract scalar element} & $\grbs{s} $ & $\ = \grbm{A}(\grbs{i}, \grbs{j})$ \\
& & $\grbs{s} $ & $\ = \grbv{u}(\grbs{i})$ \\
\midrule
\multirow{2}{*}{\tt setElement} & \multirow{2}{*}{set element} & $\grbm{C}(\grbs{i}, \grbs{j}) $ & $\ = \grbs{s}$ \\
& & $\grbv{w}(\grbs{i})$ & $\ = \grbs{s}$ \\
\bottomrule
\end{tabular}
\caption{GraphBLAS operations and methods based on \cite{DBLP:journals/toms/Davis19}.
\emph{Notation:}
Matrices and vectors are typeset in bold, starting with uppercase ($\grbm{A}$) and lowercase ($\grbv{u}$) letters, respectively.
Scalars including indices are lowercase italic ($\grbs{k}$, $\grbs{i}$, $\grbs{j}$) while arrays are lowercase bold italic ($\grba{x}$, $\grba{i}$, $\grba{j}$).
$\grbplus$ and $\grbtimes$ are the addition and multiplication operators forming a semiring and default to conventional arithmetic $+$ and $\times$ operators.
$\grbaccum$ is the accumulator operator.
}
\label{tab:graphblas-notation}
\end{table}