Inner product vs. vector triad form This program involves the matrix-vector computational primitive $y \leftarrow Ax$ where $x,y\in\mathbb{R}^n$ and $A\in \mathbb{R}^{n\times n}$. A is taken to be dense and banded in the two parts of the problem. Recall, there are many ways to implement the primitive. Two standard approaches are: 
$$\eta_i = e_i^{T}y = e_i^{T}Ax = \tilde{a}_i^{T}x, 1\leq i\leq n \ \ \text{inner product form}$$
$$y = \sum_{1}^{n}(Ae_i)(e_i^{T}x) = \sum_{1}^{n}a_i\xi_i, \ \ \text{vector triad form}$$
Note: $e^T$ is the standard basis vector.
I know that when implemented these two approaches will produce the same result but I do not understand what the two forms are doing. I believe the inner product form is just multiplying every value in each row of $A$ to the values in $x$ and summing. Any suggestions are greatly appreciated, I will be programming these in C++.
 A: There are many, many different ways to do matrix vector multiplication or the more general matrix matrix multiplication. Mathematically, they return the same result, but their run times differs significantly depending on the size and type of the relevant matrices as well as details of the underlying architeture. The goal is acheive an implementation which minimizes the runtime by making the best possible use of the available resources. 
You mention two different ways of computing the matrix vector product $y = Ax$.  Let us assume that matrix is $n$ by $n$ for the sake of simplicity. Let $r_i$ denote the $i$th row vector of $A$ and let $c_j$ denote the $j$ th column vector. Then
\begin{equation}
y = Ax = (r_1 \cdot x, r_2 \cdot x, \dotsc, r_n \cdot x)^T = \sum_{j=1}^n c_j x_j.
\end{equation}
The first method access the matrix $A$by rows, whereas the second method access the matrix by columns. The performance of the method depends on how the matrix is stored. In Fortran matrices are stored by columns by default. This is called column major format. This format favors the second method because it ensures that the matrix is accessed with stride $1$. This reduces the number of cache misses and improves performance. If the first method is used for a matrix in column major format, then the matrix would be accessed with stride $n$. This would dramatically increase the number of cache misses and significantly reduce the rate at which flops can be executed. Many C programmers prefer to store their matrices by rows, using an array of pointers to point to the beginning of each row. Here the situation is reversed. One should at all times use an algorithm which is compatible with the memory layout.
Banded matrices are normally stored in a special format, imaginatively called banded format. This is implemented in LAPACK and described here http://www.netlib.org/lapack/lug/node124.html. This format compresses the matrix into a wide rectangle which allow the columns to be accessed with stride 1. The corresponding matrix vector multiplication routine is called DGBMV (Double precision General Band Matrix Vector multiplication) and is documented here http://www.netlib.org/lapack/explore-html/d2/d3f/dgbmv_8f_source.html. In reality, the routine is nothing but a special case of the second method which takes the unique sparsity patterns of the matrix into account.
