Chapter 1 - Matrix Multiplication_Matlab.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Chapter-1-Matrix-Multiplication\" data-toc-modified-id=\"Chapter-1-Matrix-Multiplication-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Chapter 1 Matrix Multiplication</a></div><div class=\"lev2 toc-item\"><a href=\"#Basic-Algorithms-and-Notation\" data-toc-modified-id=\"Basic-Algorithms-and-Notation-11\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Basic Algorithms and Notation</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1.1-(Dot-Product)\" data-toc-modified-id=\"Algorithm-1.1.1-(Dot-Product)-111\"><span class=\"toc-item-num\">1.1.1&nbsp;&nbsp;</span>Algorithm 1.1.1 (Dot Product)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1.2-(Saxpy)\" data-toc-modified-id=\"Algorithm-1.1.2-(Saxpy)-112\"><span class=\"toc-item-num\">1.1.2&nbsp;&nbsp;</span>Algorithm 1.1.2 (Saxpy)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1.3-(MV:-Row-Oriented-Gaxpy)\" data-toc-modified-id=\"Algorithm-1.1.3-(MV:-Row-Oriented-Gaxpy)-113\"><span class=\"toc-item-num\">1.1.3&nbsp;&nbsp;</span>Algorithm 1.1.3 (MV: Row-Oriented Gaxpy)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1.3'-(MV:-Row-Oriented-Gaxpy_Dot)\" data-toc-modified-id=\"Algorithm-1.1.3'-(MV:-Row-Oriented-Gaxpy_Dot)-114\"><span class=\"toc-item-num\">1.1.4&nbsp;&nbsp;</span>Algorithm 1.1.3' (MV: Row-Oriented Gaxpy_Dot)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1.4-(MV:-Column-Oriented-Gaxpy)\" data-toc-modified-id=\"Algorithm-1.1.4-(MV:-Column-Oriented-Gaxpy)-115\"><span class=\"toc-item-num\">1.1.5&nbsp;&nbsp;</span>Algorithm 1.1.4 (MV: Column-Oriented Gaxpy)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1.4'-(MV:-Column-Oriented-Gaxpy_axpy)\" data-toc-modified-id=\"Algorithm-1.1.4'-(MV:-Column-Oriented-Gaxpy_axpy)-116\"><span class=\"toc-item-num\">1.1.6&nbsp;&nbsp;</span>Algorithm 1.1.4' (MV: Column-Oriented Gaxpy_axpy)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1.5-(MM:-ijk-Matrix-Multiplication)\" data-toc-modified-id=\"Algorithm-1.1.5-(MM:-ijk-Matrix-Multiplication)-117\"><span class=\"toc-item-num\">1.1.7&nbsp;&nbsp;</span>Algorithm 1.1.5 (MM: ijk Matrix Multiplication)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1.6-(MM:-Double-Loop-Around-Dot-Product)\" data-toc-modified-id=\"Algorithm-1.1.6-(MM:-Double-Loop-Around-Dot-Product)-118\"><span class=\"toc-item-num\">1.1.8&nbsp;&nbsp;</span>Algorithm 1.1.6 (MM: Double Loop Around Dot Product)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1.6'-(MM:-Single-Loop-Around-Row-Vector-Times-Matrix-Product)\" data-toc-modified-id=\"Algorithm-1.1.6'-(MM:-Single-Loop-Around-Row-Vector-Times-Matrix-Product)-119\"><span class=\"toc-item-num\">1.1.9&nbsp;&nbsp;</span>Algorithm 1.1.6' (MM: Single Loop Around Row Vector Times Matrix Product)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1.7-(MM:-Double-Loop-Saxpy-Matrix-Multiplication)\" data-toc-modified-id=\"Algorithm-1.1.7-(MM:-Double-Loop-Saxpy-Matrix-Multiplication)-1110\"><span class=\"toc-item-num\">1.1.10&nbsp;&nbsp;</span>Algorithm 1.1.7 (MM: Double Loop Saxpy Matrix Multiplication)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1.7'-(MM:-Single-Loop:-Saxpy-Matrix-Multiplication)\" data-toc-modified-id=\"Algorithm-1.1.7'-(MM:-Single-Loop:-Saxpy-Matrix-Multiplication)-1111\"><span class=\"toc-item-num\">1.1.11&nbsp;&nbsp;</span>Algorithm 1.1.7' (MM: Single Loop: Saxpy Matrix Multiplication)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.1-.8-(MM:-Outer-Product-Matrix-Multiplication)\" data-toc-modified-id=\"Algorithm-1.1-.8-(MM:-Outer-Product-Matrix-Multiplication)-1112\"><span class=\"toc-item-num\">1.1.12&nbsp;&nbsp;</span>Algorithm 1.1 .8 (MM: Outer Product Matrix Multiplication)</a></div><div class=\"lev2 toc-item\"><a href=\"#Structure-and-Efficiency\" data-toc-modified-id=\"Structure-and-Efficiency-12\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Structure and Efficiency</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.2.1-(Triangular-Matrix-Multiplication)\" data-toc-modified-id=\"Algorithm-1.2.1-(Triangular-Matrix-Multiplication)-121\"><span class=\"toc-item-num\">1.2.1&nbsp;&nbsp;</span>Algorithm 1.2.1 (Triangular Matrix Multiplication)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.2.1'-(Triangular-Matrix-Multiplication:-Double-Loop)\" data-toc-modified-id=\"Algorithm-1.2.1'-(Triangular-Matrix-Multiplication:-Double-Loop)-122\"><span class=\"toc-item-num\">1.2.2&nbsp;&nbsp;</span>Algorithm 1.2.1' (Triangular Matrix Multiplication: Double Loop)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.2.2-(Band-Storage-Gaxpy)\" data-toc-modified-id=\"Algorithm-1.2.2-(Band-Storage-Gaxpy)-123\"><span class=\"toc-item-num\">1.2.3&nbsp;&nbsp;</span>Algorithm 1.2.2 (Band Storage Gaxpy)</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.2.3-(Symmetric-Storage-Gaxpy)\" data-toc-modified-id=\"Algorithm-1.2.3-(Symmetric-Storage-Gaxpy)-124\"><span class=\"toc-item-num\">1.2.4&nbsp;&nbsp;</span>Algorithm 1.2.3 (Symmetric Storage Gaxpy)</a></div><div class=\"lev2 toc-item\"><a href=\"#Block-Matrices-and-Algorithms\" data-toc-modified-id=\"Block-Matrices-and-Algorithms-13\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Block Matrices and Algorithms</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.3.1-(Strassen-Matrix-Multiplication)\" data-toc-modified-id=\"Algorithm-1.3.1-(Strassen-Matrix-Multiplication)-131\"><span class=\"toc-item-num\">1.3.1&nbsp;&nbsp;</span>Algorithm 1.3.1 (Strassen Matrix Multiplication)</a></div><div class=\"lev2 toc-item\"><a href=\"#Fast-Matrix-Vector-Products\" data-toc-modified-id=\"Fast-Matrix-Vector-Products-14\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Fast Matrix-Vector Products</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.4.1--Discrete-Fourier-Transfrm\" data-toc-modified-id=\"Algorithm-1.4.1--Discrete-Fourier-Transfrm-141\"><span class=\"toc-item-num\">1.4.1&nbsp;&nbsp;</span>Algorithm 1.4.1  Discrete Fourier Transfrm</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1.4.2-DST\" data-toc-modified-id=\"Algorithm-1.4.2-DST-142\"><span class=\"toc-item-num\">1.4.2&nbsp;&nbsp;</span>Algorithm 1.4.2 DST</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1-.4.3-DCT\" data-toc-modified-id=\"Algorithm-1-.4.3-DCT-143\"><span class=\"toc-item-num\">1.4.3&nbsp;&nbsp;</span>Algorithm 1 .4.3 DCT</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithm-1-.4.4-(Haar-Wavelet-Transfrm)\" data-toc-modified-id=\"Algorithm-1-.4.4-(Haar-Wavelet-Transfrm)-144\"><span class=\"toc-item-num\">1.4.4&nbsp;&nbsp;</span>Algorithm 1 .4.4 (Haar Wavelet Transfrm)</a></div><div class=\"lev2 toc-item\"><a href=\"#Vectorization-and-Locality\" data-toc-modified-id=\"Vectorization-and-Locality-15\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Vectorization and Locality</a></div><div class=\"lev2 toc-item\"><a href=\"#Parallel-Matrix-Multiplication\" data-toc-modified-id=\"Parallel-Matrix-Multiplication-16\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Parallel Matrix Multiplication</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 1 Matrix Multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic Algorithms and Notation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.1.1 (Dot Product)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:22.899121Z",
     "start_time": "2018-02-09T14:47:22.833208Z"
    }
   },
   "outputs": [],
   "source": [
    "function c = Dot(x, y)\n",
    "    c = 0;\n",
    "    n = size(x)(1);\n",
    "    for i = 1: n\n",
    "        c = c + x(i) * y(i);\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:22.964118Z",
     "start_time": "2018-02-09T14:47:22.901121Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n",
      "ans = 1\n",
      "ans = 1\n",
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "x = [1 2 3]'; y = [1 -1 2]'; \n",
    "\n",
    "isequal(Dot(x, y),x' * y)\n",
    "isequal(Dot(x, y),dot(x,y))\n",
    "isequal(Dot(x, y),sum(conj(x) .* y ))\n",
    "isequal(Dot(x, y),sum(x .* y ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.1.2 (Saxpy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:23.023123Z",
     "start_time": "2018-02-09T14:47:22.966128Z"
    }
   },
   "outputs": [],
   "source": [
    "function y = Saxpy(a, x)\n",
    "    n = size(x)(1);\n",
    "    y = zeros(n,1);\n",
    "    for i = 1: n\n",
    "        y(i) = y(i) + a * x(i);\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:23.054121Z",
     "start_time": "2018-02-09T14:47:23.026125Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "a = 4; x = [1 2 3]';\n",
    "\n",
    "isequal(Saxpy(a, x), a * x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.1.3 (MV: Row-Oriented Gaxpy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:23.122123Z",
     "start_time": "2018-02-09T14:47:23.057123Z"
    }
   },
   "outputs": [],
   "source": [
    "function y = Gaxpy_row(A, x)\n",
    "    [m, n] = size(A);\n",
    "    y = zeros(m,1);\n",
    "    \n",
    "    for i = 1:m\n",
    "        for j = 1:n\n",
    "            y(i) = y(i) + A(i,j) * x(j);\n",
    "        end\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:23.153119Z",
     "start_time": "2018-02-09T14:47:23.125125Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "x = [1 2 3]'; A = randi(4,3);\n",
    "\n",
    "isequal(Gaxpy_row(A, x ), A * x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T00:32:24.827137Z",
     "start_time": "2018-02-09T00:32:24.801087Z"
    }
   },
   "source": [
    "### Algorithm 1.1.3' (MV: Row-Oriented Gaxpy_Dot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:23.208126Z",
     "start_time": "2018-02-09T14:47:23.155123Z"
    }
   },
   "outputs": [],
   "source": [
    "function y = Gaxpy_row2(A, x)\n",
    "    [m, n] = size(A);\n",
    "    y = zeros(m,1);\n",
    "    \n",
    "    for i = 1:m\n",
    "        y(i) = y(i) + A(i,:) * x;\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:23.240117Z",
     "start_time": "2018-02-09T14:47:23.211121Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "x = [1 2 3]'; A = randi(4,3); \n",
    "\n",
    "isequal(Gaxpy_row2(A, x ), A * x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.1.4 (MV: Column-Oriented Gaxpy) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:23.308130Z",
     "start_time": "2018-02-09T14:47:23.242123Z"
    }
   },
   "outputs": [],
   "source": [
    "function y = Gaxpy_col(A, x)\n",
    "    [m, n] = size(A);\n",
    "    y = zeros(m,1);\n",
    "    \n",
    "    for j = 1:n\n",
    "        for i = 1:m\n",
    "            y(i) = y(i) + A(i,j) * x(j);\n",
    "        end\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:23.343121Z",
     "start_time": "2018-02-09T14:47:23.310122Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "x = [1 2 3]'; A = randi(4,3);\n",
    "\n",
    "isequal(Gaxpy_col(A, x ), A * x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.1.4' (MV: Column-Oriented Gaxpy_axpy) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:23.405129Z",
     "start_time": "2018-02-09T14:47:23.346122Z"
    }
   },
   "outputs": [],
   "source": [
    "function y = Gaxpy_col2(A, x)\n",
    "    [m, n] = size(A);\n",
    "    y = zeros(m,1);\n",
    "    \n",
    "    for j = 1:n\n",
    "        y = y + x(j) * A(:,j);\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:23.446120Z",
     "start_time": "2018-02-09T14:47:23.412135Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "x = [1 2 3]'; A = randi(4,3); \n",
    "\n",
    "isequal(Gaxpy_col2(A, x ), A * x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.1.5 (MM: ijk Matrix Multiplication)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:45:42.947067Z",
     "start_time": "2018-02-09T15:45:42.843068Z"
    }
   },
   "outputs": [],
   "source": [
    "function C = MM_ijk(A, B)\n",
    "    [m,r] = size(A);\n",
    "    [r2,n] = size(B);\n",
    "    \n",
    "    assert(r == r2, 'Dimension mismatch');\n",
    "    \n",
    "    C = zeros(m, n);\n",
    "    for i = 1:m\n",
    "        for j = 1:n\n",
    "            for k = 1:r\n",
    "                C(i,j) = C(i,j) + A(i,k) * B(k,j);\n",
    "            end\n",
    "        end\n",
    "    end\n",
    "\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:45:43.809981Z",
     "start_time": "2018-02-09T15:45:43.749982Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "A = randi( [-2,2], 5, 3 );\n",
    "B = randi( [-2,2], 3, 4 );\n",
    "\n",
    "isequal( MM_ijk(A, B), A * B ) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:47:23.651122Z",
     "start_time": "2018-02-09T14:47:23.616121Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans =\n",
      "\n",
      "  -5   7\n",
      "   7  -6\n",
      "  -9   8\n",
      "   7  -8\n",
      "\n"
     ]
    }
   ],
   "source": [
    "A = [3 -1 2;1 0 -2; -2 1 3; 0 -1 -3];B = [1 0; 2 -1; -3 3];\n",
    "MM_ijk(A, B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.1.6 (MM: Double Loop Around Dot Product)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:45:56.167836Z",
     "start_time": "2018-02-09T15:45:56.073831Z"
    }
   },
   "outputs": [],
   "source": [
    "function C = MM_dot(A, B)\n",
    "    [m,r] = size(A);\n",
    "    [r2,n] = size(B);\n",
    "    \n",
    "    assert(r == r2, 'Dimension mismatch');\n",
    "    \n",
    "    C = zeros(m, n);\n",
    "    for i = 1:m\n",
    "        for j = 1:n\n",
    "            C(i,j) = C(i,j) + A(i,:) * B(:,j);\n",
    "        end\n",
    "    end\n",
    "\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:45:57.243949Z",
     "start_time": "2018-02-09T15:45:57.206925Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "A = randi( [-2,2], 5, 3 );\n",
    "B = randi( [-2,2], 3, 4 );\n",
    "\n",
    "isequal( MM_dot(A, B), A * B ) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.1.6' (MM: Single Loop Around Row Vector Times Matrix Product)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:46:03.952342Z",
     "start_time": "2018-02-09T15:46:03.873341Z"
    }
   },
   "outputs": [],
   "source": [
    "function C = MM_dot2(A, B)\n",
    "    [m,r] = size(A);\n",
    "    [r2,n] = size(B);\n",
    "    \n",
    "    assert(r == r2, 'Dimension mismatch');\n",
    "    \n",
    "    C = zeros(m, n);\n",
    "    for i = 1:m\n",
    "        C(i,:) = C(i,:) + A(i,:) * B;\n",
    "    end\n",
    "\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:46:04.773444Z",
     "start_time": "2018-02-09T15:46:04.733454Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "A = randi( [-2,2], 5, 3 );\n",
    "B = randi( [-2,2], 3, 4 );\n",
    "\n",
    "isequal( MM_dot2(A, B), A * B ) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.1.7 (MM: Double Loop Saxpy Matrix Multiplication)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:46:15.792966Z",
     "start_time": "2018-02-09T15:46:15.706972Z"
    }
   },
   "outputs": [],
   "source": [
    "function C = MM_Saxpy(A, B)\n",
    "    [m,r] = size(A);\n",
    "    [r2,n] = size(B);\n",
    "    \n",
    "    assert(r == r2, 'Dimension mismatch');\n",
    "    \n",
    "    C = zeros(m, n);\n",
    "    for j = 1:n\n",
    "        for k = 1:r\n",
    "            C(:,j) = C(:,j) + A(:,k) * B(k,j);\n",
    "        end        \n",
    "    end\n",
    "\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:46:16.514538Z",
     "start_time": "2018-02-09T15:46:16.472544Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "A = randi( [-2,2], 5, 3 );\n",
    "B = randi( [-2,2], 3, 4 );\n",
    "\n",
    "isequal( MM_Saxpy(A, B), A * B ) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.1.7' (MM: Single Loop: Saxpy Matrix Multiplication)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:46:23.113279Z",
     "start_time": "2018-02-09T15:46:23.036339Z"
    }
   },
   "outputs": [],
   "source": [
    "function C = MM_Saxpy2(A, B)\n",
    "    [m,r] = size(A);\n",
    "    [r2,n] = size(B);\n",
    "    \n",
    "    assert(r == r2, 'Dimension mismatch');\n",
    "    \n",
    "    C = zeros(m, n);\n",
    "    for j = 1:n\n",
    "        C(:,j) = C(:,j) + A * B(:,j);\n",
    "    end\n",
    "\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:46:23.973323Z",
     "start_time": "2018-02-09T15:46:23.935266Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "A = randi( [-2,2], 5, 3 );\n",
    "B = randi( [-2,2], 3, 4 );\n",
    "\n",
    "isequal( MM_Saxpy2(A, B), A * B ) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.1 .8 (MM: Outer Product Matrix Multiplication)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:46:29.278083Z",
     "start_time": "2018-02-09T15:46:29.202039Z"
    }
   },
   "outputs": [],
   "source": [
    "function C = MM_Outer2(A, B)\n",
    "    [m,r] = size(A);\n",
    "    [r2,n] = size(B);\n",
    "    \n",
    "    assert(r == r2, 'Dimension mismatch');\n",
    "    \n",
    "    C = zeros(m, n);\n",
    "    for k = 1:r\n",
    "        C = C + A(:,k) * B(k,:);\n",
    "    end\n",
    "\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T15:46:29.865254Z",
     "start_time": "2018-02-09T15:46:29.828259Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans = 1\n"
     ]
    }
   ],
   "source": [
    "A = randi( [-2,2], 5, 3 );\n",
    "B = randi( [-2,2], 3, 4 );\n",
    "\n",
    "isequal( MM_Outer2(A, B), A * B ) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Structure and Efficiency"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.2.1 (Triangular Matrix Multiplication)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-02-09T14:42:17.865403Z",
     "start_time": "2018-02-09T14:42:17.843406Z"
    }
   },
   "source": [
    "### Algorithm 1.2.1' (Triangular Matrix Multiplication: Double Loop)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.2.2 (Band Storage Gaxpy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.2.3 (Symmetric Storage Gaxpy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Block Matrices and Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.3.1 (Strassen Matrix Multiplication)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fast Matrix-Vector Products"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.4.1  Discrete Fourier Transfrm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1.4.2 DST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1 .4.3 DCT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm 1 .4.4 (Haar Wavelet Transfrm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vectorization and Locality"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parallel Matrix Multiplication"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Octave",
   "language": "octave",
   "name": "octave"
  },
  "language_info": {
   "file_extension": ".m",
   "help_links": [
    {
     "text": "GNU Octave",
     "url": "https://www.gnu.org/software/octave/support.html"
    },
    {
     "text": "Octave Kernel",
     "url": "https://github.com/Calysto/octave_kernel"
    },
    {
     "text": "MetaKernel Magics",
     "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md"
    }
   ],
   "mimetype": "text/x-octave",
   "name": "octave",
   "version": "4.2.1"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "139px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": true,
   "toc_section_display": "block",
   "toc_window_display": true,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}