\documentclass{article}

% Packages required to support encoding
\usepackage{ucs}
\usepackage[utf8x]{inputenc}

% Packages required by code


% Packages always used
\usepackage{hyperref}
\usepackage{xspace}
\usepackage[usenames,dvipsnames]{color}
\hypersetup{colorlinks=true,urlcolor=blue}

\input{preamble.tex}


\begin{document} 
CS 59000-NMC, 6 September

Please answer the following questions. You may not use any outside references or technology. Justify and explain all answers. This quiz is for my own evaluation, so that I can provide better instruction in the course.

\hypertarget{question_1}{}\subsection*{{Question}}\label{question_1}

Let $\mA$ be a binary matrix. Suppose this matrix is composed of mostly ones and that the zeros are stored with a compressed-sparse row data structure. Write down an efficient algorithm to compute $\vy = \mA \vx$ give the compressed sparse row data structure for $\mA$'{}s zeros in the arrays {\colorbox[rgb]{1.00,0.93,1.00}{\tt pointer}} and {\colorbox[rgb]{1.00,0.93,1.00}{\tt columns}}.

\hypertarget{solution_2}{}\subsection*{{Solution}}\label{solution_2}

The key insight is that the zero pattern tells us what to \emph{exclude} from the matrix-vector product, rather than what to include. Consider that if $\mA$ was composed entirely of ones, then:

\begin{displaymath}
[\mA \vx]_i = \sum x_i
\end{displaymath}
Consequently, if we set $\alpha = \sum x_i$, then

\begin{displaymath}
\mA \vx = \alpha \ve
\end{displaymath}
where \$$\ve$\$ is the vector of all ones.

Once we have this property, let $\mO$ be the matrix of all ones. Now consider $\mA$ from the problem

\begin{displaymath}
\mA = \mO - \mB$$ where $\mB$ is a *sparse matrix*with the *zero pattern* from $\mA$ and each entry is a one.

Consequently, we can just compute 
$$\mA \vx = \alpha \ve - \mB \vx
\end{displaymath}
where $\mB \vx$ is just a standard matrix-vector product.

\begin{verbatim}function sparse_zero_matvec(n,pointers,columns,x)
""" Compute a mat-vec with a mostly one matrix, with a sparse zero pattern.

This function will multiply a binary matrix $A$, which is all
ones except for a sparse pattern of zeros, by a vector $x$.

Here the arrays are zero indexed.

@param n the dimension of the matrix
@param pointers the array of pointers for a CSR pattern of zeros in the matrix
@param columns the array of columns for the CSR pattern of zeros
@param an array with the values of x
@return an array such 
"""

alpha = 0
for xi in x: # assumes x implements an interable interface
  alpha += xi

y = [alpha for _ in xrange(n)] # initialize y
for i in xrange(n):
  change = 0
  for nzi in xrange(pointers[i],pointers[i+1]):
    col = columns[nzi]
    change += x[nzi]
  
  y[i] -= change # adjust the value

return y\end{verbatim}

\end{document}
