00. np_eigen_decomposition.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import numpy.linalg as la\n",
    "from numpy.linalg import eig\n",
    "from numpy.linalg import inv\n",
    "\n",
    "import time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Eigenvector and Eigenvalues"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 4,  0, -2],\n",
       "       [ 2,  5,  4],\n",
       "       [ 0,  0,  5]])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# diagonalization and power of a matix\n",
    "A = np.array([(4, 0, -2), (2, 5, 4), (0, 0, 5)])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "eig_val, eig_vec = eig(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5. 4. 5.]\n"
     ]
    }
   ],
   "source": [
    "print(eig_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.          0.4472136  -0.89442719]\n",
      " [ 1.         -0.89442719  0.        ]\n",
      " [ 0.          0.          0.4472136 ]]\n"
     ]
    }
   ],
   "source": [
    "print(eig_vec)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[5., 0., 0.],\n",
       "       [0., 4., 0.],\n",
       "       [0., 0., 5.]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V = eig_vec\n",
    "D = np.diag(eig_val)\n",
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 4.,  0., -2.],\n",
       "       [ 2.,  5.,  4.],\n",
       "       [ 0.,  0.,  5.]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# check V*D*V(-1) = A  \n",
    "V.dot(D).dot(la.inv(V))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Computing matrix multiplication "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1024,     0, -4202],\n",
       "       [ 4202,  3125,  8404],\n",
       "       [    0,     0,  3125]])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "la.matrix_power(A, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[3125.,    0.,    0.],\n",
       "       [   0., 1024.,    0.],\n",
       "       [   0.,    0., 3125.]])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D_power5 = np.diag(eig_val**5)\n",
    "D_power5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1024.,     0., -4202.],\n",
       "       [ 4202.,  3125.,  8404.],\n",
       "       [    0.,     0.,  3125.]])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V.dot(D_power5).dot(la.inv(V))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same result with original A^5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Computation Time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.25       0.125      0.25       0.375     ]\n",
      " [0.11764706 0.05882353 0.29411765 0.52941176]\n",
      " [0.15384615 0.19230769 0.42307692 0.23076923]\n",
      " [0.19354839 0.29032258 0.19354839 0.32258065]]\n"
     ]
    }
   ],
   "source": [
    "A = np.array([(4, 4, 2, 3), (0, 1, -2, -2), (6, 12, 11, 2), (9, 20, 10, 10)])\n",
    "# preprocess for error\n",
    "A = A + A.T\n",
    "A = A/np.expand_dims(np.sum(A, 1), axis = 1)\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.2093077  0.33193195 0.8360054  0.10730763]\n"
     ]
    }
   ],
   "source": [
    "n_times = 100000\n",
    "\n",
    "# initialize parameters\n",
    "x = np.random.rand(4)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "eig_val, eig_vec = eig(A)\n",
    "D = np.diag(eig_val)\n",
    "V = eig_vec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# perform matrix multiplications in eigendecomposition way\n",
    "start_time = time.time()\n",
    "\n",
    "y_1 = V.dot((eig_val**n_times)*la.solve(V, x))\n",
    "\n",
    "end_time = time.time()\n",
    "elapse_time_1 = end_time - start_time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compare the result with the straight way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# perform matrix multiplication in a straight way\n",
    "y = x\n",
    "\n",
    "start_time = time.time()\n",
    "\n",
    "for i in range(0, n_times):\n",
    "    y_2 = A.dot(y)\n",
    "    \n",
    "end_time = time.time()\n",
    "elapse_time_2 = end_time - start_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.3783827 0.3783827 0.3783827 0.3783827] [0.34306013 0.34684371 0.47449214 0.33330137]\n"
     ]
    }
   ],
   "source": [
    "print(y_1, y_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0 0.10316801071166992\n"
     ]
    }
   ],
   "source": [
    "# compare the time \n",
    "print(elapse_time_1, elapse_time_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}