## Unit1.3.2The dot product (inner product)

Given two vectors $x$ and $y$ of size $n$

\begin{equation*} x = \left( \begin{array}{c c c c} \chi_0 \\ \chi_1 \\ \vdots \\ \chi_{n-1} \end{array} \right) \quad {\rm and} \quad y = \left( \begin{array}{c c c c} \psi_0 \\ \psi_1 \\ \vdots \\ \psi_{n-1} \end{array} \right), \end{equation*}

their dot product is given by

\begin{equation*} x^T y = \chi_0 \psi_0 + \chi_1 \psi_1 + \cdots + \chi_{n-1} \psi_{n-1} = \sum_{i=0}^{n-1} \chi_i \psi_i. \end{equation*}

The notation $x^T y$ comes from the fact that the dot product also equals the result of multiplying $1 \times n$ matrix $x^T$ times $n \times 1$ matrix $y \text{.}$

\begin{equation*} \begin{array}{l} \left( \begin{array}{r} -1 \\ 2 \\ 3 \end{array} \right)^T \left( \begin{array}{r} 1 \\ 0 \\ -1 \end{array} \right) \\ ~~~=~~~~ \lt \mbox{View first vector as a } 3 \times 1 \mbox{ matrix and transpose it} \gt \\ \left( \begin{array}{r r r} -1 \amp 2 \amp 3 \end{array} \right) \left( \begin{array}{r} 1 \\ 0 \\ -1 \end{array} \right) \\ ~~~ = ~~~~ \lt \mbox{multiply } 1 \times 3 \mbox{ matrix times } 3 \times 1 \mbox{ matrix} \gt \\ (-1) \times (1) + (2) \times (0) + \times (3) \times (-1) \\ ~~~ = ~~~~ \\ -4. \end{array} \end{equation*}

Pseudo-code for computing $\gamma := x^T y + \gamma$ is given by

\begin{equation*} \begin{array}{l} {\bf for~} i := 0, \ldots , n-1 \\ ~~~ \gamma := \chi_{i} \psi_{i} + \gamma\\ {\bf end} \end{array} \end{equation*}

###### Homework1.3.2.1.

Consider

\begin{equation*} C = \begin{array}[t]{c} \underbrace{ \left(\begin{array}{rrr} 1 \amp -2 \amp 2\\ -1 \amp 1 \amp 3\\ -2 \amp 2 \amp -1 \end{array}\right) } \\ A \end{array} \begin{array}[t]{c} \underbrace{ \left(\begin{array}{rr} -2 \amp 1\\ 1 \amp 3\\ -1 \amp 2 \end{array}\right) } \\ B \end{array}. \end{equation*}

Compute $\gamma_{2,1} \text{.}$

Solution
\begin{equation*} \gamma_{2,1} = \left(\begin{array}{rrr} -2 \amp 2 \amp -1\end{array}\right) \left(\begin{array}{rr} 1\\ 3\\ 2 \end{array} \right) = (-2) \times (1) + (2) \times (3) + (-1) \times (2) = 2. \end{equation*}

The point we are trying to make here is that $\gamma_{2,1}$ is computed as the dot product of the third row of $A$ (the row indexed with $2$) with the last column of $B$ (the column indexed with $1$):

\begin{equation*} \gamma_{2,1} = \left(\begin{array}{rrr} -2 \\ 2 \\ -1\end{array}\right)^T \left(\begin{array}{rr} 1\\ 3\\ 2 \end{array} \right) = (-2) \times (1) + (2) \times (3) + (-1) \times (2) = 2. \end{equation*}

Importantly, if you think back about how matrices are stored in column-major order, marching through memory from one element to the next element in the last row of $A \text{,}$ as you access $\widetilde a_2^T \text{,}$ requires "striding" through memory.

A routine, coded in C, that computes $x^T y + \gamma$ where $x$ and $y$ are stored at location x with stride incx and location y with stride incy, respectively, and $\gamma$ is stored at location gamma, is given by

#define chi( i ) x[ (i)*incx ]   // map chi( i ) to array x
#define psi( i ) y[ (i)*incy ]   // map psi( i ) to array y

void Dots( int n, double *x, int incx, double *y, int incy, double *gamma )
{
for ( int i=0; i<n; i++ )
*gamma += chi( i ) * psi( i );
}


in Assignments/Week1/C/Dots.c. Here stride refers to the number of items in memory between the stored components of the vector. In particular, the stride when accessing a row of a matrix is ldA when the matrix is stored in column-major order with leading dimension ldA, as illustrated in Figure 1.2.2.

###### Homework1.3.2.2.

Consider the following double precision values stored in sequential memory starting at address A

\begin{equation*} \begin{array}{l c r} \amp \amp 3 \\ {\tt A} \amp \longrightarrow \amp -1 \\ \amp \amp 0 \\ \amp \amp 2 \\ \amp \amp 3 \\ \amp \amp -1 \\ \amp \amp 1 \\ \amp \amp 4 \\ \amp \amp -1 \\ \amp \amp 3 \\ \amp \amp 5 \end{array} \end{equation*}

and assume gamma initially contains the value 1. After executing

Dots( 3, &A, 4, &A, 1, &gamma )


What are the contents of variable gamma?

$5$

Solution

The first 3 indicates that the vectors are of size $3 \text{.}$ The &A, 4 identifies the vector starting at address &A with stride 4:

\begin{equation*} \begin{array}{l c r} \amp \amp -1 \\ {\tt A}\amp \longrightarrow \amp 0 \\ \amp \amp 2 \\ \amp \amp 3 \\ \amp \amp -1 \\ {\tt A[1+4]} \amp \longrightarrow \amp 1 \\ \amp \amp 4 \\ \amp \amp -1 \\ \amp \amp 3 \\ {\tt A[1+8]} \amp \longrightarrow \amp 5 \end{array} \end{equation*}

and the &A, 1 identifies the vector starting at address &A with stride 1:

\begin{equation*} \begin{array}{l c r} \amp \amp -1 \\ \amp \amp 0 \\ \amp \amp 2 \\ {\tt A} \amp \longrightarrow \amp 3 \\ {\tt A[3+1]} \amp \longrightarrow \amp -1 \\ {\tt A[3+2]} \amp \longrightarrow \amp 1 \\ \amp \amp 4 \\ \amp \amp -1 \\ \amp \amp 3 \\ \amp \amp 5 \end{array} \end{equation*}

Hence, upon completion, gamma contains

\begin{equation*} 1 + \left( \begin{array}{r} 0 \\ 1 \\ 5 \end{array} \right)^T \left( \begin{array}{r} 3 \\ -1 \\ 1 \end{array} \right) = 1 + (0) \times (3) + (1) \times (-1) + (5) \times (1) = 5. \end{equation*}