SparseMatrixMultiplication.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "SparseMatrixMultiplication.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyPypPnHtq44DUXqq9H4jaTZ",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/AjayKadoula/Mtech_Lab_1/blob/main/SparseMatrixMultiplication.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pBYZuSknNcre"
      },
      "source": [
        "# **Sparse Matrix Multiplication**\n",
        "\n",
        "Sparse matrices are matrices in which most elements are zero. To save space and running time it is critical to only store the nonzero elements.\n",
        "\n",
        "A common operation on sparse matrices is to multiply them by a dense vector. In such an operation, the result is the dot-product of each sparse row of the matrix with the dense vector. \n",
        "\n",
        "1.First find the transpose of 2nd Matrix\n",
        "\n",
        "2.Find all the possible combinations for calculation of product\n",
        "\n",
        "3.Store all the possible combinations in the product matrix\n",
        "\n",
        "4.Arrange the product matrix\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BUNbbNclNDPg"
      },
      "source": [
        "class _MatrixElement:\n",
        "      def __init__(self, row ,col, value):\n",
        "          self.row = row\n",
        "          self.col = col\n",
        "          self.value = value\n",
        "\n",
        "class SparseMatrix:\n",
        "      def __init__(self, numRows, numCols):\n",
        "          self._numRows = numRows\n",
        "          self._numCols = numCols\n",
        "          self._elementList = list()\n",
        "    \n",
        "      def numRows(self):\n",
        "          return self._numRows\n",
        "    \n",
        "      def numCols(self):\n",
        "          return self._numCols\n",
        "\n",
        "      def __setitem__(self, ndxTuple, scalar):\n",
        "          ndx = self._findPosition(ndxTuple[0], ndxTuple[1])\n",
        "          if ndx is not None:\n",
        "              if scalar != 0.0:\n",
        "                  self._elementList[ndx].value = scalar\n",
        "              else:\n",
        "                  self._elementList.pop(ndx)\n",
        "          else:\n",
        "              if scalar != 0.0:\n",
        "                  element = _MatrixElement(ndxTuple[0], ndxTuple[1], scalar)\n",
        "                  self._elementList.append(element)\n",
        "\n",
        "      def __getitem__(self, row, col):\n",
        "          assert row >= 0 and row < self.numRows(), \"Subscript out of range\"\n",
        "          assert col >= 0 and col < self.numCols(), \"Subscript out of range\"\n",
        "          ndx = self._findPosition(row, col)\n",
        "          if ndx is not None:\n",
        "              return self._elementList[ndx]\n",
        "          else:\n",
        "              raise Exception(\"The element is not in the matrix\")\n",
        "\n",
        "      def _findPosition(self, row, col):\n",
        "          \"\"\"Find the position of the non zero element in the list, using the row and col as parameters\"\"\"\n",
        "          n = len(self._elementList)\n",
        "          for i in range(n):\n",
        "              if (row == self._elementList[i].row and\n",
        "                  col == self._elementList[i].col):\n",
        "                  return i\n",
        "          return None\n",
        "\n",
        "      def transpose(self):\n",
        "          newTransposeMatrix = SparseMatrix(numRows=self.numCols(), numCols=self.numRows())\n",
        "          for elem in self._elementList:\n",
        "              tmp_row = elem.row\n",
        "              elem.row = elem.col\n",
        "              elem.col = tmp_row\n",
        "              newTransposeMatrix._elementList.append(elem)\n",
        "          return newTransposeMatrix\n",
        "\n",
        "      def __mul__(self, otherMatrix):\n",
        "          assert isinstance(otherMatrix, SparseMatrix), \"Wrong matrix type\"\n",
        "          assert self.numCols() == otherMatrix.numRows(), \"The two matrices can't be multiplied\"\n",
        "          transpMatrix = otherMatrix.transpose()\n",
        "          sparseNewMatrix = SparseMatrix(numRows=self.numRows(), numCols=otherMatrix.numRows())\n",
        "          for apos in range(len(self._elementList)):\n",
        "              r = self._elementList[apos].row\n",
        "              for bpos in range(len(transpMatrix._elementList)):\n",
        "                   c = transpMatrix._elementList[bpos].row\n",
        "                   tmpa = apos\n",
        "                   tmpb = bpos\n",
        "                   the_sum = 0\n",
        "                   while (tmpa < len(self._elementList) and (tmpb < len(transpMatrix._elementList)) and (self._elementList[tmpa].row == r\n",
        "                                                                                                  and transpMatrix._elementList[tmpb].row == c)):\n",
        "                         if self._elementList[tmpa].col > transpMatrix._elementList[tmpb].col:\n",
        "                               tmpa += 1\n",
        "                         elif self._elementList[tmpa].col < transpMatrix._elementList[tmpb].col:\n",
        "                               tmpb += 1\n",
        "                         else:\n",
        "                               the_sum += self._elementList[tmpa].value * transpMatrix._elementList[tmpb].value\n",
        "                               tmpa += 1\n",
        "                               tmpb += 1\n",
        "          if the_sum != 0:\n",
        "                sparseNewMatrix.add(_MatrixElement(r, c, the_sum))\n",
        "          return sparseNewMatrix"
      ],
      "execution_count": 17,
      "outputs": []
    }
  ]
}