problems/Pset1.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:90aaaff1cf83c4c4236e75612103ecdd7ab56fc87eded7996dbf7839f64954a0"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Problem set 1"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "##Strassen Algorithm\n",
      "\n",
      "Let $C = AB$, where $A$ and $B$ are squared matrices of the same size.\n",
      "Direct computation of $C$ requires $\\mathcal{O}(n^3)$ arithmetic operations.\n",
      "Fortunately, this complexity can be reduced even for arbitrary matrices $A$ and $B$.\n",
      "The following approach which has $\\mathcal{O}(n^{\\log_2 7})$ is called Strassen algorithm.\n",
      "Its idea is based on the fact that elements of $2\\times 2$ matrix\n",
      "$$\n",
      "\\begin{bmatrix} c_{11} & c_{12} \\\\ c_{21} & c_{22}  \\end{bmatrix} =\n",
      "\\begin{bmatrix} a_{11} & a_{12} \\\\ a_{21} & a_{22}  \\end{bmatrix}\n",
      "\\begin{bmatrix} b_{11} & b_{12} \\\\ b_{21} & b_{22}  \\end{bmatrix}\n",
      "$$\n",
      "can be computed using only 7 multiplications:\n",
      "\\begin{equation}\\begin{split}\n",
      "c_{11} &= f_1 + f_4 - f_5 + f_7, \\\\\n",
      "c_{12} &= f_3 + f_5, \\\\\n",
      "c_{21} &= f_2 + f_4, \\\\\n",
      "c_{22} &= f_1 - f_2 + f_3 + f_6,\n",
      "\\end{split}\\end{equation}\n",
      "where\n",
      "\\begin{equation}\\begin{split}\n",
      "f_1 &= (a_{11} + a_{22}) (b_{11} + b_{22}),\\\\\n",
      "f_2 &= (a_{21} + a_{22}) b_{11},\\\\\n",
      "f_3 &= a_{11} (b_{12} - b_{22}),\\\\\n",
      "f_4 &= a_{22} (b_{21} - b_{11}),\\\\\n",
      "f_5 &= (a_{11} + a_{12}) b_{22},\\\\\n",
      "f_6 &= (a_{21} - a_{11}) (b_{11} + b_{12}),\\\\\n",
      "f_7 &= (a_{12} - a_{22}) (b_{21} + b_{22}).\n",
      "\\end{split}\\end{equation}\n",
      "\n",
      "Formulas above hold for the case when $a_{ij}, b_{ij}, c_{ij}$ ($i$ and $j=1,2$) are blocks.\n",
      "Therefore, spliting matrices $A$ and $B$ of abitrary sizes into 4 blocks and applying described procedure recursively for blocks one will get $\\mathcal{O}(n^{\\log_2 7})$ complexity.\n",
      "\n",
      "**Tasks**\n",
      "\n",
      "- (4 pts)  Prove that Strassen alogorithm has $\\mathcal{O}(n^{\\log_2 7})$ complexity\n",
      "- (4 pts) Implement Strassen algorithm in Python. **Note**: for simplicity consider that $n$ is a power of 2 \n",
      "- (3 pts) Compare the result with direct matrix-by-matrix multiplication and $\\verb|numpy.dot|$ procedure by ploting timings as a function of $n$. **Note**: use logarithmic scale"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "##Fast Fourier Transform\n",
      "\n",
      "Let $y = Ax$ (matvec operation), where $A \\in \\mathbb{C}^{m\\times n}$ and $x \\in \\mathbb{C}^{n\\times 1}$. \n",
      "Direct computation of $y$ requires $\\mathcal{O}(n^2)$. \n",
      "Since $A$ contains $n^2$ elements, this complexity can not be reduced for an arbitrary matrix $A$.\n",
      "There are certain classes of matrices for which matvec requires less operations.\n",
      "For instance, sparse, Toeplitz, lowrank, etc.\n",
      "Another important example of structured matrix which arises in a huge amount of applications (signal and image processing, fast PDE solvers) is Fourier matrix\n",
      "$$\n",
      "F_n = \\{ \\omega^{kl} \\}_{k,l=0}^{n-1}, \\quad \\text{where} \\quad \\omega = e^{-\\frac{2\\pi i}{n}}.\n",
      "$$\n",
      "Matvec operation with Fourier matrix is called discrete Fourier transform (DFT) and has $\\mathcal{O}(n \\log n)$ complexity.\n",
      "The simplest way to get this complexity is to spilt odd and even rows in Fourier matrix:\n",
      "\\begin{equation}\n",
      "P_n F_n = \\begin{bmatrix} F_{n/2} & F_{n/2} \\\\ F_{n/2} W_{n/2} & -F_{n/2} W_{n/2} \\end{bmatrix}, \\quad (1)\n",
      "\\end{equation}\n",
      "where $P_n$ is a permutaion matrix which permutes odd and even rows, and $W_{n/2}=\\text{diag}(1,\\omega,\\omega^2,\\dots,\\omega^{n/2-1})$.\n",
      "Thus, multiplication by $F_n$ is reduced to several multiplications by $F_{n/2}$ and linear operations such as multiplication by the diagonal matrix $W_{n/2}$.\n",
      "Continuing this procedure recursively for $F_{n/2}$ we will get $\\mathcal{O}(n \\log n)$ operations.\n",
      "\n",
      "**Tasks**\n",
      "\n",
      "- (4 pts) Prove expression (1)\n",
      "- (4 pts) Implement the described fft algorithm in Python. **Note**: for simplicity consider that $n$ is a power of 2 \n",
      "- (3 pts) Compare the result with $\\verb|numpy.dot|$ and $\\verb|numpy.fft.fft|$ procedures by ploting timings as a function of $n$. **Note**: use logarithmic scale"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}