{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In problem 5.11 in last week's assignment, we saw how we can use Givens rotations to perform QR factorization. This week, your task is to implement that algorithm.\n",
    "\n",
    "The overall goal of this problem is to write a function to overwrite a matrix $A \\in \\mathbb{R}^{n \\times n}$ with an upper triangular matrix $R \\in \\mathbb{R}^{n \\times n}$.\n",
    "\n",
    "A recurring theme of this class has been that it is often unwise to explicitly construct a matrix if you don't have to. To see how much time can be saved by an efficient implementation, you will implement two versions of the Givens algorithm. The naive version constructs the matrix $G$ and performs a regular matrix multiplication $G*A$ at each iteration, while the efficient version uses the algorithm from 5.11(b) to modify the necessary entries of $A$ in place at each iteration, without ever explicitly constructing $G$.\n",
    "\n",
    "First, write a givensRotation function, which takes in a matrix $A$ and a bool to indicate whether we are performing the naive or optimized algorithm, and overwrites $A$ with $R$, which is upper triangular. Note that some of the code will be shared, but at some point you should break up your function with something like: if (naive) ... else ...\n",
    "\n",
    "We've given you a skeleton below as a guide, but you're welcome to change it in any way you like.\n",
    "\n",
    "You'll also notice that one Givens rotation affects two rows of $A$. When trying to zero out an entry in row $i$, we recommend using row $i-1$ as the other row. If you adopt this strategy, make sure to loop through the matrix in an appropriate order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "givensRotation (generic function with 1 method)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function givensRotation(A, naive)\n",
    "    # Loop through entries of the matrix that need to be zeroed\n",
    "    for col = ...\n",
    "        for row = ...\n",
    "            # Define r, c, s\n",
    "            r = ...\n",
    "            c = ...\n",
    "            s = ...\n",
    "            # Naive: build full Givens rotation matrix and multiply by A. Very slow!\n",
    "            if naive\n",
    "                # YOUR CODE HERE\n",
    "            # Smarter: never build matrix G. Modify the 2 rows of A that change in place.\n",
    "            else\n",
    "                # YOUR CODE HERE\n",
    "            end\n",
    "        end\n",
    "    end\n",
    "    return A\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Verify that your function in fact produces an upper triangular matrix, by calling each version on the same random $4 \\times 4$ matrix and inspecting the output."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# function call with naive = true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# function call with naive = false"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, plot the time taken to execute each version of your Givens rotation function on random $n \\times n$ matrices, from $n=10$ to $n=150$, skipping in increments of 10. Have both plots on the same axes, and include a legend.\n",
    "\n",
    "As a hint, you can use the $\\texttt{@elapsed}$ macro in Julia, which returns how long a function call took to execute. For example, $\\texttt{@elapsed eye(100)}$ returns how long it took to build the $100 \\times 100$ identity matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.5.1",
   "language": "julia",
   "name": "julia-0.5"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}