kronecker+Product.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Kronecker product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given two matrices, $A$ with size $m\\times n$, and $B$ with size $p\\times q$, define Kronecker product ($A\\bigotimes B$) as matrix with size $mp\\times nq$ and:\n",
    "\n",
    "\n",
    "$$\n",
    "A \\otimes B   = \\begin{bmatrix}\n",
    "   a_{11} b_{11} & a_{11} b_{12} & \\cdots & a_{11} b_{1q} & \n",
    "                   \\cdots & \\cdots & a_{1n} b_{11} & a_{1n} b_{12} & \\cdots & a_{1n} b_{1q} \\\\\n",
    "   a_{11} b_{21} & a_{11} b_{22} & \\cdots & a_{11} b_{2q} & \n",
    "                   \\dots & \\cdots & a_{1n} b_{21} & a_{1n} b_{22} & \\dots & a_{1n} b_{2q} \\\\\n",
    "   \\vdots & \\vdots & \\ddots & \\vdots & & & \\vdots & \\vdots & \\dots & \\vdots \\\\\n",
    "   a_{11} b_{p1} & a_{11} b_{p2} & \\cdots & a_{11} b_{pq} & \n",
    "                   \\cdots & \\cdots & a_{1n} b_{p1} & a_{1n} b_{p2} & \\cdots & a_{1n} b_{pq} \\\\\n",
    "   \\vdots & \\vdots & & \\vdots & \\ddots & & \\vdots & \\vdots & & \\vdots \\\\\n",
    "   \\vdots & \\vdots & & \\vdots & & \\ddots & \\vdots & \\vdots & & \\vdots \\\\\n",
    "   a_{m1} b_{11} & a_{m1} b_{12} & \\cdots & a_{m1} b_{1q} & \n",
    "                   \\cdots & \\cdots & a_{mn} b_{11} & a_{mn} b_{12} & \\cdots & a_{mn} b_{1q} \\\\\n",
    "   a_{m1} b_{21} & a_{m1} b_{22} & \\cdots & a_{m1} b_{2q} & \n",
    "                   \\cdots & \\cdots & a_{mn} b_{21} & a_{mn} b_{22} & \\cdots & a_{mn} b_{2q} \\\\\n",
    "   \\vdots & \\vdots & \\ddots & \\vdots & & & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "   a_{m1} b_{p1} & a_{m1} b_{p2} & \\cdots & a_{m1} b_{pq} & \n",
    "                   \\cdots & \\cdots & a_{mn} b_{p1} & a_{mn} b_{p2} & \\cdots & a_{mn} b_{pq} \n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "For example:\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "a_{11} & a_{12} \\\\\n",
    "a_{21} & a_{22} \\\\\n",
    "a_{31} & a_{32}\n",
    "\\end{bmatrix}\n",
    "\\otimes\n",
    "\\begin{bmatrix}\n",
    "b_{11} & b_{12} & b_{13} \\\\\n",
    "b_{21} & b_{22} & b_{23}\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "a_{11} b_{11} & a_{11} b_{12} & a_{11} b_{13} & a_{12} b_{11} & a_{12} b_{12} & a_{12} b_{13} \\\\\n",
    "a_{11} b_{21} & a_{11} b_{22} & a_{11} b_{23} & a_{12} b_{21} & a_{12} b_{22} & a_{12} b_{23} \\\\\n",
    "a_{21} b_{11} & a_{21} b_{12} & a_{21} b_{13} & a_{22} b_{11} & a_{22} b_{12} & a_{22} b_{13} \\\\\n",
    "a_{21} b_{21} & a_{21} b_{22} & a_{21} b_{23} & a_{22} b_{21} & a_{22} b_{22} & a_{22} b_{23} \\\\\n",
    "a_{31} b_{11} & a_{31} b_{12} & a_{31} b_{13} & a_{32} b_{11} & a_{32} b_{12} & a_{32} b_{13} \\\\\n",
    "a_{31} b_{21} & a_{31} b_{22} & a_{31} b_{23} & a_{32} b_{21} & a_{32} b_{22} & a_{32} b_{23}\n",
    "\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from math import floor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "C = {zeros}(shape=(mp,nq))\\\\\n",
    "for \\; j=1 \\; to \\; m_{a}\\cdot m_{b}\\; step \\;1:\\\\\n",
    "\\quad\\quad\\quad\\quad for \\; i=1 \\; to \\; n_{a}\\cdot n_{b}\\; step \\;1:\\\\\n",
    "\\quad\\quad\\quad\\quad\\quad\\quad\\quad C_{i,j}=A_{\\left\\lfloor \\frac{i}{m_{a}} \\right\\rfloor,\\left\\lfloor \\frac{j}{n_{a}} \\right\\rfloor} \\cdot B_{{i\\; mod\\; n_{b}}\\;,\\;{j\\; mod\\; n_{b}}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kron_imp(matrixA,matrixB):\n",
    "    na,ma = matrixA.shape\n",
    "    nb,mb = matrixB.shape    \n",
    "    matrixC = np.zeros(shape=(na*nb,ma*mb))\n",
    "    for p in range(na*nb):\n",
    "        for q in range(ma*mb):\n",
    "            matrixC[p][q]=matrixA[floor(p/nb),floor(q/mb)]*matrixB[p%nb][q%mb]    \n",
    "    return matrixC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 311 µs, sys: 0 ns, total: 311 µs\n",
      "Wall time: 261 µs\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "#A = np.array([[1, 2], [4, 5], [6, 7], [6, 7]], np.int32)\n",
    "#B = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9],[10, 11, 12]], np.int32)\n",
    "A = np.random.randn(5, 2)\n",
    "B = np.random.randn(4, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 147 µs, sys: 0 ns, total: 147 µs\n",
      "Wall time: 150 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([[-0.17101978, -0.09240047,  1.04088165,  0.56237911],\n",
       "       [ 0.04051194,  0.07709563, -0.24656876, -0.46922892],\n",
       "       [-0.1588155 ,  0.05601377,  0.96660245, -0.34091789],\n",
       "       [ 0.27749548,  0.22742186, -1.68892716, -1.38416291],\n",
       "       [-0.54190881, -0.29278852,  0.03987889,  0.02154621],\n",
       "       [ 0.12836981,  0.24429222, -0.00944669, -0.01797738],\n",
       "       [-0.50323721,  0.17749031,  0.03703306, -0.01306145],\n",
       "       [ 0.87929738,  0.72062955, -0.0647072 , -0.05303089],\n",
       "       [-0.22753339, -0.12293427,  0.2114139 ,  0.11422505],\n",
       "       [ 0.05389914,  0.10257194, -0.05008068, -0.09530528],\n",
       "       [-0.2112962 ,  0.07452356,  0.19632702, -0.06924397],\n",
       "       [ 0.36919407,  0.30257358, -0.34303868, -0.28113789],\n",
       "       [-0.83406917, -0.45064016, -0.7265852 , -0.39256753],\n",
       "       [ 0.19757808,  0.37599796,  0.17211679,  0.32754424],\n",
       "       [-0.77454848,  0.27318101, -0.67473476,  0.237977  ],\n",
       "       [ 1.3533547 ,  1.10914397,  1.17895197,  0.96621194],\n",
       "       [ 0.43000287,  0.23232673,  0.44189136,  0.23874998],\n",
       "       [-0.10186103, -0.19384508, -0.10467723, -0.1992044 ],\n",
       "       [ 0.39931708, -0.14083798,  0.41035719, -0.1447318 ],\n",
       "       [-0.69771959, -0.57181719, -0.71700978, -0.58762649]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "kron_imp(A,B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 115 µs, sys: 7 µs, total: 122 µs\n",
      "Wall time: 112 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([[-0.17101978, -0.09240047,  1.04088165,  0.56237911],\n",
       "       [ 0.04051194,  0.07709563, -0.24656876, -0.46922892],\n",
       "       [-0.1588155 ,  0.05601377,  0.96660245, -0.34091789],\n",
       "       [ 0.27749548,  0.22742186, -1.68892716, -1.38416291],\n",
       "       [-0.54190881, -0.29278852,  0.03987889,  0.02154621],\n",
       "       [ 0.12836981,  0.24429222, -0.00944669, -0.01797738],\n",
       "       [-0.50323721,  0.17749031,  0.03703306, -0.01306145],\n",
       "       [ 0.87929738,  0.72062955, -0.0647072 , -0.05303089],\n",
       "       [-0.22753339, -0.12293427,  0.2114139 ,  0.11422505],\n",
       "       [ 0.05389914,  0.10257194, -0.05008068, -0.09530528],\n",
       "       [-0.2112962 ,  0.07452356,  0.19632702, -0.06924397],\n",
       "       [ 0.36919407,  0.30257358, -0.34303868, -0.28113789],\n",
       "       [-0.83406917, -0.45064016, -0.7265852 , -0.39256753],\n",
       "       [ 0.19757808,  0.37599796,  0.17211679,  0.32754424],\n",
       "       [-0.77454848,  0.27318101, -0.67473476,  0.237977  ],\n",
       "       [ 1.3533547 ,  1.10914397,  1.17895197,  0.96621194],\n",
       "       [ 0.43000287,  0.23232673,  0.44189136,  0.23874998],\n",
       "       [-0.10186103, -0.19384508, -0.10467723, -0.1992044 ],\n",
       "       [ 0.39931708, -0.14083798,  0.41035719, -0.1447318 ],\n",
       "       [-0.69771959, -0.57181719, -0.71700978, -0.58762649]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "np.kron(A,B)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}