
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The mask, accumulator, and replace option} %%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:maskaccum}

After a GraphBLAS operation computes a result ${\bf T}$, (for example, ${\bf
T=AB}$ for \verb'GrB_mxm'), the results are assigned to an output matrix ${\bf
C}$ via the mask/ accumulator phase, written as ${\bf C \langle M \rangle = C
\odot T}$.  This phase is affected by the \verb'GrB_REPLACE' option in the
descriptor, the presence of an optional binary accumulator operator ($\odot$),
the presence of the optional mask matrix ${\bf M}$, and the status of the mask
descriptor.  The interplay of these options is summarized in
Table~\ref{tab:maskaccum}.

The mask ${\bf M}$ may be present, or not.  It may be structural or valued, and
it may be complemented, or not.  These options may be combined, for a total of
8 cases, although the structural/valued option as no effect if ${\bf M}$ is not
present.  If ${\bf M}$ is not present and not complemented, then $m_{ij}$ is
implicitly true.  If not present yet complemented, then all $m_{ij}$ entries are
implicitly zero; in this case, ${\bf T}$ need not be computed at all.  Either
${\bf C}$ is not modified, or all its entries are cleared if the replace option
is enabled.  If ${\bf M}$ is present, and the structural option is used, then
$m_{ij}$ is treated as true if it is an entry in the matrix (its value is
ignored).  Otherwise, the value of $m_{ij}$ is used.  In both cases, entries
not present are implicitly zero.  These values are negated if the mask is
complemented.  All of these various cases are combined to give a single
effective value of the mask at position ${ij}$.

The combination of all these options are presented in the
Table~\ref{tab:maskaccum}.  The first column is the \verb'GrB_REPLACE' option.
The second column lists whether or not the accumulator operator is present.
The third column lists whether or not $c_{ij}$ exists on input to the
mask/accumulator phase (a dash means that it does not exist).  The fourth
column lists whether or not the entry $t_{ij}$ is present in the result matrix
${\bf T}$.  The mask column is the final effective value of $m_{ij}$, after
accounting for the presence of ${\bf M}$ and the mask options.  Finally, the
last column states the result of the mask/accum step; if no action is listed in
this column, then $c_{ij}$ is not modified.

Several important observations can be made from this table.  First,
if no mask is present (and the mask-complement descriptor option is not used),
then only the first half of the table is used.  In this case, the \verb'GrB_REPLACE'
option has no effect.  The entire matrix ${\bf C}$ is modified.

Consider the cases when $c_{ij}$ is present but $t_{ij}$ is not, and there is no
mask or the effective value of the mask is true for this ${ij}$ position.  With
no accumulator operator, $c_{ij}$ is deleted.  If the accumulator operator is
present and the replace option is not used, $c_{ij}$ remains unchanged.

\begin{table}
{\small
\begin{tabular}{lllll|l}
\hline
repl & accum & ${\bf C}$ & ${\bf T}$ & mask & action taken by ${\bf C \langle M \rangle = C \odot T}$ \\
\hline
    -  &-   & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, update \\
    -  &-   &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
    -  &-   & $c_{ij}$ &  -        & 1    &  delete $c_{ij}$ because $t_{ij}$ not present \\
    -  &-   &  -       &  -        & 1    &   \\
    -  &-   & $c_{ij}$ & $t_{ij}$  & 0    &   \\
    -  &-   &  -       & $t_{ij}$  & 0    &   \\
    -  &-   & $c_{ij}$ &  -        & 0    &   \\
    -  &-   &  -       &  -        & 0    &   \\
\hline
    yes&-   & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, update \\
    yes&-   &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
    yes&-   & $c_{ij}$ &  -        & 1    &  delete $c_{ij}$ because $t_{ij}$ not present \\
    yes&-   &  -       &  -        & 1    &   \\
    yes&-   & $c_{ij}$ & $t_{ij}$  & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
    yes&-   &  -       & $t_{ij}$  & 0    &   \\
    yes&-   & $c_{ij}$ &  -        & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
    yes&-   &  -       &  -        & 0    &   \\
\hline
    -  &yes & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
    -  &yes &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
    -  &yes & $c_{ij}$ &  -        & 1    &   \\
    -  &yes &  -       &  -        & 1    &   \\
    -  &yes & $c_{ij}$ & $t_{ij}$  & 0    &   \\
    -  &yes &  -       & $t_{ij}$  & 0    &   \\
    -  &yes & $c_{ij}$ &  -        & 0    &   \\
    -  &yes &  -       &  -        & 0    &   \\
\hline
    yes&yes & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
    yes&yes &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
    yes&yes & $c_{ij}$ &  -        & 1    &   \\
    yes&yes &  -       &  -        & 1    &   \\
    yes&yes & $c_{ij}$ & $t_{ij}$  & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
    yes&yes &  -       & $t_{ij}$  & 0    &   \\
    yes&yes & $c_{ij}$ &  -        & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
    yes&yes &  -       &  -        & 0    &   \\
\hline
\end{tabular}
}
\caption{Results of the mask/accumulator phase. \label{tab:maskaccum}}
\end{table}

When there is no mask and the mask \verb'GrB_COMP' option is not selected, the
table simplifies (Table~\ref{tab:maskaccum_nomask}).  The \verb'GrB_REPLACE'
option no longer has any effect.  The \verb'GrB_SECOND_T' binary operator when
used as the accumulator unifies the first cases, shown in
Table~\ref{tab:maskaccum_nomask_2nd}.  The only difference now is the behavior
when $c_{ij}$ is present but $t_{ij}$ is not.  Finally, the effect of
\verb'GrB_FIRST_T' as the accumulator is shown in
Table~\ref{tab:maskaccum_nomask_1st}.

\begin{table}[h]
\begin{center}
{\small
\begin{tabular}{lll|l}
\hline
       accum & ${\bf C}$ & ${\bf T}$        & action taken by ${\bf C = C \odot T}$ \\
\hline
        -   & $c_{ij}$ & $t_{ij}$         &  $c_{ij} = t_{ij}$, update \\
        -   &  -       & $t_{ij}$         &  $c_{ij} = t_{ij}$, insert \\
        -   & $c_{ij}$ &  -               &  delete $c_{ij}$ because $t_{ij}$ not present \\
        -   &  -       &  -               &   \\
\hline
        yes & $c_{ij}$ & $t_{ij}$         &  $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
        yes &  -       & $t_{ij}$         &  $c_{ij} = t_{ij}$, insert \\
        yes & $c_{ij}$ &  -               &   \\
        yes &  -       &  -               &   \\
\hline
\end{tabular}
}
\caption{When no mask is present (and not complemented).
\label{tab:maskaccum_nomask}}
\end{center}
\end{table}

\begin{table}[h]
\begin{center}
{\small
\begin{tabular}{lll|l}
\hline
       accum & ${\bf C}$ & ${\bf T}$        & action taken by ${\bf C = C \odot T}$ \\
\hline
        yes & $c_{ij}$ & $t_{ij}$         &  $c_{ij} = t_{ij}$, apply \verb'GrB_SECOND' accumulator \\
        yes &  -       & $t_{ij}$         &  $c_{ij} = t_{ij}$, insert \\
        yes & $c_{ij}$ &  -               &   \\
        yes &  -       &  -               &   \\
\hline
\end{tabular}
}
\caption{No mask, with the SECOND operator as the accumulator.
\label{tab:maskaccum_nomask_2nd}}
\end{center}
\end{table}

\begin{table}[h]
\begin{center}
{\small
\begin{tabular}{lll|l}
\hline
       accum & ${\bf C}$ & ${\bf T}$        & action taken by ${\bf C = C \odot T}$ \\
\hline
        yes & $c_{ij}$ & $t_{ij}$         &  \\
        yes &  -       & $t_{ij}$         &  $c_{ij} = t_{ij}$, insert \\
        yes & $c_{ij}$ &  -               &   \\
        yes &  -       &  -               &   \\
\hline
\end{tabular}
}
\caption{No Mask, with the FIRST operator as the accumulator.
\label{tab:maskaccum_nomask_1st}}
\end{center}
\end{table}

\newpage
If C and M are aliased (and C and A are not aliased) and the mask is structural
and not complemented, then only a subset of the actions in the table are taken,
as shown in Table~\ref{tab:hack1}.  The results are the same regardless of
whether replace is true or false.  

\begin{table}
{\small
\begin{tabular}{lllll|l}
\hline
repl & accum & ${\bf C}$ & ${\bf T}$ & mask & action taken by ${\bf C \langle C,struct \rangle = C \odot T}$ \\
\hline
    -  &-   & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, update \\
%   -  &-   &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
    -  &-   & $c_{ij}$ &  -        & 1    &  delete $c_{ij}$ because $t_{ij}$ not present \\
%   -  &-   &  -       &  -        & 1    &   \\
%   -  &-   & $c_{ij}$ & $t_{ij}$  & 0    &   \\
    -  &-   &  -       & $t_{ij}$  & 0    &   \\
%   -  &-   & $c_{ij}$ &  -        & 0    &   \\
    -  &-   &  -       &  -        & 0    &   \\
\hline
  % yes&-   & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, update \\
% % yes&-   &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
  % yes&-   & $c_{ij}$ &  -        & 1    &  delete $c_{ij}$ because $t_{ij}$ not present \\
% % yes&-   &  -       &  -        & 1    &   \\
% % yes&-   & $c_{ij}$ & $t_{ij}$  & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
  % yes&-   &  -       & $t_{ij}$  & 0    &   \\
% % yes&-   & $c_{ij}$ &  -        & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
  % yes&-   &  -       &  -        & 0    &   \\
\hline
    -  &yes & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
%   -  &yes &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
    -  &yes & $c_{ij}$ &  -        & 1    &   \\
%   -  &yes &  -       &  -        & 1    &   \\
%   -  &yes & $c_{ij}$ & $t_{ij}$  & 0    &   \\
    -  &yes &  -       & $t_{ij}$  & 0    &   \\
%   -  &yes & $c_{ij}$ &  -        & 0    &   \\
    -  &yes &  -       &  -        & 0    &   \\
\hline
  % yes&yes & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
% % yes&yes &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
  % yes&yes & $c_{ij}$ &  -        & 1    &   \\
% % yes&yes &  -       &  -        & 1    &   \\
% % yes&yes & $c_{ij}$ & $t_{ij}$  & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
  % yes&yes &  -       & $t_{ij}$  & 0    &   \\
% % yes&yes & $c_{ij}$ &  -        & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
  % yes&yes &  -       &  -        & 0    &   \\
\hline
\end{tabular}
}
\caption{Results of the mask/accumulator phase (C==M aliased, mask structural and
not complemented; replace is anything). \label{tab:hack1} }
\end{table}

\newpage
If M and T are aliased with each other (but not with C), 
the mask is structural and NOT complemented, then
the table simplies as given in \ref{tab:hack2}.
% This table does not look like a special case that is worth exploiting in general,
% but the replace=false case looks interesting.

\begin{table}
{\small
\begin{tabular}{lllll|l}
\hline
repl & accum & ${\bf C}$ & ${\bf T}$ & mask & action taken by ${\bf C \langle T, struct \rangle = C \odot T}$ \\
\hline
    -  &-   & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, update \\
    -  &-   &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
%   -  &-   & $c_{ij}$ &  -        & 1    &  delete $c_{ij}$ because $t_{ij}$ not present \\
%   -  &-   &  -       &  -        & 1    &   \\
%   -  &-   & $c_{ij}$ & $t_{ij}$  & 0    &   \\
%   -  &-   &  -       & $t_{ij}$  & 0    &   \\
    -  &-   & $c_{ij}$ &  -        & 0    &   \\
    -  &-   &  -       &  -        & 0    &   \\
\hline
    yes&-   & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, update \\
    yes&-   &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
%   yes&-   & $c_{ij}$ &  -        & 1    &  delete $c_{ij}$ because $t_{ij}$ not present \\
%   yes&-   &  -       &  -        & 1    &   \\
%   yes&-   & $c_{ij}$ & $t_{ij}$  & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
%   yes&-   &  -       & $t_{ij}$  & 0    &   \\
    yes&-   & $c_{ij}$ &  -        & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
    yes&-   &  -       &  -        & 0    &   \\
\hline
    -  &yes & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
    -  &yes &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
%   -  &yes & $c_{ij}$ &  -        & 1    &   \\
%   -  &yes &  -       &  -        & 1    &   \\
%   -  &yes & $c_{ij}$ & $t_{ij}$  & 0    &   \\
%   -  &yes &  -       & $t_{ij}$  & 0    &   \\
    -  &yes & $c_{ij}$ &  -        & 0    &   \\
    -  &yes &  -       &  -        & 0    &   \\
\hline
    yes&yes & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
    yes&yes &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
%   yes&yes & $c_{ij}$ &  -        & 1    &   \\
%   yes&yes &  -       &  -        & 1    &   \\
%   yes&yes & $c_{ij}$ & $t_{ij}$  & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
%   yes&yes &  -       & $t_{ij}$  & 0    &   \\
    yes&yes & $c_{ij}$ &  -        & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
    yes&yes &  -       &  -        & 0    &   \\
\hline
\end{tabular}
}
\caption{Results of the mask/accumulator phase (M==T aliased, mask structural and
not complemented). \label{tab:hack2}}
\end{table}

\newpage
If M and T are aliased with each other (but not with C), 
the mask is structural AND complemented, then
the table simplies as given in \ref{tab:hack3}.
Note that the accumulator is never actually applied, even though
this table would require it to be present.
This table looks interesting, because in the case where replace is true
and accum is present, the structure of T tells where zombies should be inserted
into C (and there are no other changes to make).

\begin{table}
{\small
\begin{tabular}{lllll|l}
\hline
repl & accum & ${\bf C}$ & ${\bf T}$ & mask & action taken by
${\bf C \langle \lnot T, struct \rangle = C \odot T}$ \\
\hline
%   -  &-   & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, update \\
%   -  &-   &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
    -  &-   & $c_{ij}$ &  -        & 1    &  delete $c_{ij}$ because $t_{ij}$ not present \\
    -  &-   &  -       &  -        & 1    &   \\
    -  &-   & $c_{ij}$ & $t_{ij}$  & 0    &   \\
    -  &-   &  -       & $t_{ij}$  & 0    &   \\
%   -  &-   & $c_{ij}$ &  -        & 0    &   \\
%   -  &-   &  -       &  -        & 0    &   \\
\hline
%   yes&-   & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, update \\
%   yes&-   &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
    yes&-   & $c_{ij}$ &  -        & 1    &  delete $c_{ij}$ because $t_{ij}$ not present \\
    yes&-   &  -       &  -        & 1    &   \\
    yes&-   & $c_{ij}$ & $t_{ij}$  & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
    yes&-   &  -       & $t_{ij}$  & 0    &   \\
%   yes&-   & $c_{ij}$ &  -        & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
%   yes&-   &  -       &  -        & 0    &   \\
\hline
%   -  &yes & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
%   -  &yes &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
    -  &yes & $c_{ij}$ &  -        & 1    &   \\
    -  &yes &  -       &  -        & 1    &   \\
    -  &yes & $c_{ij}$ & $t_{ij}$  & 0    &   \\
    -  &yes &  -       & $t_{ij}$  & 0    &   \\
%   -  &yes & $c_{ij}$ &  -        & 0    &   \\
%   -  &yes &  -       &  -        & 0    &   \\
\hline
%   yes&yes & $c_{ij}$ & $t_{ij}$  & 1    &  $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
%   yes&yes &  -       & $t_{ij}$  & 1    &  $c_{ij} = t_{ij}$, insert \\
    yes&yes & $c_{ij}$ &  -        & 1    &   \\
    yes&yes &  -       &  -        & 1    &   \\
    yes&yes & $c_{ij}$ & $t_{ij}$  & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
    yes&yes &  -       & $t_{ij}$  & 0    &   \\
%   yes&yes & $c_{ij}$ &  -        & 0    &  delete $c_{ij}$  (because of \verb'GrB_REPLACE') \\
%   yes&yes &  -       &  -        & 0    &   \\
\hline
\end{tabular}
}
\caption{Results of the mask/accumulator phase (M==T aliased, mask structural and
complemented). \label{tab:hack3}}
\end{table}

