<commit_before>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# ★ Systems Of Equations ★"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import modules\n",
    "import sys\n",
    "import numpy as np\n",
    "from scipy import linalg"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.1 Gaussian Elimination"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def naive_gaussian_elimination(matrix):\n",
    "    \"\"\"\n",
    "    A simple gaussian elimination to solve equations\n",
    "    \n",
    "    Args:\n",
    "        matrix : numpy 2d array\n",
    "        \n",
    "    Returns:\n",
    "        mat : The matrix processed by gaussian elimination\n",
    "        x   : The roots of the equation\n",
    "        \n",
    "    Raises:\n",
    "        ValueError:\n",
    "            - matrix is null\n",
    "        RuntimeError :\n",
    "            - Zero pivot encountered\n",
    "    \"\"\"\n",
    "    if matrix is None :\n",
    "        raise ValueError('args matrix is null')\n",
    "    \n",
    "    #Clone the matrix\n",
    "    mat = matrix.copy()\n",
    "    \n",
    "    # Row Size\n",
    "    n = mat.shape[0]\n",
    "    \n",
    "    # Column Size\n",
    "    m = mat.shape[1]\n",
    "    \n",
    "    # Gaussian Elimaination\n",
    "    for j in xrange(0, n):\n",
    "        if abs(mat[j , j]) == 0 :\n",
    "            raise RuntimeError('zero pivot encountered')\n",
    "        for i in xrange(j + 1, n):\n",
    "            mult = mat[i, j] / mat[j, j]\n",
    "            for k in xrange(j,m):\n",
    "                mat[i, k] = mat[i, k] - mult * mat[j, k]\n",
    "    \n",
    "    # Back Substitution\n",
    "    x = np.zeros(n, dtype=np.float)\n",
    "    for i in xrange(n - 1,-1,-1):\n",
    "        for j in xrange(i + 1, n):\n",
    "            mat[i, m-1] = mat[i ,m-1] - mat[i,j] * x[j]\n",
    "        x[i] = mat[i, m-1] / mat[i, i]\n",
    "        \n",
    "    return mat, x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example\n",
    "Solve equations\n",
    "\\begin{matrix}\n",
    "x + 2y - z = 3 & \\\\ \n",
    "2x + y - 2z = 3 & \\\\ \n",
    "-3x + y + z = -6 \n",
    "\\end{matrix}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "----------------------\n",
      "[[ 1.  2. -1.  3.]\n",
      " [ 0. -3.  0. -3.]\n",
      " [ 0.  0. -2. -4.]]\n",
      "----------------------\n",
      "[ 3.  1.  2.]\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Input:\n",
    "[[ 1  2 -1  3]\n",
    " [ 2  1 -2  3]\n",
    " [-3  1  1 -6]]\n",
    "\"\"\"\n",
    "input_mat = np.array([ 1, 2, -1, 3, 2, 1, -2, 3, -3, 1, 1, -6],dtype=np.float)\n",
    "input_mat = input_mat.reshape(3, 4)\n",
    "output_mat, x = naive_gaussian_elimination(input_mat)\n",
    "print('----------------------')\n",
    "print(output_mat)\n",
    "print('----------------------')\n",
    "print(x)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",<commit_msg>Add LU factorization<commit_after>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# ★ Systems Of Equations ★"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import modules\n",
    "import sys\n",
    "import numpy as np\n",
    "from scipy import linalg"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.1 Gaussian Elimination"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def naive_gaussian_elimination(matrix):\n",
    "    \"\"\"\n",
    "    A simple gaussian elimination to solve equations\n",
    "    \n",
    "    Args:\n",
    "        matrix : numpy 2d array\n",
    "        \n",
    "    Returns:\n",
    "        mat : The matrix processed by gaussian elimination\n",
    "        x   : The roots of the equation\n",
    "        \n",
    "    Raises:\n",
    "        ValueError:\n",
    "            - matrix is null\n",
    "        RuntimeError :\n",
    "            - Zero pivot encountered\n",
    "    \"\"\"\n",
    "    if matrix is None :\n",
    "        raise ValueError('args matrix is null')\n",
    "    \n",
    "    #Clone the matrix\n",
    "    mat = matrix.copy()\n",
    "    \n",
    "    # Row Size\n",
    "    n = mat.shape[0]\n",
    "    \n",
    "    # Column Size\n",
    "    m = mat.shape[1]\n",
    "    \n",
    "    # Gaussian Elimaination\n",
    "    for j in xrange(0, n):\n",
    "        if abs(mat[j , j]) == 0 :\n",
    "            raise RuntimeError('zero pivot encountered')\n",
    "        for i in xrange(j + 1, n):\n",
    "            mult = mat[i, j] / mat[j, j]\n",
    "            for k in xrange(j,m):\n",
    "                mat[i, k] = mat[i, k] - mult * mat[j, k]\n",
    "    \n",
    "    # Back Substitution\n",
    "    x = np.zeros(n, dtype=np.float)\n",
    "    for i in xrange(n - 1,-1,-1):\n",
    "        for j in xrange(i + 1, n):\n",
    "            mat[i, m-1] = mat[i ,m-1] - mat[i,j] * x[j]\n",
    "        x[i] = mat[i, m-1] / mat[i, i]\n",
    "        \n",
    "    return mat, x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example\n",
    "Solve equations\n",
    "\\begin{matrix}\n",
    "x + 2y - z = 3 & \\\\ \n",
    "2x + y - 2z = 3 & \\\\ \n",
    "-3x + y + z = -6 \n",
    "\\end{matrix}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "----------------------\n",
      "[[ 1.  2. -1.  3.]\n",
      " [ 0. -3.  0. -3.]\n",
      " [ 0.  0. -2. -4.]]\n",
      "----------------------\n",
      "[ 3.  1.  2.]\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Input:\n",
    "[[ 1  2 -1  3]\n",
    " [ 2  1 -2  3]\n",
    " [-3  1  1 -6]]\n",
    "\"\"\"\n",
    "input_mat = np.array([ 1, 2, -1, 3, 2, 1, -2, 3, -3, 1, 1, -6],dtype=np.float)\n",
    "input_mat = input_mat.reshape(3, 4)\n",
    "output_mat, x = naive_gaussian_elimination(input_mat)\n",
    "print('----------------------')\n",
    "print(output_mat)\n",
    "print('----------------------')\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.2 The LU Factorization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example\n",
    "Solve system\n",
    "\\begin{matrix}\n",
    "x + 2y - z = 3 & \\\\ \n",
    "2x + y - 2z = 3 & \\\\ \n",
    "-3x + y + z = -6 \n",
    "\\end{matrix}\n",
    " \n",
    " using the LU factorization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 3.  1.  2.]\n"
     ]
    }
   ],
   "source": [
    "A = np.array([ 1, 2, -1, 2, 1, -2, -3, 1, 1],dtype=np.float)\n",
    "A = A.reshape(3, 3)\n",
    "lu, piv = linalg.lu_factor(A)\n",
    "\n",
    "b = np.array([3, 3, -6])\n",
    "sol = linalg.lu_solve([lu, piv], b)\n",
    "print(sol)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example\n",
    "Find the LU factorization of the given matrices. Check by matrix multiplication\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "3 & 1 & 2 \\\\ \n",
    "6 & 3 & 4 \\\\ \n",
    "3 & 1 & 5\n",
    "\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 3.  1.  2.]\n",
      " [ 6.  3.  4.]\n",
      " [ 3.  1.  5.]]\n",
      "--------------------\n",
      "[[ 1.   0.   0. ]\n",
      " [ 0.5  1.   0. ]\n",
      " [ 0.5  1.   1. ]]\n",
      "--------------------\n",
      "[[ 6.   3.   4. ]\n",
      " [ 0.  -0.5  0. ]\n",
      " [ 0.   0.   3. ]]\n",
      "--------------------\n",
      "[[ 3.  1.  2.]\n",
      " [ 6.  3.  4.]\n",
      " [ 3.  1.  5.]]\n"
     ]
    }
   ],
   "source": [
    "A = np.array([3, 1, 2, 6, 3, 4, 3, 1, 5], dtype=np.float).reshape(3,3)\n",
    "P, L, U = linalg.lu(A)\n",
    "print(A)\n",
    "print('--------------------')\n",
    "print(L)\n",
    "print('--------------------')\n",
    "print(U)\n",
    "print('--------------------')\n",
    "print(np.matmul(P,np.matmul(L, U)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example\n",
    "Solve the system by LU factorization\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "3 & 1 & 2 \\\\ \n",
    "6 & 3 & 4 \\\\ \n",
    "3 & 1 & 5\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "x_1 \\\\ \n",
    "x_2 \\\\ \n",
    "x_3\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "0 \\\\ \n",
    "1 \\\\ \n",
    "3\n",
    "\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "too many values to unpack",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-25-c23b4dd38788>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0mb\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0marray\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0mlu\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpiv\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlinalg\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlu_factor\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mA\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlinalg\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlu_solve\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mA\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mb\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m/usr/local/lib/python2.7/dist-packages/scipy/linalg/decomp_lu.pyc\u001b[0m in \u001b[0;36mlu_solve\u001b[0;34m(lu_and_piv, b, trans, overwrite_b, check_finite)\u001b[0m\n\u001b[1;32m    109\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    110\u001b[0m     \"\"\"\n\u001b[0;32m--> 111\u001b[0;31m     \u001b[0;34m(\u001b[0m\u001b[0mlu\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpiv\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlu_and_piv\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    112\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mcheck_finite\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    113\u001b[0m         \u001b[0mb1\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0masarray_chkfinite\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mb\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mValueError\u001b[0m: too many values to unpack"
     ]
    }
   ],
   "source": [
    "A = np.array([3, 1, 2, 6, 3, 4, 3, 1, 5], dtype=np.float).reshape(3,3)\n",
    "b = np.array([0, 1, 3])\n",
    "lu, piv = linalg.lu_factor(A)\n",
    "x = linalg.lu_solve(A, b)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
{'fraction_non_alphanumeric': 0.266065210509655, 'fraction_numerical': 0.08103830326052548, 'mean_word_length': 1.6841546304163126, 'pattern_counts': {'":': 121, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2200665', 'n_tokens_mistral': 6274, 'n_tokens_neox': 5693, 'n_words': 931}