Matrix-Vector Multiplication

Matrix-Vector Multiplication

Matrix multiplication by a vector gives another vector. Let us consider the simple cast first, where the matrix is square with dimensions NxN and the vector is also of size N. The matrix has N rows and N columns, and the input vector has N elements. The resulting output vector will also have N elements. Conceptually, in pseudocode:

    MAT[N][N] * VIN[N] -> VOUT[N]

It's not immediately obvious, or at least, I don't remember my High School Math teacher mentioning it, but matrix-vector multiplication is a bunch of vector dot product computations. We need to do a vector dot product for each of the elements of the output vector. Each element is a dot product of a matrix row times the input vector. Note that the dimensions match for a dot product, with N matrix rows and N elements in the input vector.

Complexity of Matrix-Vector Multiplication. The algorithmic complexity of matrix-vector multiplication is quadratic in N, whereas matrix-matrix multiplication is cubic in N. The basic matrix-vector multiplication scans N rows of the matrix, with each row element performing a computation against each of the N elements of the vector, giving two nested loops with an overall O(N^2) cost.

Memory layout: One important point for the efficiency of matrix-vector multiplication is that the default memory layout has contiguous addresses for both the matrix row and the vector. Obviously, a vector is just a sequence of memory with all the elements in series. Not so obviously, a row of a matrix, when stored as a C++ two-dimensional array, is also a contiguous set of data (i.e. a matrix row is like a vector). Hence, the dot product multiplication of a matrix row and the input vector is simply scanning forward along contiguous addresses for both of its inputs, which makes it easy to vectorize.

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++