{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "def gauss(M):\n", " A=copy(M)\n", " n=A.nrows()\n", " for j in range(n):\n", " # Recherche du pivot\n", " if A[j,j]==0:\n", " for i in range(j+1,n):\n", " if A[i,j]!=0:\n", " A.swap_rows(i,j)\n", " break\n", " if A[j,j]==0:\n", " raise ValueError(\"non invertible matrix\")\n", " for i in range(j+1, n):\n", " A.add_multiple_of_row(i, j, -A[i,j]/A[j,j])\n", " return A" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "def matrice_inversible(n, corps=QQ):\n", " # Renvoie une matrice inversible\n", " while True:\n", " m = random_matrix(corps, n)\n", " if m.det()!=0:\n", " return m" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrr}\n", "-\\frac{1}{2} & 0 & -1 & 0 & 0 \\\\\n", "0 & -1 & 1 & 1 & -\\frac{1}{2} \\\\\n", "-2 & -2 & 0 & \\frac{1}{2} & -2 \\\\\n", "2 & 0 & -2 & 2 & -1 \\\\\n", "-\\frac{1}{2} & 1 & 1 & 1 & 1\n", "\\end{array}\\right)$ " ], "text/plain": [ "[-1/2 0 -1 0 0]\n", "[ 0 -1 1 1 -1/2]\n", "[ -2 -2 0 1/2 -2]\n", "[ 2 0 -2 2 -1]\n", "[-1/2 1 1 1 1]" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrr}\n", "-\\frac{1}{2} & 0 & -1 & 0 & 0 \\\\\n", "0 & -1 & 1 & 1 & -\\frac{1}{2} \\\\\n", "0 & 0 & 2 & -\\frac{3}{2} & -1 \\\\\n", "0 & 0 & 0 & -\\frac{5}{2} & -4 \\\\\n", "0 & 0 & 0 & 0 & -\\frac{24}{5}\n", "\\end{array}\\right)$ " ], "text/plain": [ "[ -1/2 0 -1 0 0]\n", "[ 0 -1 1 1 -1/2]\n", "[ 0 0 2 -3/2 -1]\n", "[ 0 0 0 -5/2 -4]\n", "[ 0 0 0 0 -24/5]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "M=matrice_inversible(5); show(M); show(gauss(M)); " ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrr}\n", "1 & 0 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 0 & 0 \\\\\n", "0 & 0 & 1 & 0 & 0 \\\\\n", "0 & 0 & 0 & 1 & 0 \\\\\n", "0 & 0 & 0 & 0 & 1\n", "\\end{array}\\right)$ " ], "text/plain": [ "[1 0 0 0 0]\n", "[0 1 0 0 0]\n", "[0 0 1 0 0]\n", "[0 0 0 1 0]\n", "[0 0 0 0 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(M.echelon_form());" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "def max_coeff(M):\n", " return max(max(abs(c.numerator()) for row in M.rows() for c in row),\n", " max(abs(c.denominator()) for row in M.rows() for c in row))" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrrrrrrr}\n", "-\\frac{1}{2} & 0 & 1 & 1 & -1 & -2 & -1 & -2 & -\\frac{1}{2} & 0 \\\\\n", "0 & \\frac{1}{2} & 2 & \\frac{3}{2} & 0 & -\\frac{7}{2} & -3 & -4 & -1 & 0 \\\\\n", "0 & 0 & -5 & -5 & 4 & 10 & 4 & 8 & 4 & 1 \\\\\n", "0 & 0 & 0 & -1 & 2 & 0 & 0 & -1 & -1 & 0 \\\\\n", "0 & 0 & 0 & 0 & -\\frac{9}{10} & 1 & \\frac{8}{5} & \\frac{6}{5} & \\frac{8}{5} & -\\frac{1}{10} \\\\\n", "0 & 0 & 0 & 0 & 0 & \\frac{16}{3} & \\frac{19}{3} & 3 & \\frac{23}{6} & -\\frac{1}{3} \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & \\frac{87}{32} & -\\frac{11}{32} & \\frac{315}{64} & -\\frac{13}{32} \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & \\frac{67}{87} & -\\frac{1035}{58} & \\frac{103}{174} \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \\frac{2432}{201} & -\\frac{635}{804} \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \\frac{2271}{1024}\n", "\\end{array}\\right)$ " ], "text/plain": [ "[ -1/2 0 1 1 -1 -2 -1 -2 -1/2 0]\n", "[ 0 1/2 2 3/2 0 -7/2 -3 -4 -1 0]\n", "[ 0 0 -5 -5 4 10 4 8 4 1]\n", "[ 0 0 0 -1 2 0 0 -1 -1 0]\n", "[ 0 0 0 0 -9/10 1 8/5 6/5 8/5 -1/10]\n", "[ 0 0 0 0 0 16/3 19/3 3 23/6 -1/3]\n", "[ 0 0 0 0 0 0 87/32 -11/32 315/64 -13/32]\n", "[ 0 0 0 0 0 0 0 67/87 -1035/58 103/174]\n", "[ 0 0 0 0 0 0 0 0 2432/201 -635/804]\n", "[ 0 0 0 0 0 0 0 0 0 2271/1024]" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}2432$ " ], "text/plain": [ "2432" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "G=gauss(matrice_inversible(10)); show(G); show(max_coeff(G));" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[1, 2, 4, 65, 20090477, 1192880382360512547051804985, 375777457025164771998313802791389332678265402100840617220676063425\\right]$ " ], "text/plain": [ "[1,\n", " 2,\n", " 4,\n", " 65,\n", " 20090477,\n", " 1192880382360512547051804985,\n", " 375777457025164771998313802791389332678265402100840617220676063425]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "t=[max_coeff(gauss(matrice_inversible(2^k))) for k in range(7)]; show(t)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[1, 2, 3, 7, 25, 90, 218\\right]$ " ], "text/plain": [ "[1, 2, 3, 7, 25, 90, 218]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "tt=[x.ndigits(2) for x in t]; show(tt);" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[0.0, 1.0, 1.5849625007211563, 2.807354922057604, 4.643856189774724, 6.491853096329675, 7.768184324776926\\right]$ " ], "text/plain": [ "[0.0,\n", " 1.0,\n", " 1.5849625007211563,\n", " 2.807354922057604,\n", " 4.643856189774724,\n", " 6.491853096329675,\n", " 7.768184324776926]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "lt=[float(log(tt[i],2)) for i in range(len(tt))]; show(lt);" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAkwAAAGFCAYAAAAPa6wiAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAYKUlEQVR4nO3dcYyU5Z0H8N/Iyqi4rIW4EY4BCfWqC4KmbC1gtQrYI4bTGm1ttEVt2pJsAeW8GrzkDu+sq+f1Ehv3SKG5bYkh3DUWxDaImpPlvJYWMF4pNYLFK2iktp4wsH+MAef+8LotUXyY3dl5Z4fPJ3kj7/C+z/ubN8Z8fZ9nfm+uXC6XAwCAEzot6wIAAOqdwAQAkCAwAQAkCEwAAAkCEwBAgsAEAJAgMAEAJAhMAAAJNQ9M5XI5isVi6JcJAAwVNQ9Mhw8fjpaWljh8+HCtLw0A0C+m5AAAEgQmAIAEgQkAIKEp6wIAAKplzZqI//7viGuuiZg9u3rj1uwJU1dXV7S1tUV7e3utLgkAnEL++Z8jbrkl4h//MWLu3IhNm6o3dq5c49/3F4vFaGlpiUOHDsXIkSNreWkAoIF9+tMRPT1/3F+8OOKRR6oztjVMAEBDaGs7fv+ii6o3tjVMAEBDePjhiKNH31vD9JnPRHzta9Ub25QcAECCKTkAgASBCQAgQWACAEgQmAAAEjSuBABI8Cs5AIAEU3IAAAkCEwBAgsAEAJAgMAEAJAhMAAAJAhMAQILABACQoHElAECCxpUAAAmm5AAAEgQmAIAEgQkAIEFgAgBIEJgAABIEJgCABH2YAAAS9GECAEgwJQcAkCAwAQAkCEwAAAkVBabzzz8/crnc+7aOjo7Bqg8AIHNNlRy8bdu2OHbsWN/+L3/5y5g7d27cdNNNVS8MAKBeVBSYzj333OP2H3zwwZg0aVJceeWVVS0KAKCeVBSY/tQ777wTjz32WCxdujRyudwJjyuVSlEqlfr2i8Vify8JAJCJfi/6Xr9+fRw8eDBuu+22Dz2us7MzWlpa+rZCodDfSwIAZKLfjSs/85nPxPDhw+PJJ5/80OM+6AlToVDQuBIAGDL6NSX3m9/8Jp599tn44Q9/mDw2n89HPp/vz2UAAOpCv6bkuru7o7W1Na699tpq1wMAUHcqDkzvvvtudHd3x4IFC6Kpqd9rxgEAhoyKA9Ozzz4b+/btizvuuGMw6gEAqDv9XvTdX8ViMVpaWiz6BgCGDO+SAwBIEJgAABJqFpi6urqira0t2tvba3VJAICqsIYJACDBlBwAQILABACQIDABACQITAAACQITAECCwAQAkCAwAQAkaFwJAJCgcSUAQIIpOQAYZEePRnz1qxHjxkX8xV9EvPlm1hVRKYEJAAbZv/xLxKpVEa+/HrFpU8Rdd2VdEZUSmABgkO3b9+H71D+BCQAG2ec/H3HGGX/cX7Agu1ron6asCwCARtfeHrF9e8R//EfElCkRV12VdUVUSmACgBqYPPm9jaFJHyYAgAR9mAAAEiz6BgBIEJgAABIEJgCABIEJACBBYAIASBCYAAASBCYAgASNKwEAEjSuBABIMCUHAJAgMAEAJFQcmF5//fW49dZbY/To0XHWWWfFJZdcEjt27BiM2gAA6kJTJQe//fbbMWvWrLjqqqti48aN0draGr/+9a/jnHPOGaz6AAAyV1Fgeuihh6JQKER3d3ffZ+eff361awIAqCsVTclt2LAhpk+fHjfddFO0trbGpZdeGqtWrRqs2gAA6kJFgWnv3r2xYsWKuOCCC2LTpk2xcOHCWLx4caxevfqE55RKpSgWi8dtAABDSUV9mIYPHx7Tp0+Pn/zkJ32fLV68OLZt2xY//elPP/Cc5cuXx3333fe+z/VhAgCGioqeMI0ZMyba2tqO++yiiy6Kffv2nfCcZcuWxaFDh/q2/fv3969SAICMVLToe9asWfHyyy8f99nu3btjwoQJJzwnn89HPp/vX3UAAHWgoidMd911V2zdujUeeOCBeOWVV2LNmjWxcuXK6OjoGKz6AAAyV/G75H70ox/FsmXLYs+ePTFx4sRYunRpfOUrXznp871LDgAYarx8FwAgwbvkAAASBCYAgISaBaaurq5oa2uL9vb2Wl0SAKAqrGECAEgwJQcAkCAwAQAkCEwAAAkCEwBAgsAEAJAgMAEAJAhMAAAJGlcCACRoXAkAkGBKDgAgQWACAEgQmAAAEgQmAIAEgQkAIEFgAgBIEJgAABI0rgQASNC4EgAgwZQcAECCwAQAkCAwAQAkCEwAAAkCEwBAgsAEAJAgMAEAJGhcCQCQoHElAECCKTkAgASBCQAgoaLAtHz58sjlcsdt55133mDVBgBQF5oqPWHy5Mnx7LPP9u0PGzasqgUBANSbigNTU1OTp0oAwCml4jVMe/bsibFjx8bEiRPj5ptvjr17937o8aVSKYrF4nEbAMBQUlFguuyyy2L16tWxadOmWLVqVRw4cCBmzpwZb7311gnP6ezsjJaWlr6tUCgMuGgAgFoaUB+m3t7emDRpUnzjG9+IpUuXfuAxpVIpSqVS336xWIxCoaAPEwAwZFS8hulPjRgxIi6++OLYs2fPCY/J5/ORz+cHchkAgEwNqA9TqVSKl156KcaMGVOtegAA6k5Fgenuu++Onp6eePXVV+NnP/tZ3HjjjVEsFmPBggWDVR8AQOYqmpJ77bXX4gtf+EL8/ve/j3PPPTc++clPxtatW2PChAmDVR8AQOa8fBcAIMG75AAAEgQmAICEmgWmrq6uaGtri/b29lpdEgCgKqxhAgBIMCUHAJAgMAEAJAhMAKe4YjFi3bqI55/PuhKoXwITwCmsWIz45Ccjbrgh4lOfivi7v8u6IqhPAhPAKWzjxoiXXvrj/re+lV0tUM8EJoBT2KhRx++PHp1NHVDvBCaAU9jcuRFLl0YMHx4xdmzEY49lXRHUp5r1Yerq6oqurq44duxY7N69Wx8mgDpSLkfkcllXAfVL40oAgARTcgAACQITAECCwAQAkCAwAQAkCEwAAAkCEwBAQs0CU1dXV7S1tUV7e3utLgkAUBX6MAEAJJiSAwBIEJgAABIEJgCABIEJACBBYAIASBCYAAASBCYAgASNKwEAEjSuBABIMCUHAJAgMAEAJAhMAAAJAwpMnZ2dkcvl4s4776xWPQAAdaffgWnbtm2xcuXKmDp1ajXrAQCoO/0KTEeOHIlbbrklVq1aFR/5yEeqXRMAQF3pV2Dq6OiIa6+9NubMmZM8tlQqRbFYPG4DABhKmio9Ye3atfHCCy/Etm3bTur4zs7OuO+++youDACgXlT0hGn//v2xZMmSeOyxx+KMM844qXOWLVsWhw4d6tv279/fr0IBALJSUafv9evXx2c/+9kYNmxY32fHjh2LXC4Xp512WpRKpeP+7oPo9A0ADDUVTcnNnj07du7cedxnt99+e1x44YVxzz33JMMSAMBQVFFgam5ujilTphz32YgRI2L06NHv+xwAoFHo9A0AkFDRGqZqsIYJABhqPGECAEgQmAAAEmoWmLq6uqKtrS3a29trdUkAgKqwhgkAIMGUHABAgsAEAJAgMAEAJAhMAAAJAhMAQILABACQoA8TAECCPkwAAAmm5AAAEgQmAIAEgQkAIEFgAgBIEJgAABIEJgCABIEJACBB40oAgASNKwEAEkzJAQAkCEwAAAkCEwBAgsAEAJAgMAEAJAhMAAAJAhMAQILGlQAACRpXAgAkmJIDAEgQmAAAEioKTCtWrIipU6fGyJEjY+TIkTFjxozYuHHjYNUGAFAXKgpM48aNiwcffDC2b98e27dvj6uvvjquu+662LVr12DVBwCQuQEv+h41alQ8/PDD8eUvf/mkjrfoGwAYapr6e+KxY8fiBz/4QfT29saMGTNOeFypVIpSqdS3XywW+3tJAIBMVLzoe+fOnXH22WdHPp+PhQsXxrp166Ktre2Ex3d2dkZLS0vfVigUBlQwAECtVTwl984778S+ffvi4MGD8fjjj8d3v/vd6OnpOWFo+qAnTIVCwZQcADBkDHgN05w5c2LSpEnxne9856SOt4YJABhqBtyHqVwuH/cECQCg0VS06Pvee++NefPmRaFQiMOHD8fatWtj8+bN8dRTTw1WfQAAmasoMP32t7+NL37xi/HGG29ES0tLTJ06NZ566qmYO3fuYNUHAJA5L98F6la5HPHTn773z5kzI3K5rCsCTlXeJQfUrS99KWLWrIjLL4+49dasqwFOZZ4wAXXp17+O+OhHj/9s9+6ICy7Iph7g1FazJ0xdXV3R1tYW7e3ttbokMISddVbEaX/yX6hc7r3PALLgCRNQtx55JOKv/uq9Pz/8cMRdd2VbD3DqEpiAuvaHNm/5fLZ1AKe2fr98F6AWBCWgHviVHABAgsAEAJAgMAEAJAhMAAAJAhMAQILGlQAACfowAQAkmJIDAEgQmAAAEgQmAIAEgQkAIEFgAgBIEJgAABIEJgCABI0rAQASNK4EAEgwJQcAkCAwAQAkCEwAAAkCEwBAgsAEAJAgMAEAJOjDBACQoA8TAECCKTkAgASBCQAgQWACAEioKDB1dnZGe3t7NDc3R2tra1x//fXx8ssvD1ZtAAB1oaLA1NPTEx0dHbF169Z45pln4ujRo3HNNddEb2/vYNUHAJC5Af1K7ne/+120trZGT09PXHHFFSd1jl/JAQBDTdNATj506FBERIwaNeqEx5RKpSiVSn37xWJxIJcEAKi5fi/6LpfLsXTp0rj88stjypQpJzyus7MzWlpa+rZCodDfSwIAZKLfU3IdHR3x4x//OJ5//vkYN27cCY/7oCdMhULBlBwAMGT0a0pu0aJFsWHDhtiyZcuHhqWIiHw+H/l8vl/FAQDUg4oCU7lcjkWLFsW6deti8+bNMXHixMGqCwCgblQUmDo6OmLNmjXxxBNPRHNzcxw4cCAiIlpaWuLMM88clAIBALJW0RqmXC73gZ93d3fHbbfddlJjaCsAAAw1FU/JAQCcarxLDgAgQWACAEioWWDq6uqKtra2aG9vr9UlAQCqYkDvkusPi74BgKHGlBwAQILABACQIDABACQITAAACQITAECCwAT98F//FTF+fMQZZ0T89V9nXQ0Ag01bAeiHiRMj/ud//rj/9NMRc+dmVg4Ag0zjSuiH3//+w/cBaCyeMEE//O3fRvzDP7z35z//84if/SzinHOyrQmAwSMwQT9t2RLx299GXHNNREtL1tUAMJiasi4Ahqorrsi6AgBqxa/kAAASBCYAgASBCQAgQWACAEjQhwkAIEFbAQCABFNyAAAJAhMAQILABACQIDABACQITAAACQITAECCwAQAkKBxJQBAgsaVAAAJpuQAABIEJgCAhIoD05YtW2L+/PkxduzYyOVysX79+sGoCwCgblQcmHp7e2PatGnx6KOPDkY9AAB1p6nSE+bNmxfz5s0bjFqokiefjNi5M2LOnIhPfCLragBg6LOGqcF0dUX85V9G/M3fRMyaFfGf/5l1RQAw9A16YCqVSlEsFo/bGDz/9m9//PPRoxHr1mVXCwA0ikEPTJ2dndHS0tK3FQqFwb7kKW3SpA/fBwAqN6DGlblcLtatWxfXX3/9CY8plUpRKpX69ovFYhQKBY0rB8nBgxFf/ep7a5jmzYv4p3+KOM3EKwAMSMWLviuVz+cjn88P9mX4f+ecE/Hv/551FQDQWCoOTEeOHIlXXnmlb//VV1+NF198MUaNGhXjx4+vanEAAPWg4im5zZs3x1VXXfW+zxcsWBDf+973kud7lxwAMNR4+S4AQILlwAAACQITAEBCzQJTV1dXtLW1RXt7e60uCQBQFdYwAQAkmJIDAEgQmAAAEgQmAIAEgQkAIEFgAgBIEJgAABIEJgCABI0rAQASNK4EAEgwJQcAkCAwAQAkCEwAAAkCEwBAgsAEAJAgMAEAJAhMAAAJGlcCACRoXAkAkGBKDgAgQWACAEgQmAAAEgQmAIAEgQkAIEFgAgBIEJgAABI0rgQASNC4EgAgwZQcAECCwAQAkCAwAQAkCEwAAAk1C0xHj0Z87WsRbW3v7f/v/9bqygAAA9NUjUHK5XIcPnz4A/+uVCpFqVSK7343YuXKiIj3jrv77mL8679W4+oAAP3X3NwcuVzuQ4+pSluBP7QKAAAYak6m1VFVAtPJPGHasSPixhsjjh59IyI+EX//97+KJUv+bEDXbW9vj23btg1ojGqNU0+1FIvFKBQKsX///gH3uqqn71Vv47jPtRnHfa7NOO5zbcZp1PtcT7X05x6fzBOmqkzJ5XK5ZFHjxkVs3x6xfn3E8uURt9/ePOB/WYYNG1aV5pfVGKeeavmDkSNHNtz3qrdxItznWowT4T7XYpwI97kW40Q03n2up1r+oBr3+E/V9Fdy06ZFfPnL1Ruvo6Ojbsapp1qqqd6+V72NUy319r3qbZxqqbfvVW/jVEu9fa96G6da6ul71VMtg6Xmr0Z57bXX+h6VjRs3rpaXPmV4/UxtuM+14T7XhvtcG+7z4Busezxs+fLly6s22kkolUrx8MMPx7Jly2LEiBG1vPQpZdiwYfHpT386mpqqMuvKCbjPteE+14b7XBvu8+AbjHvs5bsAAAk6fQMAJNT8CdMfWhCczE/4AADqQc0DEwDAUGNKDgAgQWBqMFu2bIn58+fH2LFjI5fLxfr167MuqeF0dnZGe3t7NDc3R2tra1x//fXx8ssvZ11Ww1mxYkVMnTq1r/ncjBkzYuPGjVmX1dA6Ozsjl8vFnXfemXUpDWX58uWRy+WO284777ysy2pIr7/+etx6660xevToOOuss+KSSy6JHTt2VGVsganB9Pb2xrRp0+LRRx/NupSG1dPTEx0dHbF169Z45pln4ujRo3HNNddEb29v1qU1lHHjxsWDDz4Y27dvj+3bt8fVV18d1113XezatSvr0hrStm3bYuXKlTF16tSsS2lIkydPjjfeeKNv27lzZ9YlNZy33347Zs2aFaeffnps3LgxfvWrX8W3vvWtOOecc6oyviYQDWbevHkxb968rMtoaE899dRx+93d3dHa2ho7duyIK664IqOqGs/8+fOP2//mN78ZK1asiK1bt8bkyZMzqqoxHTlyJG655ZZYtWpV3H///VmX05Campo8VRpkDz30UBQKheju7u777Pzzz6/a+J4wwQAdOnQoIiJGjRqVcSWN69ixY7F27dro7e2NGTNmZF1Ow+no6Ihrr7025syZk3UpDWvPnj0xduzYmDhxYtx8882xd+/erEtqOBs2bIjp06fHTTfdFK2trXHppZfGqlWrqja+wAQDUC6XY+nSpXH55ZfHlClTsi6n4ezcuTPOPvvsyOfzsXDhwli3bl20tbVlXVZDWbt2bbzwwgvR2dmZdSkN67LLLovVq1fHpk2bYtWqVXHgwIGYOXNmvPXWW1mX1lD27t0bK1asiAsuuCA2bdoUCxcujMWLF8fq1aurMr4pORiAr3/96/GLX/winn/++axLaUgf+9jH4sUXX4yDBw/G448/HgsWLIienh6hqUr2798fS5YsiaeffjrOOOOMrMtpWH+6TOLiiy+OGTNmxKRJk+L73/9+LF26NMPKGsu7774b06dPjwceeCAiIi699NLYtWtXrFixIr70pS8NeHxPmKCfFi1aFBs2bIjnnnvOi6QHyfDhw+OjH/1oTJ8+PTo7O2PatGnxyCOPZF1Ww9ixY0e8+eab8fGPfzyampqiqakpenp64tvf/nY0NTXFsWPHsi6xIY0YMSIuvvji2LNnT9alNJQxY8a873+mLrrooti3b19VxveECSpULpdj0aJFsW7duti8eXNMnDgx65JOGeVyOUqlUtZlNIzZs2e/79dat99+e1x44YVxzz33xLBhwzKqrLGVSqV46aWX4lOf+lTWpTSUWbNmva/Fy+7du2PChAlVGV9gajBHjhyJV155pW//1VdfjRdffDFGjRoV48ePz7CyxtHR0RFr1qyJJ554Ipqbm+PAgQMREdHS0hJnnnlmxtU1jnvvvTfmzZsXhUIhDh8+HGvXro3Nmze/71eK9F9zc/P71t6NGDEiRo8ebU1eFd19990xf/78GD9+fLz55ptx//33R7FYjAULFmRdWkO56667YubMmfHAAw/E5z73ufj5z38eK1eujJUrV1bnAmUaynPPPVeOiPdtCxYsyLq0hvFB9zciyt3d3VmX1lDuuOOO8oQJE8rDhw8vn3vuueXZs2eXn3766azLanhXXnllecmSJVmX0VA+//nPl8eMGVM+/fTTy2PHji3fcMMN5V27dmVdVkN68skny1OmTCnn8/nyhRdeWF65cmXVxvYuOQCABIu+AQASBCYAgASBCQAgQWACAEgQmAAAEgQmAIAEgQkAIEFgAgBIEJgAABIEJgCABIEJACBBYAIASPg/bGm/ZZAlC5cAAAAASUVORK5CYII=\n", "text/plain": [ "Graphics object consisting of 1 graphics primitive" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "points(enumerate(lt))" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "# Cela corrobore l'hypothèse d'un nombre de chiffres des numérateurs et dénominateurs polynômial en la dimension de la matrice" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "import time;" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "def temps_gauss(n):\n", " M=matrice_inversible(n)\n", " debut=time.time()\n", " gauss(M)\n", " return(time.time() - debut)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.0002124309539794922" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "temps_gauss(5)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "625 loops, best of 3: 117 μs per loop" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('gauss(M)')" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[2.1457672119140625 \\times 10^{-05}, 1.8596649169921875 \\times 10^{-05}, 4.172325134277344 \\times 10^{-05}, 0.0002300739288330078, 0.0019309520721435547, 0.022881031036376953, 0.16617679595947266, 1.777696132659912\\right]$ " ], "text/plain": [ "[2.1457672119140625e-05,\n", " 1.8596649169921875e-05,\n", " 4.172325134277344e-05,\n", " 0.0002300739288330078,\n", " 0.0019309520721435547,\n", " 0.022881031036376953,\n", " 0.16617679595947266,\n", " 1.777696132659912]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "t=[temps_gauss(2^k) for k in range(8)]; show(t)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[-15.508146903670326, -15.714597781137751, -14.548788888167671, -12.085614867844559, -9.016471928834905, -5.449704127275807, -2.5892091489482882, 0.830008740719973\\right]$ " ], "text/plain": [ "[-15.508146903670326,\n", " -15.714597781137751,\n", " -14.548788888167671,\n", " -12.085614867844559,\n", " -9.016471928834905,\n", " -5.449704127275807,\n", " -2.5892091489482882,\n", " 0.830008740719973]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "tt=[float(log(t[k],2)) for k in range(8)]; show(tt)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAkwAAAGGCAYAAACJ/96MAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAfzklEQVR4nO3de3RU5b3G8WdIwoBkMkgAQ8JAUlAggCTVGCUoqJTIigSvgFZFvOEyooJyNHW5SI/WBFtFrRELFvCSLs6yAoa2cnFxKVTQCGIVNFAQAoRLD9GZEO1wyZw/OE5NCbwJc9k75PtZay9n7+z9vr9s88fDu/e8ryMQCAQEAACAU2pjdQEAAAB2R2ACAAAwIDABAAAYEJgAAAAMCEwAAAAGBCYAAAADAhMAAIABgQkAAMCgRQSmQCAgn88n5tgEAABWaBGBqba2Vm63W7W1tVaXAgAAWqEWEZgAAACsRGACAAAwsHVgKi0tVXp6urKysqwuBQAAtGKOQAt4k9rn88ntdsvr9SohIcHqcgAAgE0dOyZt3iyde67Uo0f42rX1CBMAAEBTHTkijRghZWRIP/mJ9Prr4WubwAQAAM4KixdLK1ee+Hz8uDR1avjaJjABAICzQlxcw/3Y2PC1TWACAABnhbw86frrT3x2OqVXXw1f22HMXgAAANaJiZEWLJD27JFcLsntDl/bBCYAAHBW6d49/G3ySA4AAMCAwAQAAGBAYAIAADCwdWBiaRQAAGAHLI0CAABgYOsRJgAAADsgMAEAABgQmAAAAAwITAAAAAYEJgAAAAMCEwAAgAGBCQAAwMDSxXcDgYBqa2tPOu73++X3+4P7P5zj8/miVhsAAGgdXC6XHA7Hac+xdOLKHyakBAAAsEpTJsa2NDA1dYRp3759uuSSS7RlyxalpKQ0u5+srCxVVFScUY0t7VqfzyePx6Pdu3ef0azoLe33DeVaK+9VqNe3tvvV0q7lXjUd96rpuFdN19x71ZQRJksfyTkcjmb9T3e5XGf0RxITE3PGS6q0xGslKSEhgXvVRFbcq1Cvb233qyVeK3GvmoN71XTcq6Y703vVmFbx0ndBQUGrujYULfH3bYn3KtTrW9v9aonXhqIl/r7cq+hcG4qW+Ptada8a0yIW392zZ09waK179+5Wl2NrLFTcdNyr5uF+NR33qum4V03HvWq6SNyrmKKioqKwtBRBfr9fv/71r1VYWKgOHTpYXY7txcTEaNiwYYqNtfSJa4vAvWoe7lfTca+ajnvVdNyrpgv3vWoRI0ykagAAYKVW8Q4TAABAKAhMAAAABgQmAAAAAwITAACAga0DU2lpqdLT05WVlWV1KS3CX//6V40aNUrJyclyOBxatGiR1SXZUnFxsbKysuRyudS1a1ddd911qqystLosW5o5c6YuvPDC4ORvl112md5//32ry2oRiouL5XA49Mgjj1hdiu0UFRXJ4XA02JKSkqwuy7b27t2r2267TYmJiTrnnHOUkZGhDRs2WF2W7aSmpp70d+VwOMI2l5OtA1NBQYG2bNkS0vITrUldXZ0GDRqkV155xepSbG316tUqKCjQ+vXrtXz5ch07dkwjRoxQXV2d1aXZTvfu3VVSUqJPPvlEn3zyia666iqNHj1amzdvtro0W6uoqNCsWbN04YUXWl2KbfXv31/79u0Lbp9//rnVJdnSN998o5ycHMXFxen999/Xli1b9Pzzz6tjx45Wl2Y7FRUVDf6mli9fLkm6+eabw9I+EzmcRUaOHKmRI0daXYbtLVmypMH+3Llz1bVrV23YsEFXXHGFRVXZ06hRoxrs/+pXv9LMmTO1fv169e/f36Kq7O3w4cP6+c9/rtmzZ+uZZ56xuhzbio2NZVSpCaZPny6Px6O5c+cGj6WmplpXkI116dKlwX5JSYl69eqloUOHhqV9W48wAdHg9XolSZ06dbK4Ens7fvy45s+fr7q6Ol122WVWl2NbBQUFysvL0/Dhw60uxda2bdum5ORkpaWlady4cdqxY4fVJdlSeXm5Lr74Yt18883q2rWrMjMzNXv2bKvLsr0jR47o7bff1l133WVcVLepCExo1QKBgKZMmaIhQ4ZowIABVpdjS59//rni4+PldDp1//33a+HChUpPT7e6LFuaP3++Nm7cqOLiYqtLsbXs7Gy9+eabWrp0qWbPnq39+/dr8ODBOnTokNWl2c6OHTs0c+ZMnX/++Vq6dKnuv/9+PfTQQ3rzzTetLs3WFi1apG+//VZ33nln2NrkkRxatQcffFB///vftXbtWqtLsa0+ffpo06ZN+vbbb/Xuu+9q/PjxWr16NaHpP+zevVsPP/ywli1bpnbt2lldjq39+NWBgQMH6rLLLlOvXr30xhtvaMqUKRZWZj/19fW6+OKL9eyzz0qSMjMztXnzZs2cOVN33HGHxdXZ1+9//3uNHDlSycnJYWuTESa0WpMmTVJ5eblWrlzJos6n0bZtW/Xu3VsXX3yxiouLNWjQIL300ktWl2U7GzZs0MGDB3XRRRcpNjZWsbGxWr16tV5++WXFxsbq+PHjVpdoWx06dNDAgQO1bds2q0uxnW7dup30j5N+/fqpqqrKoorsb9euXfrggw90zz33hLVdRpjQ6gQCAU2aNEkLFy7UqlWrlJaWZnVJLUogEJDf77e6DNu5+uqrT/qm14QJE9S3b189/vjjiomJsagy+/P7/fryyy91+eWXW12K7eTk5Jw07cnWrVvVs2dPiyqyvx++yJOXlxfWdglMZ5HDhw/rH//4R3D/66+/1qZNm9SpUyf16NHDwsrspaCgQH/4wx/03nvvyeVyaf/+/ZIkt9ut9u3bW1ydvfziF7/QyJEj5fF4VFtbq/nz52vVqlUnfdMQksvlOuk9uA4dOigxMZH34/7DY489plGjRqlHjx46ePCgnnnmGfl8Po0fP97q0mxn8uTJGjx4sJ599lmNGTNGH3/8sWbNmqVZs2ZZXZot1dfXa+7cuRo/frxiY8MccQItgNfrDUgKeL1eq0uxtZUrVwYknbSNHz/e6tJspbF7JCkwd+5cq0uznbvuuivQs2fPQNu2bQNdunQJXH311YFly5ZZXVaLMXTo0MDDDz9sdRm2M3bs2EC3bt0CcXFxgeTk5MANN9wQ2Lx5s9Vl2dbixYsDAwYMCDidzkDfvn0Ds2bNsrok21q6dGlAUqCysjLsbTsCgUAgvBEs/Hw+n9xut7xerxISEqwuBwAAtDK2fumbpVEAAIAdMMIEAABgYOsRJgAAADsgMAEAABgQmAAAAAwITAAAAAYEJgAAAAMCEwAAgAGBCQAAwIDABAAAYGDrwMRM3wAAwA6Y6RsAAMDA1iNMAAAAdkBgAgAAMCAwAQAAGBCYAAAADCIemI4eParHH39cAwcOVIcOHZScnKw77rhD1dXVke4aAAAgLCIemL777jtt3LhRTz31lDZu3KgFCxZo69atys/Pj3TXAAAAYWHJtAIVFRW65JJLtGvXLvXo0cN4PtMKAAAAK1nyDpPX65XD4VDHjh2t6B4AAKBZYqPd4b/+9S898cQTuvXWW085WuT3++X3+4P7Pp8vWuUBAACcJOwjTGVlZYqPjw9ua9asCf7s6NGjGjdunOrr6/Xqq6+eso3i4mK53e7g5vF4wl0mAABAk4X9Haba2lodOHAguJ+SkqL27dvr6NGjGjNmjHbs2KEVK1YoMTHxlG00NsLk8Xh4hwkAAFgi7I/kXC6XXC5Xg2M/hKVt27Zp5cqVpw1LkuR0OuV0OsNdGgAAwBmJ+DtMx44d00033aSNGzfqT3/6k44fP679+/dLkjp16qS2bdtGugQAAICQRHxagZ07dyotLa3Rn61cuVLDhg0ztsG0AgAAwEoRH2FKTU2VBVM9AQAAhA1ryQEAABgQmAAAAAwITAAAAAYEJgAAbO7YMWnLFumf/7S6ktbL1oGptLRU6enpysrKsroUAAAs8f330tChUv/+kscjLVxodUWtU8SnFQgHphUAALRWc+ZId9/97/2f/ETavt26elorW48wAQDQ2jkcp99HdBCYAACwsVtuka644sTn9u2lGTOsrae1ivjElQAA4My1ayetWCHt2CElJkqdOlldUetEYAIAwOZiYqTzz7e6itaNR3IAAAAGBCYAAAADAhMAAIABgQkAAMCAwAQAAGBg68DE0igAAMAOWBoFAADAwNYjTAAAAHZAYAIAADAgMAEAABgQmAAAAAwITAAAAAYEJgAAAAMCEwAAgAGBCQAAwMDWgYmZvgEAgB0w0zcAAICBrUeYAAAA7IDABAAAYEBgAgAAMCAwAQAAGEQ9ME2cOFEOh0MvvvhitLsGAAA4I1ENTIsWLdJHH32k5OTkaHYLAAAQkqgFpr179+rBBx9UWVmZ4uLiotUtAABAyKISmOrr63X77bdr6tSp6t+/fzS6BAAACJvYaHQyffp0xcbG6qGHHmrS+X6/X36/P7jv8/kiVRoAAIBR2EeYysrKFB8fH9xWr16tl156SfPmzZPD4WhSG8XFxXK73cHN4/GEu0wAAIAmC/vSKLW1tTpw4EBw/5133tGTTz6pNm3+nc2OHz+uNm3ayOPxaOfOnSe10dgIk8fjYWkUAABgiYivJXfo0CHt27evwbHc3FzdfvvtmjBhgvr06WNsg7XkAACAlSL+DlNiYqISExMbHIuLi1NSUlKTwhIAAIDVmOkbAADAICrfkvtPjb23BAAAYFeMMAEAABgQmAAAAAwITAAAAAYEJgAAAANbB6bS0lKlp6crKyvL6lIAAEArFvGJK8OBiSsBAICVbD3CBAAAYAcEJgAAAAMCEwAAgAGBCQAAwIDABAAAYEBgAgAAMCAwAQAAGBCYAAAADAhMAAAABrYOTCyNAgAA7IClUQAAAAxsPcIEAABgBwQmAAAAAwITAACAAYEJAADAgMAEAABgQGACAERdfb00aZKUlCQNGSLt2mV1RcDpEZgAAFH31lvSK69IBw5If/ubNHGi1RUBp0dgAgBE3d69p98H7MbWgYmZvgHg7HTjjdKP5yG+6y7ragGagpm+AQCW2L5dWr5c6t1bGj7c6mqA04u1ugAAQOvUq9eJDWgJbP1IDgAAwA4ITAAAAAYEJgAAAIOoBaYvv/xS+fn5crvdcrlcuvTSS1VVVRWt7gEAAM5YVALT9u3bNWTIEPXt21erVq3SZ599pqeeekrt2rWLRvcAAAAhicq0AuPGjVNcXJzeeuutM7qeaQUAAICVIj7CVF9frz//+c+64IILlJubq65duyo7O1uLFi2KdNcAAABhEfHAdPDgQR0+fFglJSW65pprtGzZMl1//fW64YYbtHr16kav8fv98vl8DTYAAACrhD0wlZWVKT4+PrhVVlZKkkaPHq3JkycrIyNDTzzxhK699lq99tprjbZRXFwst9sd3DweT7jLBAAAaLKwz/Sdn5+v7Ozs4H6XLl0UGxur9PT0Buf169dPa9eubbSNwsJCTZkyJbjv8/kITQAAwDJhD0wul0sul6vBsaysrOBI0w+2bt2qnj17NtqG0+mU0+kMd2kAAABnJCpryU2dOlVjx47VFVdcoSuvvFJLlizR4sWLtWrVqmh0DwAAEJKoTCsgSXPmzFFxcbH27NmjPn366Je//KVGjx7dpGuZVgAAAFgpaoEpFAQmAABgJdaSAwAAMCAwAQAAGBCYAAAADAhMAAAABrYOTKWlpUpPT1dWVpbVpQAAgFaMb8kBAAAY2HqECQAAwA4ITAAAAAYEJgAAAAMCEwAAgAGBCQAAwIDABAAAYEBgAgAAMCAwAQAAGBCYAAAADGwdmFgaBQAA2AFLowAAABjYeoQJAADADghMAAAABgQmAAAAAwITAACAAYEJAADAgMAEAABgQGACAAAwIDABAAAY2DowMdM3AACwA2b6BgAAMLD1CBMAAIAdEJgAAAAMCEwAAAAGBCYAAACDqASmw4cP68EHH1T37t3Vvn179evXTzNnzoxG1wAAACGLjUYnkydP1sqVK/X2228rNTVVy5Yt0wMPPKDk5GSNHj06GiUAAACcsaiMMK1bt07jx4/XsGHDlJqaqvvuu0+DBg3SJ598Eo3uAQAAQhKVwDRkyBCVl5dr7969CgQCWrlypbZu3arc3NxodA8AABCSqDySe/nll3Xvvfeqe/fuio2NVZs2bfT6669ryJAhjZ7v9/vl9/uD+z6fLxplAgAANCrsI0xlZWWKj48PbmvWrNHLL7+s9evXq7y8XBs2bNDzzz+vBx54QB988EGjbRQXF8vtdgc3j8cT7jIBAACaLOxLo9TW1urAgQPB/ZSUFLndbi1cuFB5eXnB4/fcc4/27NmjJUuWnNRGYyNMHo+HpVEAAIAlwv5IzuVyyeVyBfd9Pp+OHj2qNm0aDmbFxMSovr6+0TacTqecTme4SwMAADgjEX+HKSEhQUOHDtXUqVPVvn179ezZU6tXr9abb76pF154IdLdAwAAhCzsj+Qas3//fhUWFmrZsmWqqalRz549dd9992ny5MlyOBzG630+n9xuN4/kAACAJaISmEJFYAIAAFZiLTkAAAADAhMAAIABgQkAAMCAwAQAAGBAYAIAADCwdWAqLS1Venq6srKyrC4FAAC0YkwrAAAAYGDrESYAAAA7IDABAAAYEJgAAAAMCEwAAAAGBCYAAAADAhMAAIABgQkAwuiZZ6TBg6X77pMOH7a6GgDhEmt1AQBwtpgzR3rqqROf162THA7pd7+ztiYA4WHrESZm+gbQkmze3HD/iy+sqQNA+Nk6MBUUFGjLli2qqKiwuhQAMBo58sSo0g/y8qyrBUB48UgOAMJk+HBp2TJp6VKpf3/pzjutrghAuLCWHAAAgIGtH8kBAADYAYEJAADAgMAEAABgQGACAAAwIDABAAAYEJgAAAAMCEwAAAAGtg5MLI0CAADsgIkrAQAADGw9wgQAAGAHBCYAAAADAhMAAIABgQkAAMAg5MC0YMEC5ebmqnPnznI4HNq0adNJ5/j9fk2aNEmdO3dWhw4dlJ+frz179oTaNQAAQFSEHJjq6uqUk5OjkpKSU57zyCOPaOHChZo/f77Wrl2rw4cP69prr9Xx48dD7R4AACDiwjatwM6dO5WWlqZPP/1UGRkZweNer1ddunTRW2+9pbFjx0qSqqur5fF49Je//EW5ubnGtplWAAAAWCni7zBt2LBBR48e1YgRI4LHkpOTNWDAAH344YeNXuP3++Xz+RpsAAAAVol4YNq/f7/atm2rc889t8Hx8847T/v372/0muLiYrnd7uDm8XgiXSYAAMApNSswlZWVKT4+PritWbPmjDsOBAJyOByN/qywsFBerze47d69+4z7AQAACFVsc07Oz89XdnZ2cD8lJcV4TVJSko4cOaJvvvmmwSjTwYMHNXjw4EavcTqdcjqdzSkNAAAgYpo1wuRyudS7d+/g1r59e+M1F110keLi4rR8+fLgsX379umLL744ZWACAACwk2aNMDWmpqZGVVVVqq6uliRVVlZKOjGylJSUJLfbrbvvvluPPvqoEhMT1alTJz322GMaOHCghg8fHmr3AAAAERfyS9/l5eXKzMxUXl6eJGncuHHKzMzUa6+9FjxnxowZuu666zRmzBjl5OTonHPO0eLFixUTExNq9wAAABEXtnmYIol5mAAAgJVYSw4AAMCAwAQAAGBAYAIAADAgMAEAABjYOjCVlpYqPT1dWVlZVpcCAABaMb4lBwAAYGDrESYAAAA7IDABAAAYEJgAAAAMCEwAAAAGBCYAAAADAhMAAIABgQkAAMCAwAQAAGBg68DETN8AAMAOmOkbAADAwNYjTAAAAHZAYAIAADAgMAEAABgQmAAAAAwITAAAAAYEJgAAAAMCEwAAgAGBCQAAwIDABAAAYGDrwMTSKAAAwA5YGgUAAMDA1iNMAAAAdkBgAgAAMCAwAQAAGBCYAAAADEIOTAsWLFBubq46d+4sh8OhTZs2Nfh5TU2NJk2apD59+uicc85Rjx499NBDD8nr9YbaNQAAQFSEHJjq6uqUk5OjkpKSRn9eXV2t6upq/eY3v9Hnn3+uefPmacmSJbr77rtD7RoAACAqwjatwM6dO5WWlqZPP/1UGRkZpz33nXfe0W233aa6ujrFxsYa22ZaAQAAYCVzWomAH4LPqcKS3++X3+8P7vt8vmiVBqARR49K1dVSUpLkdFpdDQBEX9Rf+j506JCefvppTZw48ZTnFBcXy+12BzePxxPFCgH8WHW1NGCAlJoq9e4tVVZaXREARF+zAlNZWZni4+OD25o1a5rVmc/nU15entLT0zVt2rRTnldYWCiv1xvcdu/e3ax+AITP9OnS1q0nPu/ZIxUVWVoOAFiiWY/k8vPzlZ2dHdxPSUlp8rW1tbW65pprFB8fr4ULFyouLu6U5zqdTjkZ9wds4ejR0+8DQGvQrMDkcrnkcrma3YnP51Nubq6cTqfKy8vVrl27ZrcBwBqPPiq9996JR3OdOklPPml1RQAQfSG/9F1TU6OqqipVV1dLkir//wWHpKQkJSUlqba2ViNGjNB3332nt99+Wz6fL/gSd5cuXRQTExNqCQAiqFcv6csvTzyW69VLOvdcqysCgOgLeVqBefPmacKECScdnzZtmoqKirRq1SpdeeWVjV779ddfKzU11dgH0woAAAArhW0epkgiMAEAACuxlhwAAIABgQkAAMCAwAQAAGBAYAIAADCwdWAqLS1Venq6srKyrC4FAAC0YnxLDgAAwMDWI0wAAAB2QGACAAAwIDABAAAYEJgAAAAMCEwAAAAGBCYAAAADAhMAAIABgQkAAMDA1oGJmb4BAIAdMNM3AACAga1HmAAAAOyAwAQAAGBAYAIAADAgMAEAABgQmAAAAAwITAAAAAYEJgAAAAMCEwAAgAGBCQAAwMDWgYmlUQAAgB2wNAoAAICBrUeYAAAA7IDABAAAYEBgAgAAMCAwAQAAGIQcmBYsWKDc3Fx17txZDodDmzZtOuW5gUBAI0eOlMPh0KJFi0LtGgAAICpCDkx1dXXKyclRSUmJ8dwXX3xRDocj1C4BAACiKjbUBm6//XZJ0s6dO0973meffaYXXnhBFRUV6tatW6jdAgAARE3IgakpvvvuO91yyy165ZVXlJSUZDzf7/fL7/cH930+XyTLAwAAOK2ovPQ9efJkDR48WKNHj27S+cXFxXK73cHN4/FEuEIAAIBTa1ZgKisrU3x8fHBbs2aN8Zry8nKtWLFCL774YpP7KSwslNfrDW67d+9uTpkAAABh1axHcvn5+crOzg7up6SkGK9ZsWKFtm/fro4dOzY4fuONN+ryyy/XqlWrTrrG6XTK6XQ2pzQAAICIaVZgcrlccrlczergiSee0D333NPg2MCBAzVjxgyNGjWqWW0BAABYIeSXvmtqalRVVaXq6mpJUmVlpSQpKSmpwfafevToobS0tFC7BwAAiLiQX/ouLy9XZmam8vLyJEnjxo1TZmamXnvttZCLAwAAsANHIBAIWF2Eic/nk9vtltfrVUJCgtXlAACAVoa15AAAAAwITAAAAAYEJrRa//yn9Le/SYcOWV0JAMDuCExolTZulC64QBoyROrbV9q82eqKAAB2ZuvAVFpaqvT0dGVlZVldCs4yzz0nffvtic//+7/SCy9YWw8AwN5sHZgKCgq0ZcsWVVRUWF0KzjLt2p1+HwCAH7N1YAIipahI6t37xOd+/aQnn7S0HACAzYU80zfQEqWmSl99deKF786dpTb80wEAcBoEJrRaMTFS165WVwEAaAn4dzUAAIABgQkAAMCAwAQAAGBAYAIAADAgMAEAABjYOjAx0zcAALADRyAQCFhdhInP55Pb7ZbX61VCQoLV5QAAgFbG1iNMAAAAdkBgAgAAMCAwAQAAGBCYAAAADAhMAAAABgQmAAAAAwITAACAge0D05Yt0oUXnvg8Zozk91tbDwAAaH1sH5gmTZJ27TrxeelS6Xe/s7YeAADQ+tg6MJWWlurDD9Ml/XtpFK/XunoAAEDrZPulUf7nf6Rbb/Wpvt6t887z6uOPE9Sjh9VVAQCA1sTWI0ySNHastH79ic/r1omwdBrHjkn//d/STTdJs2dbXQ0AAGePWKsLaIo+fU78NzHR2jrs7qmnpJKSE5/ffVfq0EG69VZrawIA4Gxg+xEmNN26daffBwAAZ4bAdBa5/PLT7wMAgDMTcmBasGCBcnNz1blzZzkcDm3atKnR89atW6errrpKHTp0UMeOHTVs2DB9//33oXaPHykqkqZPP/EY7o03TsxbBQAAQhfyO0x1dXXKycnRzTffrHvvvbfRc9atW6drrrlGhYWF+u1vf6u2bdvqs88+U5s2DHCFU0yM9F//ZXUVAACcfcI2rcDOnTuVlpamTz/9VBkZGQ1+dumll+pnP/uZnn766TNq2+fzye12y+v1KiEhIRzlAgAANFnEh3gOHjyojz76SF27dtXgwYN13nnnaejQoVq7dm2kuwYAAAiLiAemHTt2SJKKiop07733asmSJfrpT3+qq6++Wtu2bWv0Gr/fL5/P12ADAACwSrMCU1lZmeLj44PbmjVrjNfU19dLkiZOnKgJEyYoMzNTM2bMUJ8+fTRnzpxGrykuLpbb7Q5uHo+nOWUCAACEVbNe+s7Pz1d2dnZwPyUlxXhNt27dJEnp6ekNjvfr109VVVWNXlNYWKgpU6YE9wOBgI4cOSKXy9WccgEAAMKiWYHJ5XI1O7SkpqYqOTlZlZWVDY5v3bpVI0eObPQap9Mpp9PZrH4AAAAiJeRpBWpqalRVVaXq6mpJCgajpKQkJSUlyeFwaOrUqZo2bZoGDRqkjIwMvfHGG/rqq6/0xz/+MdTuAQAAIi7kaQXmzZunCRMmnHR82rRpKioqCu6XlJSotLRUNTU1GjRokJ577jkNGTIklK4BAACiImzzMAEAAJytmGobAADAgMAEAABgQGACAAAwIDABAAAYEJgAAAAMCEwAAAAGBCYAAAADAhMAAIABgQkAAMCAwAQAAGBAYAIAADAgMAEAABj8H6l6JJOJLWr7AAAAAElFTkSuQmCC\n", "text/plain": [ "Graphics object consisting of 1 graphics primitive" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "points(enumerate(tt))" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": [ "#cela corrobore une complexité polynômiale en la dimension de la matrice" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "def gauss_ent(M):\n", " A=copy(M)\n", " n=A.nrows()\n", " for j in range(n):\n", " # Recherche du pivot\n", " if A[j,j]==0:\n", " for i in range(j+1,n):\n", " if A[i,j]!=0:\n", " A.swap_rows(i,j)\n", " break\n", " if A[j,j]==0:\n", " raise ValueError(\"non invertible matrix\")\n", " for i in range(j+1, n):\n", " c=-A[i,j]; A.rescale_row(i,A[j,j]); A.add_multiple_of_row(i, j, c)\n", " return A" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrr}\n", "48 & 52 & 87 & 80 & 31 \\\\\n", "30 & 90 & 71 & 89 & 48 \\\\\n", "92 & 96 & 52 & 20 & 28 \\\\\n", "15 & 19 & 80 & 71 & 77 \\\\\n", "33 & 87 & 41 & 89 & 60\n", "\\end{array}\\right)$ " ], "text/plain": [ "[48 52 87 80 31]\n", "[30 90 71 89 48]\n", "[92 96 52 20 28]\n", "[15 19 80 71 77]\n", "[33 87 41 89 60]" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrr}\n", "48 & 52 & 87 & 80 & 31 \\\\\n", "0 & 2760 & 798 & 1872 & 1374 \\\\\n", "0 & 0 & -15061632 & -17334528 & -3920256 \\\\\n", "0 & 0 & 0 & 31391807938560 & -104565789941760 \\\\\n", "0 & 0 & 0 & 0 & -9290509432193132582141952000\n", "\\end{array}\\right)$ " ], "text/plain": [ "[ 48 52 87 80 31]\n", "[ 0 2760 798 1872 1374]\n", "[ 0 0 -15061632 -17334528 -3920256]\n", "[ 0 0 0 31391807938560 -104565789941760]\n", "[ 0 0 0 0 -9290509432193132582141952000]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "M=random_matrix(ZZ,5,x=10,y=99); show(M); show(gauss_ent(M));" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [], "source": [ "#On voit bien que la taille des coefficients double en gros à chaque étape" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [], "source": [ "def gauss_b(M):\n", " A=copy(M).change_ring(QQ)\n", " n=A.nrows()\n", " for j in range(n):\n", " # Recherche du pivot\n", " if A[j,j]==0:\n", " for i in range(j,n):\n", " if A[i,j]!=0:\n", " A.swap_rows(i,j)\n", " break\n", " if A[j,j]==0:\n", " raise ValueError(\"non invertible matrix\")\n", " for i in range(j+1, n):\n", " c=-A[i,j]; A.rescale_row(i,A[j,j]); A.add_multiple_of_row(i, j, c);\n", " if j>0:\n", " A.rescale_row(i,1/A[j-1,j-1]);\n", " return A" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrr}\n", "48 & 52 & 87 & 80 & 31 \\\\\n", "30 & 90 & 71 & 89 & 48 \\\\\n", "92 & 96 & 52 & 20 & 28 \\\\\n", "15 & 19 & 80 & 71 & 77 \\\\\n", "33 & 87 & 41 & 89 & 60\n", "\\end{array}\\right)$ " ], "text/plain": [ "[48 52 87 80 31]\n", "[30 90 71 89 48]\n", "[92 96 52 20 28]\n", "[15 19 80 71 77]\n", "[33 87 41 89 60]" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrr}\n", "48 & 52 & 87 & 80 & 31 \\\\\n", "0 & 2760 & 798 & 1872 & 1374 \\\\\n", "0 & 0 & -313784 & -361136 & -81672 \\\\\n", "0 & 0 & 0 & 4936564 & -16443644 \\\\\n", "0 & 0 & 0 & 0 & 732193080\n", "\\end{array}\\right)$ " ], "text/plain": [ "[ 48 52 87 80 31]\n", "[ 0 2760 798 1872 1374]\n", "[ 0 0 -313784 -361136 -81672]\n", "[ 0 0 0 4936564 -16443644]\n", "[ 0 0 0 0 732193080]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(M) ;show(gauss_b(M));" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "732193080" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M.determinant()" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [], "source": [ "def gauss_b_det(M):\n", " A=copy(M.change_ring(QQ))\n", " n=A.nrows(); perm=1;\n", " for j in range(n):\n", " # Recherche du pivot\n", " if A[j,j]==0:\n", " for i in range(j+1,n):\n", " if A[i,j]!=0:\n", " A.swap_rows(i,j); perm=-perm;\n", " break\n", " if A[j,j]==0:\n", " return(0)\n", " for i in range(j+1, n):\n", " c=-A[i,j]; A.rescale_row(i,A[j,j]); A.add_multiple_of_row(i, j, c);\n", " if j>0:\n", " A.rescale_row(i,1/A[j-1,j-1]);\n", " return perm*A[n-1,n-1];" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}732193080$ " ], "text/plain": [ "732193080" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(gauss_b_det(M));" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [], "source": [ "range(1,5);" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrr}\n", "1 & 1 & 1 & 2 & 1 \\\\\n", "1 & 1 & 2 & 0 & 1 \\\\\n", "1 & 0 & 2 & 2 & 0 \\\\\n", "1 & 2 & 2 & 0 & 0 \\\\\n", "1 & 0 & 2 & 1 & 2\n", "\\end{array}\\right)$ " ], "text/plain": [ "[1 1 1 2 1]\n", "[1 1 2 0 1]\n", "[1 0 2 2 0]\n", "[1 2 2 0 0]\n", "[1 0 2 1 2]" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrr}\n", "1 & 1 & 1 & 2 & 1 \\\\\n", "0 & 2 & 1 & 0 & 2 \\\\\n", "0 & 0 & 1 & 1 & 0 \\\\\n", "0 & 0 & 0 & 2 & 1 \\\\\n", "0 & 0 & 0 & 0 & 1\n", "\\end{array}\\right)$ " ], "text/plain": [ "[1 1 1 2 1]\n", "[0 2 1 0 2]\n", "[0 0 1 1 0]\n", "[0 0 0 2 1]\n", "[0 0 0 0 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "M=matrice_inversible(5,corps=GF(3)); show(M); show(gauss(M));" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [], "source": [ "def gauss_det(M):\n", " A=copy(M)\n", " n=A.nrows(); perm=1;\n", " for j in range(n):\n", " # Recherche du pivot\n", " if A[j,j]==0:\n", " for i in range(j+1,n):\n", " if A[i,j]!=0:\n", " A.swap_rows(i,j); perm=-perm;\n", " break\n", " if A[j,j]==0:\n", " return(0)\n", " for i in range(j+1, n):\n", " A.add_multiple_of_row(i, j, -A[i,j]/A[j,j])\n", " return(perm*prod([A[i,i] for i in range(n)]))" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}2$ " ], "text/plain": [ "2" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}2$ " ], "text/plain": [ "2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(gauss_det(M)); show(M.determinant())" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [], "source": [ "def det_mod(M):\n", " A=copy(M); n=A.nrows();\n", " m=max(abs(A[i,j]) for i in range(n) for j in range(n));\n", " Maj=n^(n/2)*m^n;\n", " N=floor(log(2*Maj+1,2));\n", " P=Primes(); L=[P.unrank(i) for i in range(N)]\n", " D=[ZZ(gauss_det(copy(A).change_ring(GF(L[i])))) for i in range(N)]\n", " p=prod(L[i] for i in range(N)); res=crt(D,L);\n", " if res>Maj:\n", " return(res-p)\n", " return(res)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}-27261248$ " ], "text/plain": [ "-27261248" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}-27261248$ " ], "text/plain": [ "-27261248" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "M=random_matrix(ZZ,5,x=10,y=99); show(M.determinant()); show(det_mod(M));" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}22$ " ], "text/plain": [ "22" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(crt([0,1,2],[2,3,5]));" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "22%3; 22%5" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [], "source": [ "def det_mod1(M):\n", " A=copy(M); n=A.nrows();\n", " m=max(abs(A[i,j]) for i in range(n) for j in range(n));\n", " Maj=n^(n/2)*m^n;\n", " N=floor(2*Maj);\n", " P=Primes(); p=P.next(N);\n", " d=ZZ(gauss_det(A.change_ring(GF(p))));\n", " if d>Maj:\n", " return(d-p)\n", " return(d)" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}-27261248$ " ], "text/plain": [ "-27261248" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}-27261248$ " ], "text/plain": [ "-27261248" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(det_mod1(M)); show(M.determinant())" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "625 loops, best of 3: 129 μs per loop" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('gauss_det(copy(M).change_ring(QQ))')" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "625 loops, best of 3: 280 μs per loop" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('gauss_b_det(M)')" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "125 loops, best of 3: 3.94 ms per loop" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('det_mod(M)')" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "625 loops, best of 3: 1.13 ms per loop" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('det_mod1(M)')" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [], "source": [ "# On a du mal à voir l'apport de GB par rapport à Gauss classique sur cet exemple ; les méthodes modulaires sont moins rapides avec cette implémentation et en particulier la méthode modulaire à plusieurs nombres premiers est loin derrière" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [], "source": [ "M=random_matrix(ZZ,5,x=10^1000,y=10^1001)" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "125 loops, best of 3: 4.45 ms per loop" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('gauss_det(copy(M).change_ring(QQ))')" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "625 loops, best of 3: 816 μs per loop" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('gauss_b_det(M)')" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [], "source": [ "# GB est meilleur que Gauss classique, en accord avec le cours." ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [], "source": [ "M=random_matrix(ZZ,20,x=10^5,y=10^6)" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "25 loops, best of 3: 7.01 ms per loop" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('gauss_b_det(M)')" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5 loops, best of 3: 224 ms per loop" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('det_mod(M)')" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5 loops, best of 3: 786 ms per loop" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('det_mod1(M)')" ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [], "source": [ "# La version à plusieurs nombres premiers est plus performante que celle à un seul, mais GB est bien meilleur ! Cela ne reflète pas la compléxité théorique." ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.0", "language": "sage", "name": "sagemath" }, "language": "python", "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.8.10" } }, "nbformat": 4, "nbformat_minor": 2 }