Skip to main content

Unit 1.3.2 The 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*}

Homework 1.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.

Homework 1.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[0]} \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[1], 4, &A[3], 1, &gamma )

What are the contents of variable gamma?

Answer

\(5 \)

Solution

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

\begin{equation*} \begin{array}{l c r} \amp \amp -1 \\ {\tt A[1]}\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[3], 1 identifies the vector starting at address &A[3] with stride 1:

\begin{equation*} \begin{array}{l c r} \amp \amp -1 \\ \amp \amp 0 \\ \amp \amp 2 \\ {\tt A[3]} \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*}