pbe.ipynb

{
 "metadata": {
  "name": "pbe"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "$\\beta(i_1,j_1,k_1,i-i_1,j-j_1,k-k_1) \\approx \\sum_{\\alpha=1}^r \\Phi_{\\alpha}(i_1,j_1,k_1)\\Phi_{\\alpha}(i-i_1,j-j_1,k-k_1)$\n\nFor $n = 16$ $r = 6$ (for accuracy $\\varepsilon=10^{-6}$)\nReduction in storage:  \nInstead of  \n$n^6$ we have $2n^3 r$\n\n$16^6 = 16777216$, whereas  \n$2 \\cdot 16^3 = 49152$ "
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "$$\\phi(i,j,k) = \\sum_{i_1=1}^{i-1} \\sum_{j_1=1}^{j-1} \\sum_{k_1=1}^{k-1} \\beta(i_1,j_1,k_1,i-i_1,j-j_1,k-k_1) F(i_1,j_1,k_1) F(i-i_1,j-j_1,k-k_1)$$\n\n$$\\phi(i,j,k) = \\sum_{\\alpha=1}^r \\Big(\\sum_{i_1=1}^{i-1}\\sum_{j_1=1}^{j-1} \\sum_{k_1=1}^{k-1}  \\Phi_{\\alpha}(i_1,j_1,k_1)\\Phi_{\\alpha}(i-i_1,j-j_1,k-k_1)F(i_1,j_1,k_1) F(i-i_1,j-j_1,k-k_1)\\Big)$$\n\n"
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "\\begin{equation}\n\\phi_{\\alpha}(i,j,k) = \\sum_{i_1=1}^{i-1}\\sum_{j_1=1}^{j-1} \\sum_{k_1=1}^{k-1}  \\Phi_{\\alpha}(i_1,j_1,k_1)\\Phi_{\\alpha}(i-i_1,j-j_1,k-k_1)F(i_1,j_1,k_1) F(i-i_1,j-j_1,k-k_1)\n\\end{equation}\n\nWe can introduce  new variable:  \n\\begin{equation}\n\\widehat{F}_{\\alpha}(i,j,k) = \\Phi_{\\alpha}(i,j,k) F(i,j,k)\n\\end{equation}\n\n\\begin{equation}\n\\phi_{\\alpha}(i,j,k) = \\sum_{i_1=1}^{i-1}\\sum_{j_1=1}^{j-1} \\sum_{k_1=1}^{k-1}  \\widehat{F}_{\\alpha}(i_1,j_1,k_1) \\widehat{F}_{\\alpha}(i-i_1,j-j_1,k-k_1)\n\\end{equation}\n\nThis is a convolution, and it can be done in $\\mathcal{O}(n^3 \\log n)$ operations (using the FFT).  \nThe total complexity would be $\\mathcal{O}(n^3 \\log n r)$ operations.  \n\nIt was $\\mathcal{O}(n^6)$ operations for the loop.\n\n"
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "$$v(i) = \\sum_{j=1}^{i-1} f(j) g(i-j)$$ \n\n$$ G = \\begin{pmatrix}\n0 & 0 & 0 & 0 \\\\\ng_1  & 0 & 0 & 0\\\\\ng_2 & g_1 & 0 & 0 \\\\\ng_3 & g_2 & g_1 & 0\n\\end{pmatrix},\n$$\n\nThen\n$$\n  v = Gf.\n$$\n\n\\begin{equation} \nG = \\begin{pmatrix}\n0   & 0   & 0   & 0  & g_3 & g_2 & g_1\\\\\ng_1 & 0   & 0   & 0  & 0   & g_3 & g_2\\\\\ng_2 & g_1 & 0   & 0  & 0   & 0   & g_3 \\\\\ng_3 & g_2 & g_1 & 0  & 0   & 0   & 0 \\\\\n0   & g_3 & g_2 & g_1& 0   & 0   & 0 \\\\  \n0   & 0   & g_3 & g_2& g_1 & 0   & 0 \\\\\n0   & 0   & 0   & g_3& g_2 & g_1 & 0 \\\\\n\\end{pmatrix},\n\\end{equation}\n"
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "# GIT"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "",
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}