-
Notifications
You must be signed in to change notification settings - Fork 2
/
table-graphblas-notation.tex
94 lines (93 loc) · 14.2 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
83
84
85
86
87
88
89
90
91
92
93
94
%\setlength{\tabcolsep}{1.9pt}
%\renewcommand\arraystretch{0.85}
\begin{table*}[htbp]
\centering
\begin{tabular}{llr@{}ll}
\toprule
\multicolumn{1}{c}{\bf operation/method} & \multicolumn{1}{c}{\bf description} & \multicolumn{2}{c}{\bf notation} \\
% <operations>
\midrule
\tt mxm & matrix-matrix multiplication & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A} \grbplustimes \grbm{B}$ \\
\tt vxm & vector-matrix multiplication & $\grbv{w}\grbt \grbmask{\grbv{m}\grbt} $ & $\grbaccumeq{} \grbv{u}\grbt \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 using operator $\grbgenericop$ & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A} \grbewiseadd{\grbgenericop} \grbm{B}$ \\
& on elements in the set union of structures of $\grbm{A}/\grbm{B}$ and $\grbv{u}$/$\grbv{v}$ & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{u} \grbewiseadd{\grbgenericop} \grbv{v}$ \\
\midrule
\multirow{2}{*}{\tt eWiseMult} & element-wise multiplication using operator $\grbgenericop$ & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A} \grbewisemult{\grbgenericop} \grbm{B}$ \\
& on elements in the set intersection of structures of $\grbm{A}/\grbm{B}$ and $\grbv{u}$/$\grbv{v}$ & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{u} \grbewisemult{\grbgenericop} \grbv{v}$ \\
\midrule
\multirow{3}{*}{\tt extract} & extract submatrix from matrix $\grbm{A}$ using indices $\grba{i}$ and indices $\grba{j}$ & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbm{A}(\grba{i}, \grba{j})$ \\
%& extract the $\grbs{i}$th row vector from matrix $\grbm{A}$ & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{A}(\grbs{i}, :)$ \\
& extract the $\grbs{j}$th column vector from matrix $\grbm{A}$ & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbv{A}(:, \grbs{j})$ \\
& extract subvector from $\grbv{u}$ using indices $\grba{i}$ & $\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 $\mathit{f}$ with optional thunk $k$} & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbf{f}{\grbm{A}, \grbs{k}}$ \\
& & $\grbv{w} \grbmask{\grbv{m}} $ & $\grbaccumeq{} \grbf{f}{\grbv{u}, \grbs{k}}$ \\
\midrule
\multirow{2}{*}{\tt select} & \multirow{2}{*}{apply select operator $\mathit{f}$ with optional thunk $k$} & $\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} & row-wise 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 using operator $\grbgenericop$ & $\grbm{C} \grbmask{\grbm{M}} $ & $\grbaccumeq{} \grbkron{\grbm{A}, \grbgenericop, \grbm{B}}$ \\
\midrule
% </operations>
% <methods>
% \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 dup} & duplicate matrix & $\grbm{C} $ & $\grbassign \grbm{A}$ \\
& duplicate vector & $\grbv{w} $ & $\grbassign \grbv{u}$ \\
\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 arrays ($\grba{i}, \grba{j}$) and value arrays ($\grba{x}$)} & $ \left\{ \grba{i}, \grba{j}, \grba{x} \right\} $ & $\grbassign \grbm{A} $ \\
& & $ \left\{ \grba{i}, \grba{x} \right\} $ & $\grbassign \grbv{u} $ \\
\midrule
\multirow{2}{*}{\tt extractElement} & \multirow{2}{*}{extract element to scalar} & $\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
% </methods>
\end{tabular}
\caption{GraphBLAS operations and methods based on \cite{DBLP:journals/toms/Davis19,GraphBLASv13}.
\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.
% \todo{do we need everything, e.g. subassign, Kronecker?
% Tim Davis's comment: if we have space, I suggest we add all operations.
% I added kron (but please check my choice of notation).
% Maybe also add nvals, nrows, ... since we use those in the algorithms.
Operations can be modified via a descriptor;
matrices can be transposed ($\grbm{B}\grbt$),
the mask can be complemented ($\grbm{C}\grbmask{\neg \grbm{M}}$), and
the mask can be valued (shown above) or structural ($\grbm{C}\grbmask{\grbstr{\grbm{M}}}$).
A structural mask can also be complemented ($\grbm{C}\grbmask{\grbneg\grbstr{\grbm{M}}}$).
The result can be cleared (replaced) after using it as input to the mask/accumulator step ($\grbm{C}\grbmaskreplace{\grbm{M}}$).
Not all methods are listed (creating new operators, monoids, and semirings, clearing a matrix/vector, etc.).
% For the {\tt assign} operation, the dimensions of the masks are the same as the output's: $\grbdim{\grbm{M}} = \grbdim{\grbm{C}}$ and $\grbdim{\grbv{m}} = \grbdim{\grbv{w}}$.
% For the {\tt subassign} operation, the dimensions of the masks are the same as the submasks: $\grbnrows{\grbm{M}} = |\grba{i}|, \grbncols{\grbm{M}} = |\grba{j}|$ for matrices and $\grbdim{\grbv{m}} = |i|$ for vectors.
}
\label{tab:graphblas-notation}
\end{table*}
%\todo{consider using $\grbm{C}\grbmask{\grbval{\grbm{M}}}$ for valued}