{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cas d'utilisation des valeurs et vecteurs propres"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import numpy.linalg as lin\n",
    "\n",
    "np.set_printoptions(precision=3, linewidth=150, suppress=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fibonnacci\n",
    "\n",
    "La suite de Fibonnacci est $x_n = x_{n-2} + x_{n-1}$ avec $x_0 = 1, x_1 = 1$.\n",
    "\n",
    "Quelle est la complexité pour calculer $x_n$ ?\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comme on a 2 termes à droite du signe égal, écrivons Fibonnacci sous forme d'un système matriciel $2\\times 2$ :\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "x_{n-1} &= x_{n-1} \\\\\n",
    "x_n &= x_{n-2} + x_{n-1} \\\\\n",
    "\\end{align}\n",
    "$$\n",
    "ce qui donne\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "x_{n-1}\\\\\n",
    "x_n  \\\\\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "0 & 1 \\\\\n",
    "1 & 1 \\\\\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "x_{n-2}\\\\\n",
    "x_{n-1}  \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Écrire la matrice F ci-dessous et vérifier que le 6e élément de la suite de Fibonacci est 8 en n'utilisant que \n",
    "la matrice F et les valeurs initiales de la suite. La fonction `numpy.linalg.matrix_power` pourra vous être utile."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 1],\n",
       "       [1, 1]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F = np.array([[0,1],[1,1]])\n",
    "F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 5,  8],\n",
       "       [ 8, 13]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F6 = lin.matrix_power(F,6)\n",
    "F6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculer n produits matriciels n'est pas rentable, par contre sachant que\n",
    "$F = P\\, D\\, P^{-1}$ avec\n",
    "\n",
    "* P la matrice des vecteurs propres\n",
    "* D la matrice diagonale des valeurs propres\n",
    "\n",
    "on peut faire quelque chose car il va avoir des simplification lors du calcul de de $F^n$. \n",
    "\n",
    "* Ecrire la formule matriciel de la suite de Fibonnacci en fonction de P et D. \n",
    "* Expliquer pourquoi le calcul du n-ème élément de la suite peut se faire en temps constant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$F^n = F \\times F^{n-1} = P\\times D^n \\times P^{-1}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Écrire la fonction `fibo(n)` qui calcule le n-ème élément de la suite de Fibonnacci en temps constant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibo(n):\n",
    "    F = np.array([[0,1],[1,1]], dtype=int)\n",
    "    D, P = lin.eig(F)\n",
    "    return (P @ lin.matrix_power(np.diag(D),n) @ lin.inv(P))[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([5., 8.])"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibo(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifier que votre fonction est en temps constant en chronométrant `fibo(5)` et `fibo(1000)` avec la commande \n",
    "`%timeit` de Jupyter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "84.8 μs ± 7.75 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)\n",
      "109 μs ± 6.71 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit fibo(5)\n",
    "%timeit fibo(1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Google page rank\n",
    "\n",
    "Soit N pages web numérotées qui font référence les unes aux autres. Disons que si la page 3 est référencée par les pages 8 9 et 13 j'écris $x_3 = x_8 + x_9 + x_{13}$. On voit qu'on peut écrire ces référencements dans une\n",
    "matrice avec le i-ième ligne qui décrit par qui est référencée la i-ème page web. Cette matrice a un 1 dans\n",
    "la j-ième colonne si la page j cite la page i et sinon un 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 1, 0, 0, 0, 1, 0, 0],\n",
       "       [0, 0, 0, 0, 0, 0, 1, 0],\n",
       "       [1, 1, 0, 0, 1, 0, 1, 1],\n",
       "       [1, 1, 1, 0, 1, 1, 0, 0],\n",
       "       [1, 1, 1, 0, 0, 0, 0, 0],\n",
       "       [0, 0, 1, 1, 1, 0, 1, 0],\n",
       "       [1, 1, 0, 1, 0, 1, 0, 1],\n",
       "       [1, 0, 0, 0, 0, 0, 0, 0]])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.random.seed(42)\n",
    "N = 8\n",
    "A = np.random.randint(2,size=(N,N))\n",
    "for i in range(len(A)):\n",
    "    A[i,i] = 0   # on ne compte pas les auto-référencements\n",
    "A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Cet article](https://www.math.upenn.edu/~wilf/website/KendallWei.pdf) indique que Google à l'époque de l'écriture de l'article (2001) basait son classement des pages web \n",
    "en utilisant les vecteurs propres de cette matrice (vous n'avez pas besoin de lire cet article pour faire l'exercice).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approche itérative\n",
    "Une bonne introduction qui va un peu plus loin peut-être trouvé [ici](https://pi.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html).\n",
    "\n",
    "Dans un premier temps on procède de la manière suivant pour trouver l'importance d'une page:\n",
    "Étant donné N page à évaluer \n",
    "* On initialise un vecteur __v__ de taille N avec 1 partout -> Correspond à une distribution uniforme de l'importance initialement\n",
    "* On calcule le produit matrice vecteur A __v__\n",
    "* On normalise le résultat pour que la norme 1 soit égale au nombre de pages (N)\n",
    "* On répète ces étapes jusqu'à un point fixe\n",
    "\n",
    "De cette manière l'entrée i du vecteur __v__ correspond à l'importance de la page i -> Discutez pourquoi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.774 0.387 1.419 1.419 1.032 1.29  1.548 0.129]]\n",
      "[[0.542 0.5   1.25  1.583 0.833 1.75  1.292 0.25 ]]\n",
      "[[0.742 0.426 1.127 1.608 0.756 1.636 1.526 0.179]]\n",
      "[[0.672 0.497 1.183 1.527 0.748 1.635 1.496 0.242]]\n",
      "[[0.694 0.487 1.19  1.542 0.766 1.613 1.489 0.219]]\n",
      "[[0.683 0.484 1.189 1.545 0.771 1.622 1.481 0.226]]\n",
      "[[0.686 0.482 1.187 1.546 0.767 1.624 1.485 0.222]]\n",
      "[[0.686 0.484 1.186 1.546 0.767 1.624 1.485 0.223]]\n",
      "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n",
      "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n",
      "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n",
      "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n",
      "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n",
      "[[0.686 0.484 1.187 1.545 0.767 1.623 1.485 0.223]]\n"
     ]
    }
   ],
   "source": [
    "v = np.zeros((N,1))\n",
    "vprime = np.ones((N,1))\n",
    "\n",
    "while (np.absolute(np.max(vprime - v)) > 1e-5): # which norm is used here?\n",
    "    v = vprime\n",
    "    vprime = \n",
    "    vprime *= \n",
    "    print(vprime.T)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Un autre approche\n",
    "\n",
    "Vous constatez que A.__v__ = α * __v__ pour une constante α. Est-ce que ça vous rappelle quelque chose ?\n",
    "\n",
    "* On considère que les composantes du premier vecteur propre représentent la valeur de chaque page. Calculez les valeurs des pages. Comparez avec le résultat obtenue auparavant.\n",
    "* Calculez le nombre de citations pour chaque page."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.13.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}