Skip to content

Instantly share code, notes, and snippets.

@ankschoubey

ankschoubey/20191021_matrix_multiplication_from_scratch.ipynb

Created October 23, 2019 15:46
Show Gist options
  • Save ankschoubey/5d182dc83dfb857d62b40e0c99da76ef to your computer and use it in GitHub Desktop.
Save ankschoubey/5d182dc83dfb857d62b40e0c99da76ef to your computer and use it in GitHub Desktop.
Download ZIP
20191021_matrix_multiplication_from_scratch.ipynb
Display the source blob
Display the rendered blob
Raw
20191021_matrix_multiplication_from_scratch.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "20191021_matrix_multiplication_from_scratch.ipynb",
"provenance": [],
"collapsed_sections": [],
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/ankschoubey/5d182dc83dfb857d62b40e0c99da76ef/20191021_matrix_multiplication_from_scratch.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "2AI-OW5W9khf",
"colab_type": "text"
},
"source": [
"FastAI 8 \n",
"https://forums.fast.ai/t/lesson-8-notes/41442/22\n",
"\n",
"http://matrixmultiplication.xyz/\n",
"\n",
"---\n",
"\n",
"\n",
"This is one of my random practice notebook. I try to recreate what I am learning from FastAI without refering the original notesa. \n",
"\n",
"Most/all content/ideas from this ntoebook are not my own but from source are links above. #NoPlagiarism\n",
"\n",
"---\n"
]
},
{
"cell_type": "code",
"metadata": {
"id": "4iBYkZIE_JDE",
"colab_type": "code",
"colab": {}
},
"source": [
"import torch"
],
"execution_count": 0,
"outputs": []
},
{
"cell_type": "code",
"metadata": {
"id": "eayn6JUV9p6B",
"colab_type": "code",
"outputId": "ff3842b3-91ff-4c11-c188-eab79c818b43",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 67
}
},
"source": [
"m1 = [\n",
" [1, 2, 3],\n",
" [4, 5, 6],\n",
" [6, 7, 8],\n",
"]\n",
"\n",
"m1 = torch.Tensor(m1)\n",
"m1, m1.shape"
],
"execution_count": 2,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"(tensor([[1., 2., 3.],\n",
" [4., 5., 6.],\n",
" [6., 7., 8.]]), torch.Size([3, 3]))"
]
},
"metadata": {
"tags": []
},
"execution_count": 2
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "xYA_AVir_HqA",
"colab_type": "code",
"outputId": "8493c871-86e3-4665-bdb7-4a8d6013888f",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 67
}
},
"source": [
"m2 = [\n",
" [1], \n",
" [2], \n",
" [3],\n",
"]\n",
"m2 = torch.Tensor(m2)\n",
"m2, m2.shape"
],
"execution_count": 3,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"(tensor([[1.],\n",
" [2.],\n",
" [3.]]), torch.Size([3, 1]))"
]
},
"metadata": {
"tags": []
},
"execution_count": 3
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "1BItx4jP_WZd",
"colab_type": "code",
"outputId": "fba1cc14-eeab-4c86-935e-71cd91f1d187",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 67
}
},
"source": [
"m1 @ m2"
],
"execution_count": 4,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"tensor([[14.],\n",
" [32.],\n",
" [44.]])"
]
},
"metadata": {
"tags": []
},
"execution_count": 4
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "xRPGrXKB_kh3",
"colab_type": "text"
},
"source": [
"# Manual"
]
},
{
"cell_type": "code",
"metadata": {
"id": "7jqG7WQQ_laU",
"colab_type": "code",
"outputId": "783ee75b-1261-48f6-ad19-e935fab9b8eb",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 67
}
},
"source": [
"#check if rows of first matrix is equal to columns of second\n",
"r1, c1 = m1.shape\n",
"r2, c2 = m2.shape\n",
"assert c1 == r2\n",
"\n",
"# the resultant matrix shape is rows of first column x columns of second\n",
"# creating empty array\n",
"result = torch.zeros(r1, c2)\n",
"\n",
"# run and look at matrixmultiplication.xyz to clearly understand what is written below\n",
"# i tracks row number of first matrix and row of resultant matrix\n",
"#### j tracks columns of first matrix which is equal to rows of second \n",
"######## k tracks columns of second matrix and column of resultant matrix\n",
"\n",
"for i in range(r1):\n",
" for j in range(c1):\n",
" for k in range(c2):\n",
" result[i,k] += m1[i,j] * m2[j,k]\n",
"\n",
"result"
],
"execution_count": 5,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"tensor([[14.],\n",
" [32.],\n",
" [44.]])"
]
},
"metadata": {
"tags": []
},
"execution_count": 5
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "Ii6FF_6RCBwH",
"colab_type": "text"
},
"source": [
"To make this faster we have to vectorize it... remove loops starting from innter most"
]
},
{
"cell_type": "code",
"metadata": {
"id": "4uutfCeU_3kZ",
"colab_type": "code",
"outputId": "956f7b08-5b48-471b-f1f7-ef39a87ff285",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 250
}
},
"source": [
"result = torch.zeros(r1, c2)\n",
"\n",
"for i in range(r1):\n",
" for j in range(c1):\n",
" result[i] = m1[i]*m2[j]\n",
" #for k in range(c2):\n",
" # result[i,k] += m1[i,j] * m2[j,k]"
],
"execution_count": 6,
"outputs": [
{
"output_type": "error",
"ename": "RuntimeError",
"evalue": "ignored",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mRuntimeError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-6-f7776c7ad833>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mr1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mj\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mc1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m \u001b[0mresult\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mm1\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0mm2\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 6\u001b[0m \u001b[0;31m#for k in range(c2):\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 7\u001b[0m \u001b[0;31m# result[i,k] += m1[i,j] * m2[j,k]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mRuntimeError\u001b[0m: The expanded size of the tensor (1) must match the existing size (3) at non-singleton dimension 0. Target sizes: [1]. Tensor sizes: [3]"
]
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "lYIORL5sHoEX",
"colab_type": "text"
},
"source": [
"Because of errors I went back and looked at my multiplication loop and then modiefied it so that we can easily remove variable k"
]
},
{
"cell_type": "code",
"metadata": {
"id": "eWCMiquaCWAG",
"colab_type": "code",
"outputId": "cbb5baa8-6755-4c22-994e-8ef4b53b36ca",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 67
}
},
"source": [
"m1"
],
"execution_count": 7,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"tensor([[1., 2., 3.],\n",
" [4., 5., 6.],\n",
" [6., 7., 8.]])"
]
},
"metadata": {
"tags": []
},
"execution_count": 7
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "RphrtWC_HLma",
"colab_type": "code",
"outputId": "9bc1b6c0-b49e-41dd-b00b-0de655688d58",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 67
}
},
"source": [
"m2"
],
"execution_count": 8,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"tensor([[1.],\n",
" [2.],\n",
" [3.]])"
]
},
"metadata": {
"tags": []
},
"execution_count": 8
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "z3grmPhQHMp2",
"colab_type": "code",
"outputId": "65326c9a-c544-4ada-ba0d-5b6227660c4c",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
}
},
"source": [
"# get first row of first matrix\n",
"i = 0\n",
"m1[i]"
],
"execution_count": 9,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"tensor([1., 2., 3.])"
]
},
"metadata": {
"tags": []
},
"execution_count": 9
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "B7umNhhKHSQ9",
"colab_type": "code",
"outputId": "6f0578a7-b13b-4d20-946c-dc14ebeeef8d",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
}
},
"source": [
"# get first column of second matrix\n",
"j = 0\n",
"m2[:,j]"
],
"execution_count": 13,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"tensor([1., 2., 3.])"
]
},
"metadata": {
"tags": []
},
"execution_count": 13
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "FaFA07EXHUet",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 67
},
"outputId": "4b4230c6-6fc3-41d5-d05a-ca40161c287a"
},
"source": [
"result = torch.zeros(r1, c2)\n",
"\n",
"# shorten function\n",
"\n",
"for i in range(r1):\n",
" for j in range(c2):\n",
" result[i,j] = (m1[i]*m2[:,j]).sum()\n",
"\n",
"result"
],
"execution_count": 15,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"tensor([[14.],\n",
" [32.],\n",
" [44.]])"
]
},
"metadata": {
"tags": []
},
"execution_count": 15
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "7DQisbehRFtQ",
"colab_type": "text"
},
"source": [
"Even simpler:\n",
"\n",
"Einsum\n",
"\n",
"FastAI 8 \n",
"https://forums.fast.ai/t/lesson-8-notes/41442/22"
]
},
{
"cell_type": "code",
"metadata": {
"id": "DtJrGl3DQ_XP",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 67
},
"outputId": "997bbb4b-2958-40cf-c167-f2cfced2db4b"
},
"source": [
"result = torch.einsum('ik,kj->ij',m1,m2)\n",
"result"
],
"execution_count": 20,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"tensor([[14.],\n",
" [32.],\n",
" [44.]])"
]
},
"metadata": {
"tags": []
},
"execution_count": 20
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "nWYx9wHRSGLU",
"colab_type": "text"
},
"source": [
"Simplest:"
]
},
{
"cell_type": "code",
"metadata": {
"id": "FyotozvcSFtp",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 67
},
"outputId": "fb54b518-d609-4828-f4a9-f53593103fce"
},
"source": [
"result = m1@m2\n",
"result"
],
"execution_count": 21,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"tensor([[14.],\n",
" [32.],\n",
" [44.]])"
]
},
"metadata": {
"tags": []
},
"execution_count": 21
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "Ll4vCTc7RQaw",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 67
},
"outputId": "4d96a402-bf24-4817-8881-90a2e6b4ed19"
},
"source": [
"result = m1.matmul(m2)\n",
"result"
],
"execution_count": 23,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"tensor([[14.],\n",
" [32.],\n",
" [44.]])"
]
},
"metadata": {
"tags": []
},
"execution_count": 23
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "9IyCHFc_SSmj",
"colab_type": "text"
},
"source": [
"The reason to use Pytorch implementation is that it is about 50,000 times faster than regular python.\n",
"\n",
"For details check out:\n",
"\n",
"FastAI 8 \n",
"https://forums.fast.ai/t/lesson-8-notes/41442/22"
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment