{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#Table of Contents\n",
    "* [Practice session 2](#Practice-session-2)\n",
    "\t* [FFT](#FFT)\n",
    "\t* [Circulant matvec](#Circulant-matvec)\n",
    "\t* [Toeplitz matvec](#Toeplitz-matvec)\n",
    "\t* [Singular Value Decomposition (SVD)](#Singular-Value-Decomposition-%28SVD%29)\n",
    "\t* [Profiling and debugging](#Profiling-and-debugging)\n",
    "\t\t* [profiling](#profiling)\n",
    "\t\t* [debugging](#debugging)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice session 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fast matvecs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FFT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Create the Fourier matrix $F$ using `np.meshgrid` function\n",
    "* Generate random vector $x$\n",
    "* Compare timings of the FFT(x) and direct multiplication $Fx$ by plotting times for different matrix sizes\n",
    "* Make sure that you got $\\mathcal{O}(n^2)$ and $\\mathcal{O}(n \\log n)$ complexity by find slopes of each line in the loglog scale"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Circulant matvec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Generate a random circulant matrix $C$\n",
    "* Implement fast multiplication by $C$ using fast Fourier transforms\n",
    "* Plot times of direct multiplication by $C$ and using your fast implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Toeplitz matvec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Do tasks in the Circulant matvec part but for randomply generated Toeplitz matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Singular Value Decomposition (SVD)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Singular value decomposition is a representation of $A$ in the folling form\n",
    "$$\n",
    "A = U\\Sigma V^*,\n",
    "$$\n",
    "where $U$ and $V$ are unitary matrices and $\\Sigma = \\text{diag}(\\sigma_1, \\dots, \\sigma_r, 0, \\dots, 0)$ with $\\sigma_1 \\geq \\sigma_2 \\geq \\dots \\geq \\sigma_r>0$ is a martrix with singular values on the diagonal, where $r$ is rank of the matrix $A$. \n",
    "Often in practice we have matrices of full rank, but a lot of singular values are small enough for this matrix to be considered as approximately of low rank.\n",
    "On the next week you will learn mathematical formulation of this property.\n",
    "\n",
    "And now we will just play around SVD.\n",
    "\n",
    "* Assemble Hilbert matrix $A$ by using `np.meshgrid` function\n",
    "* Calculate singular value decomposition of the Hilbert matrix of size $n\\times n$ by `np.linalg.svd`\n",
    "* Plot on the same plot singular values for different $n$ in the logarithmic scale\n",
    "* What is approximate rank $r_\\text{machine}$ of the Hilbert matrix with machine precision for different $n$? \n",
    "* Plot $r_\\text{machine}$ as a function of $n$\n",
    "* Find low-rank approximation of $A$ by truncating singular values that are of machine precision. Measure norm of difference between the initial matrix and the low-rank approximation\n",
    "* Plot singular values of randomly generated matrix. Can it be well approximated by a low-rank matrix?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Profiling and debugging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section you learn how to use profiling."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### profiling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You have a task with implementing Gram-Schmidt algorithm in your home assignment. If you've already completed it, try to improve your implementation with help of line profiler. If you haven't done this task yet try to do it here. The instructions on how to use line profiler are below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def gram_schmidt(V):\n",
    "    #your code goes here\n",
    "    #V - is a matrix of columns to orthogonalize\n",
    "    #U - orthogonalized output\n",
    "    \n",
    "    return U"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How fast is your code? Let's use *line profiler* package. It's not part of standard python library and not in anaconda distribution. In order to install it run:\n",
    "```\n",
    "conda install line_profiler\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If installation is successful you can add profiling functionality into your notebook with help of IPython magic.\n",
    "Run \n",
    "```python\n",
    "%load_ext line_profiler\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "somewhere in the notebook.\n",
    "Now you can assess any function with the following code:\n",
    "```python\n",
    "%lprun -f your_func your_func(*args, **kwargs)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task**: Run line profiler on your algorithm. What's the most time-consuming operation in the code? Verify that it holds for different sizes of initial matrix.\n",
    "\n",
    "How can you improve your code? Try to implement your optimization and run *line profiler* to "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### debugging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try to run the following code. Why does it fail? Use ```%pdb``` magic to debug that code and fix the error."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def mul_col(shape):\n",
    "    mat = np.random.rand(*shape)\n",
    "    vec = np.random.rand(shape[0])\n",
    "    res = mat.dot(vec)\n",
    "    return res"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}