{"worksheets": [{"metadata": {}, "cells": [{"metadata": {}, "source": ["# Relative cost of matrix factorizations"], "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "input": ["import numpy as np\n", "import numpy.linalg as npla\n", "import scipy.linalg as spla\n", "\n", "import matplotlib.pyplot as pt\n", "\n", "from time import time"], "cell_type": "code", "language": "python", "metadata": {}, "prompt_number": 1}, {"collapsed": false, "outputs": [{"text": ["array([  10,   14,   20,   30,   43,   63,   92,  133,  193,  279,  404,\n", "        585,  848, 1228, 1778], dtype=int32)"], "metadata": {}, "prompt_number": 2, "output_type": "pyout"}], "input": ["n_values = (10**np.linspace(1, 3.25, 15)).astype(np.int32)\n", "n_values"], "cell_type": "code", "language": "python", "metadata": {}, "prompt_number": 2}, {"collapsed": false, "outputs": [{"text": ["-----> lu\n", "10\n", "14\n", "20\n", "30\n", "43\n", "63\n", "92\n", "133\n", "193\n", "279\n", "404\n", "585"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "848\n", "1228"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "1778"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "----->"], "stream": "stdout", "output_type": "stream"}, {"text": [" qr\n", "10\n", "14\n", "20\n", "30\n", "43\n", "63\n", "92\n", "133\n", "193\n", "279\n", "404\n", "585"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "848"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "1228"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "1778"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "----->"], "stream": "stdout", "output_type": "stream"}, {"text": [" svd\n", "10\n", "14\n", "20\n", "30\n", "43\n", "63\n", "92\n", "133\n", "193\n", "279"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "404"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "585"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "848"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "1228"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n", "1778"], "stream": "stdout", "output_type": "stream"}, {"text": ["\n"], "stream": "stdout", "output_type": "stream"}, {"text": ["<matplotlib.text.Text at 0x7f846db8ea90>"], "metadata": {}, "prompt_number": 9, "output_type": "pyout"}, {"png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAERCAYAAACdPxtnAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xd8FVX+//HXJwkkIZQQEEVAgwqIyhpARayxrbprW4Ku\nYIvdtWIvuyj+bNgQXbGX2ED5Euy4tk0sKyIIERQEURCVohBqgNTP74+ZhEtIyE1y587c3M/z8ZhH\n7sy9ufO+c5NzZs6ZOSOqijHGmPiU4HcAY4wx/rFKwBhj4phVAsYYE8esEjDGmDhmlYAxxsQxqwSM\nMSaOeVoJiMhVIjJHRL4Vkau8XJcxxpjG86wSEJF9gAuA/YF9gRNEZHev1meMMabxvDwS2BOYpqqb\nVbUS+AQY4uH6jDHGNJKXlcC3wKEikiEibYC/At09XJ8xxphGSvLqjVX1exG5F/gAKAFmAVVerc8Y\nY0zjSbTGDhKRu4ElqvpEyDIbuMgYY5pAVSUS7+P12UFd3J+7AH8Dxtd+jaoGbrrtttt8z2CZLFM8\n5rJMdUzffIPeccdWyyLJ6+sEJonId8BbwKWqus7j9UXE4sWL/Y6wDcsUHssUviDmsky1bNwIw4bB\nrrt6tgrP+gQAVPUwL9/fGGNatOuug6wsOPNMz1bhaSUQq3Jzc/2OsA3LFB7LFL4g5rJMId58E957\nD4qKQCLS/F+nqHUM17lyEfVz/cYYE0hLl8KAATB5Mhx00DZPiwgaCx3DTSUicT3VpbCwMLpfQhgs\nU3iCmAmCmcsyAVVVcPbZcOmldVYAkRbY5qB4PUKorxIwxsSJBx+E0lK45ZaorC6QzUHuoY4PifwX\nz5/dmLg3Ywb85S8wffp2zwhq8c1BxhgTdzZsgOHD4dFHPT0ltDarBGKEtZWGxzKFL4i54jrTVVfB\nIYfAaadFZ30uqwQaKTMzk48//tjvGMaYlmTiRPjsM3jkkaiv2voEGqlnz548++yzHHnkkZ68f5A/\nuzHGAz//DPvvD1OmwH77hfUr1idgjDEtQWWlczXwddeFXQFEmlUCTaCq5ObmMnLkyJplhYWF9OjR\nw7N1xnVbaSNYpvAFMVfcZbr7bmjd2qkEfBLY6wSCzs7nN8Y0y9SpMG4cfP01JPi3Px6zlUCkyuBY\naX7Pzs72O8I2LFN4gpgJgpkrbjKtXQtnnAFPPAHdukX+/RshZiuBWCm8jTFmG5ddBsceC6ec4ncS\n6xNoqrS0NDZu3Fgzv3z5ck/XF3dtpU1kmcIXxFxxkenll2HmTGd4iACwSqCJsrKymDJlCqtXr2b5\n8uWMHTvW70jGmKD78Ue4+mqYMAHatPE7DeDxdQIicjNwJs4N5ucA56pqacjzMXudwMEHH8w555zD\ne++9R8+ePcnNzWXMmDEsWbKkWe8f5M9ujGmG8nI49FDnTmFXXdWst4rkdQKeVQIikgn8F+irqqUi\n8howRVVfCHlNzFUCXovnz25Mi/avfznNQO++2+wzW2LlYrF1QDnQRkSSgDbAbx6ur0WLi7bSCLBM\n4Qtirhab6ZNP4Lnn4PnnPb1LWFN4VgmoajHwILAEWAqsUdWPvFqfMcYEUnExnHWWUwnsuKPfabbh\n2SmiIrI7MALIBNYC/yciZ6jqK6Gvy83NJTMzE4D09HSysrK8ihRzqvdAsrOzyc7O3mq+9vN+zFcv\nC0qe2ntsQckT1PnqZUHJ0yK/P1Wyx42DIUMoTEmBJm7vwsJC8vLyAGrKy0jxsk/g78AxqnqBO38W\ncKCqXhbyGusTqCWeP7sxLc6zzzojg06bBikpEXvbWOkT+B44UERSxRlj4Whgrofra9Fq7yUFgWUK\nTxAzQTBztahM8+fDTTc5p4NGsAKINC/7BL4BXgRmALPdxU95tT5jjAmM0lLnVNA77oC99vI7zXbZ\n/QQCJp4/uzEtxvXXww8/wOuve3I2UCSbg2J27CBjjAmkDz+EV1+FWbMCdzpoXWzYiBjRotpKPWSZ\nwhfEXDGf6Y8/IDcX8vKgc2ePEkWWVQLGGBMJqnDeec41AUcd5XeasFmfgIcqKipISmpci1tL+ezG\nxJ1x45wjgP/9z7lbmIdi5RTRFmvWrFkMGDCA9u3bc/rpp3P66aczcuRICgsL6d69O/fddx9du3bl\n/PPP9zuqMSYavv0WRo2C8eM9rwAizSqBRiorK+OUU07hnHPOYfXq1Zx66qlMnjwZEUFEWLFiBatX\nr2bJkiU8+eSTEVtvzLeVRollCl8Qc8Vkpk2bnNNB77sPevWKSqZIitmzg+T2yPS6622Na3r58ssv\nqaio4Cp3KNicnBz233//mucTEhK4/fbbadWqFa1atYpIRmNMgN14o3MtQG6u30maJGYrgcYW3pGy\ndOlSutW6J+iuu+5a046/ww470NqDw8HQ8V6CwjKFJ4iZIJi5Yi7Tu+/CW2/FzOmgdbHmoEbq2rUr\nv/229YjYP//8M+L+AUiM/iEYYxpp2TK44AJ46SXo2NHvNE1mlUAjHXTQQSQlJfHII49QXl7O5MmT\nmT59OoCnZ/XEZFupDyxT+IKYK2YyVVU5zT8XXeTcLSyGWSXQSK1atWLy5Mnk5eXRqVMnJk6cyJAh\nQ1DVms5hY0wLN3YsrF8PI0f6naTZ7DqBCDj33HPp3r07d9xxR7PfK9Y+uzFxZ9YsOPZYZ3jonj19\niWDXCQSMFdrGxImSEud00Icf9q0CiDSrBCIgGs1AMdNW6jPLFL4g5gp8pquvhkGDnIqghYjZU0SD\n5Pnnn/c7gjHGa/n58PHHUFTkd5KIsj6BgInnz25MYP3yC+y3n3NNwKBBfqeJnT4BEekjIrNCprUi\ncqWX6zTGmIiqrISzz4arrgpEBRBpnlYCqjpfVfuran9gILAReN3LdbZUgW8rDQjLFL4g5gpkpksu\ncYaJvvFGv6N4Ipp9AkcDP6rqL1FcpzHGNN20aTBpEsyeDYmJfqfxRNT6BETkOWCGqj4Wssz6BGqJ\n589uTKCsXw/9+8O990JOjt9pthJz9xgWkdbAicA2x1O5ublkZmYCkJ6eTlZWVjQi+Wrx4sXstttu\nVFRUkJBQf4tc9aFx9QBWNm/zNh/F+aFDYc89yXYrAD/zFBYWkpeXB1BTXkaMqno+AScD/6ljudal\nvuUtxaJFi1REtLKycpvn6vvsBQUFHqdqPMsUniBmUg1mrsBkeuUV1T59VDdsCE6mEG45EZHyOVp9\nAsOACVFalzHGNN2iRTBiBLz/PqSl+Z3Ge5GqTeqbgDRgJdCujue2V8sF1ujRo7Vbt27arl077dOn\nj77yyiuampqqxcXFNa+ZOXOmdu7cWSsqKrSiokKvvfZa7dy5s+6222766KOPNvpIwBgTBeXlqoMH\nqz74oN9JtotYOhJQ1RKgs9friZb58+czbtw4ZsyYwU477cSSJUuoqKhg8ODB5Ofnc8EFFwAwfvx4\nTj31VBITE3niiSd49913KSoqok2bNgwZMsRGGzUmiO64A9q1c44E4kTsjh0kEpmpkRITEyktLeW7\n776jvLycXXbZhd12243hw4czYYLT4qWqvPbaawwfPhyAiRMncvXVV9OtWzc6duzILbfc0ugzgKo7\niYLEMoUniJkgmLl8zfT55/DUU5CXBwlbisYgbqdIit1KQDUyUyPtsccejB07llGjRrHjjjsybNgw\nli1bxpAhQ5g6dSrLly/n008/JSEhgUMOOQSAZcuW0aNHj5r32GWXXSK2GYwxEbBmDZx5Jjz9NHTt\n6neaqLKxg5ph/fr1XHzxxSQlJfHiiy9yyimncMQRRzB37lwyMjK45557ADjyyCP5+9//zsUXXwzA\nhx9+yLHHHlvnKaKx8tmNaTFU4fTToUsX+Pe//U4Tlpi7TqAlWbBgAb/++isHH3wwycnJpKSk1BTa\nw4cPZ/To0SxZsoSCgoKa3znttNN45JFHOOGEE2jTpg2jR4/2K74xprYXXoC5c51moDgUu81BPikt\nLeXmm29mhx12oGvXrqxcubJmj/+kk05i4cKFdO3alX79+tX8zoUXXsixxx7Lvvvuy3777UdOTk6j\nO4aD2C5pmcITxEwQzFxRz/TDD3D99TBhAqSmBiNTlNmRQCP169ePadOm1flcSkoK69at22Z5YmIi\nY8aMYcyYMTXLLr30Us8yGmPCUFYGw4fDqFGwzz5+p/GN9QkETDx/dmOi6qab4LvvnHsExNgp29Yn\nYIwxzfHxx/DSS85dwmKsAog06xOIEUFsl7RM4QliJghmrqhkWrkSzjnH6QjeYYcGXx7E7RRJVgkY\nY+KHKlxwgXNK6DHH+J0mEKxPIGDi+bMb47knn3SmqVMhOdnvNE0WyT4BqwQCJp4/uzGemjsXDj/c\nGR6iTx+/0zRLzNxovjlEJC6n+gSxXdIyhSeImSCYuTzLtHmzczroPfc0ugII4naKpEBWApEaIrWp\nU0FBga/rN8ZE2M03wx57wPnn+50kcALZHGSMMRHz3ntw8cXO6aAZGX6niQi7TsAYY8KxYoWz9z9h\nQoupACLN0+YgEUkXkUkiMk9E5orIgV6uL1KC2AZomcJjmcIXxFwRzVRVBbm5cN55TodwEwVxO0WS\n10cCDwNTVHWoiCTh3GrSGGO89+9/w+rVcNttficJNM/6BESkAzBLVXfbzmusT8AYE3nffANHHw3T\npsFu9RZBMStWThHtCfwhIs+LyEwReVpE2ni4PmOMgY0bYdgwGDOmRVYAkeZlc1ASMAC4XFWni8hY\n4Cbg1tAX5ebmkpmZCUB6ejpZWVlkZ2cDW9rioj1fvcyv9dc1Xzub33kAxo4dG4jvK3S+qKiIEe5N\nwoOQp1rQ/p6gBX9/EydC//4Udu8OhYUt4vsrLCwkz73pTXV5GTEenuu+E7AoZP4Q4J1ar9EgKigo\n8DvCNixTeCxT+IKYq9mZ3nhDtWdP1TVrIpJHNZjbyS07I1JWe3qdgIh8ClygqgtEZBSQqqo3hjyv\nXq7fGBNHfvsNBg6E11+HwYP9TuOpmBk7SET2BZ4BWgM/Aueq6tqQ560SMMY0X1WVMypodjaMHOl3\nGs/FSscwqvqNqu6vqvuq6pDQCiDIQtsCg8IyhccyhS+IuZqc6YEHoLwcbrklonkgmNspkuyKYWNM\nbJsxw6kEZsyAxES/08QcGzvIGBO7NmyA/v3hrrvgtNP8ThM1UesTEJGBQEOldLmqzmnSyq0SMMY0\nx3nnOfcIfvZZv5NEVTT7BAqBBxuY3o5EkCAJYhugZQqPZQpfEHM1KtNrrzk3iHn4Yc/yQDC3UyQ1\n1CcwQ1WP2N4LRKQggnmMMaZhP/8MV1wBU6ZA27Z+p4lp1idgjIktlZXOqaAnngg33OB3Gl9E/RRR\nETlERNq6j88SkYdEZNdIBDDGmEa5+25o3Rquu87vJC1CuNcJPA6UuBd/XQMsBF70LJXPgtgGaJnC\nY5nCF8RcDWb64gsYNw5efBESonN33CBup0gKdytWuO02pwDjVHUc0M67WMYYU8vatXDGGfDkk9Ct\nm99pWoyw+gTcMYD+A5wLHAr8ARSpar9mrdz6BIwx4VB1KoD0dHjsMb/T+M6Pewz/HRgGnKeqy0Vk\nF+D+SAQwxpgGvfyyc6OY6dP9TtLihNUcpKrLVHWMqn7mzi9RVesTiCLLFB7LFL4g5qoz048/wjXX\nODeLbxP9+1IFcTtF0nYrARF5p6E3COc1xhjTJOXlMHy4MzLon/7kd5oWqaFhI9YCnzbwHvuoas8m\nrdz6BIwx2/PPf8KsWfDuu87wEAaIbp/AyWG8R2kkghhjzFYKC+H556GoyCoAD223OUhVC8OYpm7v\nPURksYjMFpFZIvJVZON7I4htgJYpPJYpfEHMVZOpuBjOPhueew66dAlGphYqGvcTUCBbVYujsC5j\nTKxThQsvhJwcOO44v9O0eJ6PHSQii4D9VHVVHc9Zn4AxZmvPPAOPPgrTpkFyst9pAsmXewyLSBug\nh6rOb9QKRH4C1gKVwJOq+nTIc1YJGGO2+P57OPRQ+OQT2Gsvv9MElh8DyJ0EzALed+f7i8hbYa7j\nYFXtDxwPXCYihzYpaRQFsQ3QMoXHMoUvcLlKSyk88US4885AVQCB204RFm6fwChgEFAAoKqzRGS3\ncH5RVZe5P/8QkdeBA4DPqp/Pzc0lMzMTgPT0dLKyssjOzga2bPxoz1fza/2xMl9UVBSoPIWFhRQV\nFQUqT6ig5Ans93f22RSlpJB90UXByBOg76+wsJC8vDyAmvIyUsIdO2iaqg4SkVnuXj0iMltVt3v1\nhtuElKiq60UkDfgAuF1VP3Cft+YgYwx88AGcf75zOminTn6nCTw/xg76TkTOAJJEpBdwJfBFGL+3\nI/C6OOf4JgGvVFcAxhgDwO+/w7nnwksvWQXgg3CHkr4C2BvnwrAJwDpgREO/pKqLVDXLnfZR1Xua\nHjV6ah8GBoFlCo9lCl8gcqk6RwBnnw1HHhmMTLUEMVMkhXUkoKolwC3uZIwxkfHYY7B8OeTn+50k\nboXbJ7A/TgWQyZaKQxvqEwjjfa1PwJh49e23cMQRzt3CevXyO01M8aNP4BXgOuBboCoSKzbGxLFN\nm2DYMLj/fqsAfBZun8AfqvqWqv6kqourJy+D+SmIbYCWKTyWKXy+5rrhBth7bzjnnK0WB3FbBTFT\nJIV7JHC7iDwLfASUuctUVSd7E8sY02K98w68/baNDhoQ4fYJvAL0Ab4jpDlIVc9t1sqtT8CY+LJs\nGfTvD5MmwSGH+J0mZvnRJ7AfsKeV2MaYJquqcpp/LrnEKoAACbdP4AsgOIN5eCyIbYCWKTyWKXxR\nz/XQQ1BSAv/6V70vCeK2CmKmSAr3SGAwUOQOC119J7FmnyJqjIkTM2fCvffCV19BUjRuY2LCFW6f\nQGZdy5t7hpD1CRgTB0pKYMAAGDXKOS3UNFvU7icgIu1VdZ2IZNT1fHPvFmaVgDFx4KKLoLQUXnjB\n7yQtRjTvJzDB/TkT+LqOqUUKYhugZQqPZQpfVHLl58N//+vcKSwMQdxWQcwUSdttnFPVv7o/M6OS\nxhjTcvzyC1x6qXNNQLt2fqcx9Qi3T+BjVT2qoWWNXrk1BxnTMlVWwlFHwbHHws03+52mxYnadQIi\nkgq0AXao1S/QHugWiQDGmBbo3nudq4FvuMHvJKYBDfUJXAzMwLlaOLQv4C0gvEa+GBTENkDLFB7L\nFD7Pck2bBg8/7NwkJjExGJmaIYiZIqmhPoGxwFgRuVJVH2nKCkQkEaci+VVVT2zKexhjYsS6dTB8\nODz+OHTv7ncaE4aw+gSatQKRa4CBQDtVPanWc9YnYExLcvbZkJoKTz7pd5IWLZqniDaLiHQH/gI8\nA9hwgca0ZK+8AtOnw5gxficxjeBpJQA8BFxPjN2IJohtgJYpPJYpfBHNtWgRjBgB48dDWlowMkVI\nEDNFUkNnBw0E6m2vUdWZ2/ndE4DfVXWWiGQ3OaExJtgqKuCMM5xTQfv39zuNaaSGRnJ6kO1UAsAR\n23nuIOAkEfkLkAK0F5EXVfXs0Bfl5uaSmZkJQHp6OllZWWRnZwNbamCbzyY7OztQeaoVFhYGJk/t\nPbag5AnqfPWyZr9fQQG0a0dhVhZE4P1Cs3n5+WNpvrCwkLy8PICa8jJSPO8YBhCRw4Hrap8dZB3D\nxsS4zz6D006DWbNgp538ThM3otYxLCI5IjKkvqmR64qZ0r72HkkQWKbwWKbwNTvX6tVw5pnwzDMR\nqwCCuK2CmCmSGmoOOpHtF95h3WNYVT8BPgk3lDEm4FSdO4SdfDL89a9+pzHNEJXmoHpXbs1BxsSm\n5593TgWdPh1SUvxOE3eidj+BWis9AecWkzXfuKr+v2at3CoBY2LPggVw8MFQUAD77ON3mrgU9YvF\nRORJ4DTgSpyLvk4Ddo1EgCAKYhugZQqPZQpfk3KVlTnDQtx+uycVQBC3VRAzRVK4F4sd5J7aWayq\ntwMH4gwqZ4yJJyNHws47wz/+4XcSEyHh3k/gK1U9QES+BHKAVcC3qrpHs1ZuzUHGxI6PP3bGBioq\ngh128DtNXIva/QRCvCMiHYH72XJbyacjEcAYEwNWroRzzoG8PKsAWpiGrhO4WkQOAO5W1dWqmg9k\nAnuq6shoBPRDENsALVN4LFP4ws6lChdcAMOGwTHHBCNTFAUxUyQ1dCTQHRgL9BWROcDnwBfuZIyJ\nB08+6dwveOJEv5MYD4TbJ5AM7AcMxhkTaDCwRlX7Nmvl1idgTLDNnQuHHw6ffw597FyQoPCjTyAV\n577CHdxpKTA7EgGMMQG1ebPTBDR6tFUALVhDfQJPi8j/gFdx9v6/AIaq6kBVPTcaAf0QxDZAyxQe\nyxS+BnPddBP07g3nnReVPBDMbRXETJHU0JHALkAy8APwmzut8TqUMcZnU6bA6687p4OK3RSwJWuw\nT0BEEoC92dIf0A/nOoEvVfXWZq3c+gSMCZ4VKyArC157DQ47zO80pg5+jR3UA6cSOBg4Aeikqh2a\ntXKrBIwJlqoqZ1TQ/faDO+7wO42pRzTvJ3CViLwmIktwhoI+EZgH/A3IiESAIApiG6BlCo9lCl+d\nuR55xLlPwK3NOshvsiBuqyBmiqSG+gQygYnA1aq61Ps4xhjfFBXBXXfBtGnQqpXfaUyUeHo/ARFJ\nwTmCSAZaA2+q6s0hz1tzkDF+U4WXXoLrroNHH3VuF2kCzY/rBJpEVTeLyBGqulFEkoDPReQQVf3c\ny/UaY8L0xx9w8cWwcCF8+CHsu6/fiUyUhTuUdJOp6kb3YWsgESj2ep3NFcQ2QMsUHssUvsI774Q/\n/cm5FmD69EBUAEHcVkHMFEmeHglAzSmmM4HdgcdVda7X6zTGbMfatTBiBLz/Pvzf/8Ehh/idyPjI\n80pAVauALBHpALwvItmqWlj9fG5uLpmZmQCkp6eTlZVFdnY2sKUGtvlssrOzA5WnWmFhYWDy1N5j\nC0qeQM3PmkX2ww/D8cfDs89SWFGB82xA8oUISp4gzBcWFpKXlwdQU15GSlRvNC8iI4FNqvqAO28d\nw8ZEw6ZNcMstzp7/0087lYCJWVG/x3BTiUhnEUl3H6cCxwCzvFxnJNTeIwkCyxQey1SH6dNhwABY\nvhxmz66pAHzPVQfLFH1eNwd1BV5w+wUSgJdU9WOP12mMASgvd877f/xxePhhOP10vxOZAIpqc9A2\nK7fmIGO8MW8enHUWdOkCzzzj3BzetBgx0xxkjImyqip46CFn4LeLLoJ337UKwGyXVQJ1CGIboGUK\nT1xnWrwYjjoK8vPhyy+dSmA7w0DH9bZqhCBmiiSrBIyJdarw/POw//5Op+8nn8Duu/udysQI6xMw\nJpatWOHs8f/8szP+T79+ficyUWB9AsYYmDzZGephn33gq6+sAjBNYpVAHYLYBmiZwhMXmdasgbPP\nhhtvdG4Beddd0Lq1/7kiwDJFn1UCxsSSjz5yBn1r184Z/3/wYL8TmRhnfQLGxIKNG+Gmm5w9/2ef\nhT//2e9ExkfWJ2BMPJk2Dfr3h+JiZ9gHqwBMBFklUIcgtgFapvC0qExlZTByJJx0Etx5J7z8MnTs\n6H8uD1mm6PN8KGljTBN8950z7MPOOztt/127+p3ItFDWJ2BMkFRWwtixMHo03HMPnH/+dq/6NfEp\nZu4xbIxphEWL4JxznMdffQU9e/qbx8QF6xOoQxDbAC1TeGIyk6oz0ucBB8DJJ0NBQVQqgJjcVj4I\nYqZIsiMBY/y0fDlccAEsXeoU/vvs43ciE2esT8AYv0yaBJdfDhde6JwF1ISrfk18ipk+ARHpAbwI\ndAEUeEpVH/FyncYE3urVTuE/Ywa8+SYMGuR3IhPHvO4TKAeuVtW9gQOBy0Skr8frbLYgtgFapvAE\nPtMHHzjDPnTqBLNm+VoBBH5bBUQQM0WSp0cCqrocWO4+3iAi84CdgXlerteYwCkpgRtugLffdsb+\nP/povxMZA0SxT0BEMoFPgL1VdYO7zPoETMs3daoz6ufgwfDII5Ce7nciE0OqtIqVG1fSJa1LzbKY\n6ROoJiJtgUnAVdUVQLXc3FwyMzMBSE9PJysri+zsbGDLYZjN23xMzn/4IeTlkf3xx/DYYxRmZEBR\nUXDy2Xxg5yurKvn3xH/zyeJP+Kr1V+xdsjc7/+jcK7q6vIwYVfV0AloB7wMj6nhOg6igoMDvCNuw\nTOEJTKZvvlHdd1/VE0/Ugvx8v9PUKTDbKkQ8ZyqrKNP3F76vF751oXa5v4sOeHKA3vXpXfr9H99v\n81q37IxIGe312UECPAvMVdWxXq7LmECorIQHH4T774f77oPcXOeev8bUYXPFZj788UPy5+Xz9oK3\n6d2pNzl9c/jy/C/p2TE6V4x72icgIocAnwKzcU4RBbhZVf/jPq9ert+YqPrxR2fYh6QkyMuDSB+2\nmxahpKyE/yz8D5PmTeK9H95j3532ZWjfofyt79/o3r57WO8RyT4Bu1jMmOZShaeegn/+E/71L7jy\nSkiwEVnMFutK1/HOgnfIn5fPRz99xKBug8jpm8Mpe57Cjm13bPT72U1lPFbdQRMklik8Uc+0dCn8\n5S/w9NPw6acwYsQ2FUAQtxMEM1dLylS8qZi8ojxOnHAiPR7qwfg54zmh1wn8dOVPfHDWB1y838VN\nqgAizcYOMqapXnvN2ev/xz+co4BWrfxOZHy2YsMK3vj+DfLn5TPtt2kcvdvRDNtnGC//7WU6pHTw\nO16drDnImMYqLobLLnNu9vLii7D//n4nMj76bd1vTJ43mfx5+RQtL+L4XseT0zeH4/c4nrTWaZ6s\nM+auEzCmxXjvPWfAt1NPhZkzITXV70TGB4vXLCZ/bj758/KZv2o+J/Q+gWsGX8Ofd/8zKUkpfsdr\nFOsTqENLapf0Ulxl2rABLrnEmV58ER56KOwKIIjbCYKZK8iZ5q+cz92f3c3ApwZywNMHMH/VfG47\n/DaWXbuMF055gZP6nBRzFQDYkYAxDfvf/5xhHw47DGbPhg7BbNs1kaWqfPv7t+QV5XHFvCtYtXEV\nQ/oO4YFjHuDQXQ8lKaFlFJ/WJ2BMfUpL4dZbnT3/xx+HU07xO5HxmKoyc9lM8uflM2nuJEorS8np\nm8PQvYYeIXEqAAAVj0lEQVRyYPcDSZBgNJ5Yn4AxXisqcvb+d98dvvkGunRp+HdMTKrSKr789Uvy\n5+Yz+fvJJCUkMbTvUMbnjGdg14E4Ax+0XMGo1gImyO2SQdIiM1VUwD33wDHHwHXXweTJza4Agrid\nIJi5opWpsqqSwsWFXDHlCno81IOL3r6Itq3b8ubpb7Lg8gXcc/Q97LfzfohIILdTJNmRgDHVfvjB\nGfYhNRW+/hp22cXvRCaCyivLKVhcwKS5k3jj+zfo3r47Q/cayn/P/i99OvfxO55vrE/AGFWnzf/W\nW53p8stt2IcWor4B2ob0HcJuHXfzO16T2dhBxkTKr7/C+ec79/198UXYc0+/E5lmqmuAtuqCP9wB\n2oLOxg7yWBDbAC1TeMLOpAqvvAIDBsAhh8AXX3hWAQRxO0EwczU107rSdYyfM56ciTnsPGZnnvj6\nCbJ3zWb+5fP5JPcTrhx0ZZMrgCBup0iyPgETf1audMb7+e475wrggQP9TmSaoHhTMW/Nf4v8efl8\nsvgTDtv1MHL65vDUCU/RqU0nv+PFDGsOMvFj3Tqnyeeee+D00+HOO23YhxhTe4C2o3oeRU7fHE7o\nfUJgB2jzgvUJGNMYc+fCuHEwYQIcfTRccw0ceKDfqUyY/BigLehipk9ARJ4TkRUiMsfL9URaENsA\nLVN4ajJVVEB+Phx5JBx1FHTuDHPmwMSJUa8AgridIJi5qjMtXrOYB794kIOePYh+j/djxrIZXDP4\nGpZft5wJORMYutfQqFUAQdxOkeR1n8DzwL+BFz1ejzGO4mKnmeeJJ6BnT+d0z7/9DVq39juZacD8\nlfN5efbLXLvgWn5Z+wsn9zmZ2w6/jSN6HkHrRPv+vOJ5c5CIZAJvq2q/Op6z5iDTfKowdSo8+qjT\n0Xvqqc54//vu63cysx3VA7Tlz3OGZK4eoC2nb06LGqDNCzZ2kDEAGzc67fyPPuoM9XzppU7bf8eO\nficz9ahvgLYn/voEg3sMDswAbfHE90ogNzeXzMxMANLT08nKyiI7OxvY0hYX7fnqZX6tv6752tn8\nzgMwduxYf76v7t3h8ccpfOYZ2GsvskePhmOOofDTTyl64QVGjBgRiO0T5L8niN73d9jhh/Hlr18y\ndsJYPl3yKe36tCOnbw7Xdr2W3p16c8QRR9S8vqioyL6/ev7/8/LyAGrKy4hRVU8nIBOYU89zGkQF\nBQV+R9hG3GeqrFR95x3V449X7dxZ9YYbVH/6yd9MYQpiJlVvc1VUVmjBogK9/N3LdecHd9a9x+2t\nt/73Vv1m+TdaVVXlS6amCmImt+yMSBltfQIm2IqL4bnnnLF9OnZ0Onr//nc7vz+AQgdoe3P+m3Rr\n142cvjnk7JXDnp1tOI5Iipk+ARGZABwOdBKRX4BbVfV5L9dpWoiZM532/cmT4cQTYfx4OOAAaOFj\nu8ea2gO09croRU7fHKaePzWmB2iLJ572wqjqMFXdWVWTVbVHrFQAoW2BQREXmUpLnfF8DjrIOa1z\njz1gwQLnKt9Bg8KqAOJiO0VIU3OVlJWQPzef4fnD2emBnXhg6gMM6DqAoouL+PKCL7n+4OubXAEE\ncVsFMVMk+d4xbAy//AJPPgnPPAP9+sENN8AJJ0CS/XkGxbrSdbyz4B3y5+Xz0U8fcUC3A8jpm8OY\nY8ewU9ud/I5nmsGGjTD+UIWCAuf0zsJCOPNM5xRPG8o5MGoP0HborocytO9QTupzkg3Q5jMbO8jE\nrnXr4KWXnPb+hASno/fMM6FtW7+TGeD3kt954/s3mDR3UlwP0BZ0Vgl4rLCwsOZc3aCI+Uy1B3G7\n7DI47LCId/TG/HaKkjWb1/Dq26/Srk87FqxawILiBcxfOZ+fVv/EcXsc5wzQ1ut42raObuUcxG0V\nxEwxc3aQiXMVFfDmm07hP28eXHSRM4hbt25+J4sLm8o3sbB4IT8U/+AU9CHTxvKNdF3ZlYEykN6d\nevPXXn9lxKAR/GnHP5Hayk6/jSd2JGAib8UKePppp7M3M9PZ6x8yxAZx80BFVQWL1yyuKdx/WPUD\nC4qdxys2rKBnx5707tSb3hm9nZ/utFPbnRA73TZmWXOQCZ7qQdzGjYMpU2wQtwhSVZauX7rVnnz1\n3v3iNYvp2q4rvTJ6bVXI9+7Um1067GKDsLVQVgl4LIhtgIHNdMABTjv/uHGwfr1zhk9urm+DuAV2\nO4WRqXhT8TbNNgtWLWBh8ULatm5bU7iHFvi7Z+xOSlKKp7miyTKFx/oEjP9+/NEZymHoUBg8GO6+\nG/78Z+eMH1OvkrISFhYv3FLIF28p7CuqKrbsyWf05pQ9T6kp9O3MHOMVOxIw4du40Tm3/7HH4Kuv\n4Lzz4JJLnJu3mBpllWUsWr1oq2ab6mnVplXs3nH3rZptqvfsu6R1sXb6OKQKmzbBmjVbT2vXbnnc\nvTucddaW37EjAeOtqipYvBhmz94yzZnjXNmbleWc5TNpUlwP4lalVfy67tc6O2R/WfsL3dp3q9mj\n79elHzl9c+jdqTfd23cnMSHR7/gmglSd21nUV4Bvb1n18sRESE/fMnXosPV8pEePDmVHAnUIYhug\nZ5nWrHEK+NAC/9tvnTb9P/1p66lXL2jVyvtMzRDJTKrKyo0r6+yQXVi8kI6pHevskO2Z3pPkpGRP\nMkVSEHP5kamqyrmGsb6CetasQjIysustwNeuhZSU+gvw7S3v0MGZUhrZrWNHAqbxysudwdhqF/ir\nV8M++2wp6M8805mPo7tzrS9dv02zTfU8QJ9OfejVqRe9M3pz6l6n0rtTb/bI2IN2ye18Tm7AuRyl\nujBuzN539eP1650L1usrqCsrnUtb9t677kK9Q4et9o1ijh0JtDSqznn6oc04s2fD/PnQo4czQFvo\n3n1mZovtzK2sqmRt6VpWbVxF8aZiVm1yfi5bv2yrTtm1m9c6hbzbfFPzuFNvOqV2snZ6j5WVNb0A\nX7PG6apq3z78ve/ay9u3d5pjYomdImocmzY5wzHULvArK53z80ML/L33hjZt/E7cJKrKutJ1NYV4\n7UJ91cZVFG/edvnazWtpl9yOjNQMOqV2cn626cSOaTtu1SHbrX03u7dtM2ze3LTCu3oqK2t6AZ6e\n7uzFt9D9mHrFTCUgIscBY4FE4BlVvbfW84GsBALVVur2OhW+9RbZ7dptXeAvXgy9ezuFfGiB37Vr\nVG6+0tjtpKqUlJfUXYiHztdavnrzalKTUunUptNWBXrtwj0jNYOfi37m6COPplObTqSnpAfiYqlA\n/T3h/ElVVMCHHxay//7ZbN7sFOSbNm3bwRlOoV5V5bQehtP+XVeh3qbNlj/XoG0rCGammOgTEJFE\n4FHgaOA3YLqIvKWq87xaZ6QUFRV596WrOr1Qf/yxZfr9963nay9LTKQoOZnsAw90CvuTT4aRI6FP\nH9+GYthUvonCqYVk9M1ocO+8elnxpmKSEpK2Kbir57u160a/Lv3qLOxbJYbX6Dp2ylj6dO7j8adv\nnLr+niorqSl8w502bYrc7yQkgEgRHTpkk5LidEwmJ0O7dtsW0hkZzlnA9e2Vp6REbp/D0/+9Jgpi\npkjycjfpAGChqi4GEJFXgZOBwFcCa9asCe+FVVVQUrJ1r1RDBfvKlU7BvcMO0KWL87N62nlnpxmn\n9nNt2rBm1CgYNarRn6WyqpKS8hJKykooKS9hQ9mGmsfbW1bf8vWl6yneVEyVVtHqs1bkp+dvKdTd\nn53bdK5pTw8t7DNSM5p8dWu4wv3uVJ0bmUWqwN3e63/7bQ1jxmy9rKKCmsK3ekpN3XbZ9qYOHRr/\nO9VTUhKMGrWmKX9Sngr7fy+KgpgpkrysBLoBv4TM/woM8nB9W6v+Ly8tdRody8udqfpxXctKS53C\nfPp0GD16S+Fe37R+PZqa6p7n1Z6qDh2o6tyJqk4ZVHbOoGLHjpT3zaSsUzplGR0ozWhPacf2lLdO\npKKqos6pvLKciqpNVFT9SMXa+VSsdpbPWDqDMVPHhBTcTsFcXVBvCCmsN5aXsKF8AxvLSyivKic1\nqQ1tktJIa9WW1KQ02iSlkZqURmpiGm2S2pKamEZKYpr7syMdEnuwY0IayWlppLZLIzkhjZSEtiQn\npJEsbWmb0InEqlSeX3A7w3uOoqLCKdQqyqByE1T87swXV8Dv1c+5U2Xl1vN1Tc15zdKl8Oqr23+P\n6q86OTm8ArO+gjYjI7zfefppuP76rZ9v1cpul2yCwctKIKzG/jmffc2yc45HFKr/J5zHWvMzQUFU\nSXSnhKotjxOrlOTKKpIrqkiurCKlspLkiipaVypliUJZYgLlCUJ5olCWIFSEPC5PxP0pVCRAaSKs\nS07ggxWbaLvyc9amwNpknJ9tqliboaxJqWJNchVrU6pYl6pUJpaAbgT9HdFEpKoVaBJSlQRrk2B1\nEvJDEmgSVLZCNAmq6p+0MvRxK+dxZRKVMxbw3q+90LI0tKwDlO0MZWlIeVukIo2EyjQSKtypMg2p\naEtyRRqpmkJigkACbEqA0gRYl+AUQAkJ25/qe01SkjPNn7+Y3393Hicmblle31TXa6r3SpvzHqHT\nbbctZvToht8nOTl6nYnr1y9ml12is67GWLx4sd8RtmGZos+zjmERORAYparHufM3A1WhncMiErxe\nYWOMiQGBPztIRJKA+cBRwFLgK2BYLHQMG2NMvPCsOUhVK0TkcuB9nFNEn7UKwBhjgsXXi8WMMcb4\ny7fr7ETkOBH5XkR+EJEbo7jeHiJSICLfici3InKluzxDRD4UkQUi8oGIpIf8zs1uzu9F5M8eZksU\nkVki8nYQMolIuohMEpF5IjJXRAYFINPN7nc3R0TGi0iyH5lE5DkRWSEic0KWNTqHiAx0P8sPIvKw\nB5nud7+/b0Rksoh0CHnOl0whz10rIlUikhGETCJyhbutvhWR0L5Lv767A0TkK7dMmC4i+3uSSVWj\nPuE0Dy0EMoFWQBHQN0rr3gnIch+3xem36AvcB9zgLr8RGO0+3svN18rNuxBI8CjbNcArwFvuvK+Z\ngBeA89zHSUAHPzO57/sTkOzOvwac40cm4FCgPzAnZFljclQfhX8FHOA+ngIcF+FMx1R/ZmB0EDK5\ny3sA/wEWARl+ZwKOAD4EWrnzOwQgUyFwrPv4eKDAi0x+HQnUXEimquVA9YVknlPV5apa5D7egHPx\nWjfgJJxCD/fnKe7jk4EJqlquzoVvC938ESUi3YG/AM+w5WxZ3zK5e4yHqupz4PTxqOpaPzMB64By\noI04Jx60wTnpIOqZVPUzYHWtxY3JMUhEugLtVPUr93UvhvxORDKp6oeqWuXOTgO6+53JNQa4odYy\nPzP9A7jHLY9Q1T8CkGkZzo4XQDrOyAsRz+RXJVDXhWTdoh1CRDJxat9pwI6qusJ9agWwo/t4Zzdf\nNa+yPgRcD1SFLPMzU0/gDxF5XkRmisjTIpLmZyZVLQYeBJbgFP5rVPVDPzPV0tgctZf/5nG+83D2\nDn3NJCInA7+q6uxaT/m5nXoBh4nIlyJSKCL7BSDTTcCDIrIEuB+42YtMflUCvvdGi0hbIB+4SlXX\nhz6nzrHU9jJGNL+InAD8rqqz2HIUsPUKo5wJp/lnAPCYqg4ASnD+KH3LJCK7AyNwDoF3BtqKyJl+\nZqp3JQ3niCoR+SdQpqrjfc7RBrgFuC10sU9xQiUBHVX1QJydsYk+5wF4FrhSVXcBrgae82IlflUC\nv+G0CVbrwdY1mKdEpBVOBfCSqr7hLl4hIju5z3cFfq8na3e2HJZFykHASSKyCJgAHCkiL/mc6Vec\nvbXp7vwknEphuY+Z9gO+UNVVqloBTAYG+5wpVGO+r1/d5d1rLY94PhHJxWlqPCNksV+ZdsepxL9x\n/967A1+LyI4+ZsJdz2QA92++SkQ6+5zpAFV93X08iS1NmZHN1NSOjOZMOLXujzh/DK2Jbsew4LSV\nPVRr+X3Aje7jm9i2A601ThPJj7idMB7lOxx4OwiZgE+B3u7jUW4e3zIB+wLfAqnu9/gCcJlfmdy/\n39odw43KgdMUOcj9PM3qXKwn03HAd0DnWq/zLVOt5+rqGPZjO10M3O4+7g0sCUCmmcDh7uOjgOle\nZIpoodHID3w8zpk5C4Gbo7jeQ3Da3YuAWe50HJABfAQsAD4A0kN+5xY35/e4vfUe5jucLWcH+ZoJ\np9CdDnyDs5fUIQCZbsAp1ObgVAKt/MiEc8S2FCjD6d86tyk5gIHuZ1kIPBLhTOcBPwA/h/ytP+ZT\nptLq7VTr+Z9wKwE/M7l/Ry+56/gayPb5uzsX58h3Gk5ZNRXo70Umu1jMGGPiWJzdlM0YY0woqwSM\nMSaOWSVgjDFxzCoBY4yJY1YJGGNMHLNKwBhj4phVAsYYE8esEjDGmDhmlYAJNPemIy+FzCeJyB/i\n3ninnt/pICL/aOB9/xeBbM1+D2P8ZpWACboSYG8RSXHnj8EZLGt7l7p3BC6t6wlxqerBzQ0Wifcw\nxm9WCZhYMAX4q/t4GM44KwIgIm+IyAz3loAXuq8ZDezu3pbvXhHZVUTmi8gLwGygh4hscH9/f/fW\ni8kikua+z16hK3eXvysiRe6t+051l1e/xyXuumaJyCIR+a+7/EwRmeYuf0JE7P/NBI6NHWQCTUTW\n4wy1fStwJvAlzj0FrlPVE0Wko6quFpFUnFvrHQa0B95R1X7ue2TijLQ4WN27LonIelVt5z6+A0jB\nGZ30F1W9NyQCIpKDM0jXRe58O1VdH/oe7vIk4L/AvTgDo90L/E1VK0XkMWCqqr5U670PBXKAT9xF\ne6vqnc3ecMaEKcnvAMY0RFXnuAX5MODdWk9fJSLVt9DrjnOHqN/Z1s+65bZ7tf0/YAawCbiijudn\nAw+IyGicyuXzet7nEeBjVX1XRC7HGdFxhoiAU8Esr+vjuT9/VdXp7l23jIkaqwRMrHgLeABnqO0d\nAETkcJxx1g9U1c0iUoCzR1+Xku28d2cgDUjEKaw3hj6pqj+ISH+cJqk7ReRjVb0j9DXujVt6qGpo\nX8QLqnrL9j6Uqn4uIje6FUAHnIrImKixNkoTK54DRqnqdyHLOgCr3QpgT+BAd/l6oF3tN9iOJ4F/\nAeNxmnC24t4lbLOqvoJTEfWv9fxA4FrgrJDFHwNDRaS6wsoQkV3qeO9UYLM7ezwwRUSsw9lEjR0J\nmKBTAFX9DXg0ZJkC/wEuEZG5ODcomuq+dpWI/E9E5uB0Kj/GtmcTObeZEzkbKFXVV92O2y9EJFtV\nC0Ne2w+4X0SqgHLgktD3AC7HOSOpwG36ma6qF4nIv4AP3PctxzljaUmtHHuzpT9gA7Arzt3TjIkK\n6xg2xpg4Zs1BxhgTx6wSMMaYOGaVgDHGxDGrBIwxJo5ZJWCMMXHMKgFjjIljVgkYY0wcs0rAGGPi\n2P8HjaciA9mJ77QAAAAASUVORK5CYII=\n", "text": ["<matplotlib.figure.Figure at 0x7f846dcafe48>"], "metadata": {}, "output_type": "display_data"}], "input": ["for name, f in [\n", "        (\"lu\", spla.lu_factor),\n", "        (\"qr\", npla.qr),\n", "        (\"svd\", npla.svd)\n", "        ]:\n", "\n", "    times = []\n", "    print(\"----->\", name)\n", "    \n", "    for n in n_values:\n", "        print(n)\n", "\n", "        A = np.random.randn(n, n)\n", "        \n", "        start_time = time()\n", "        f(A)\n", "        times.append(time() - start_time)\n", "        \n", "    pt.plot(n_values, times, label=name)\n", "\n", "pt.grid()\n", "pt.legend(loc=\"best\")\n", "pt.xlabel(\"Matrix size $n$\")\n", "pt.ylabel(\"Wall time [s]\")"], "cell_type": "code", "language": "python", "metadata": {}, "prompt_number": 9}, {"metadata": {}, "source": ["* The faster algorithms make the slower ones look bad. But... it's all relative.\n", "* Is there a better way of plotting this?\n", "* Can we see the asymptotic cost ($O(n^3)$) of these algorithms from the plot?"], "cell_type": "markdown"}]}], "nbformat": 3, "metadata": {"signature": "sha256:dd647001ebaddd506724da15254ee7030118777ace4023bbbc9865723cbff646", "name": ""}, "nbformat_minor": 0}