\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}

When the matrix $\mA$ is upper-triangular, then there are no updated values of the solution that are affected by the entries of the matrix, and the two iterations will be the same.

\textbf{Unexpected, and correct, but slightly trivial answer} When you start the two with the correct solution!

\textbf{Reason you shouldn'{}t solve the system them} When $\mA$ is upper-triangular, then we can employ a technique called \emph{back-substitution} to solve the system without an iterative method.

\hypertarget{backsubstitution_3}{}\subsection*{{Back-substitution}}\label{backsubstitution_3}

Let $\mA$ be upper triangular:

\begin{displaymath}
A_{i,j} = 0 \text{ when } i > j
\end{displaymath}
e.g.

\begin{displaymath}
\mA = \bmat{A_{1,1} & A_{1,2} & A_{1,3} \\ 0 & A_{2,2} & A_{2,3} \\ 0 & 0 & A_{3,3} }.
\end{displaymath}
Note that for $\mA \vx = \vb$ that

\begin{displaymath}
x_n = b_n / A_{n,n}.
\end{displaymath}
We can use this value to find $x_{n-1}$ now:

\begin{displaymath}
A_{n-1,n-1} x_{n-1} + A_{n-1,n} x_n =  b_{n-1}
\end{displaymath}
so

\begin{displaymath}
x_{n-1} = A_{n-1,n-1}^{-1} ( b_{n-1} - A_{n-1,n} x_n ).
\end{displaymath}
Just continue in this manner through the rest of the matrix:

\begin{displaymath}
x_i = A_{i,i}^{-1} ( b_{i} - \sum_{j > i} A_{i,j} x_j ).
\end{displaymath}
For this algorithm, note that you have to proceed \emph{backwards} through the rows of the matrix.


\end{document}
