On the Parallelization of Subproduct-tree TechniquesWe compute the complexity of different algorithms based on the subproduct tree technique. Specifically evaluation and interpolation.We partition all of the major algorithms (subproduct tree, evaluation (+subinverse tree) and interpolation) into plain arithmetics and FFT-based arithmetics. (Each of them could be doing nothing). We call this threshold in which the arithmetics will be switched in to another H. All of the complexity estimates are depending on this H. At last we want to investigate what's the optimum H to get faster implementation.
## Number of Polys at level i of the subproduct-tree.
polyno := proc(i,k)
RETURN(2^(k-i));
end proc:
## Length of each poly at level i of the subproduct-tree.
QyQ+SStwb2x5TGVuZ3RoRzYiZio2I0kiaUdGJUYlRiVGJS1JJ1JFVFVSTkclKnByb3RlY3RlZEc2IywmKSIiIzkkIiIiRjFGMUYlRiVGJSEiIg==
## Cost for plain multiplication of polys with length of d.
Qyo+SS9tdWx0aWNvc3ROYWl2ZUc2ImYqNiNJImRHRiVGJUYlRiUtSSdSRVRVUk5HJSpwcm90ZWN0ZWRHNiMsKCokOSQiIiNGMEYvISIjIiIiRjJGJUYlRiUhIiI+STJtdWx0aWNvc3RGRlRGaXhlZEdGJWYqRic2J0kibEdGJUkibUdGJUkickdGJUkiQ0dGJUkjZDBHRiVGJUYlQyY+OCQtSSlzaW1wbGlmeUdGJTYjLCZGL0YwRjFGMj44JSYtSSNvcEdGKzYjRj82I0YwPjgnLCYqJkY/RjJGRUYyIiM6Rj9GMC1GKjYjRkxGJUYlRiVGMz5JLXBsYWluRGl2Q29zdEdGJWYqNiRJI2wxR0YlSSNsMkdGJTYkRjhGO0YlRiVDJT5GPywoOSVGMkYvRjNGMkYyPkZFLCQqJkY/RjJGL0YyRjAtRio2I0ZFRiVGJUYlRjM+STBjb21wdXRlT3B0aW11bUhHRiVmKjYjSSJGR0YlNihJJE1JTkdGJUkiS0dGJUY5SSJoR0YlSSJlR0YlSSRpbmRHRiVGJUYlQyQ+Rj8iNisrKysrKysrKysiPyhGRSIiJUYyIiNCSSV0cnVlR0YrQyU+OCZGPz8oRkwiIiFGMkZFRl1wQyQ+OCgtSSVldmFsR0YrNiRGLzclL0kiSEdGJUZML0kia0dGJUZFL0kibkdGJSlGMEZFQCQyRmVwRmBwQyQ+RmBwRmVwPjgpRkwtSSZwcmludEdGKzYjRmZxRiVGJUYlRjM=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=NiI=Subproduct TreeWe compute complexity of constructing subprocut tree using different methods for multiplications (Plain and FFT) in which up to level H, all of the arithmetics are based on plain multiplications; and from H to the root of the trees, FFT-based multiplication is used.Here's some notes about our representations:** By passing e to the procedures, we mean the level in which we have 2^e polynomials.** We pass the multiplication cost as an input to the procedure which is the cost for multiplying to polynomial which is going to be FFT-based or Naive.QyQ+ST9zdWJwcm9kdWN0VHJlZUNvbnN0cnVjdGlvbkNvc3RHNiJmKjYmSSJrR0YlSSNlMUdGJUkjZTJHRiVJIk1HRiVGJUYlRiUtSSdSRVRVUk5HJSpwcm90ZWN0ZWRHNiMtSSRzdW1HRiU2JComLUkncG9seW5vR0YlNiRJImlHRiU5JCIiIi05JzYjLUkrcG9seUxlbmd0aEdGJTYjLCZGN0Y5ISIiRjlGOS9GNzssKEY4Rjk5JkZBRjlGOSwmRjhGOTklRkFGJUYlRiVGQQ==QywtST9zdWJwcm9kdWN0VHJlZUNvbnN0cnVjdGlvbkNvc3RHNiI2Jkkia0dGJSwmRiciIiJJI0gyR0YlISIiLCZGJ0YpSSNIMUdGJUYrSSJNR0YlRik+SSZDX2xvd0dGJS1JKXNpbXBsaWZ5R0YlNiMtRiQ2JkYnIiIhLCZGJ0YpSSJIR0YlRitJMm11bHRpY29zdEZGVEZpeGVkR0YlRiktSSZsYXRleEdGJTYjSSIlR0YlRik+SSdDX2hpZ2hHRiUtRjI2Iy1GJDYmRidGN0YnSS9tdWx0aWNvc3ROYWl2ZUdGJUYpRjpGKQ==LUkjbWlHNiMvSSttb2R1bGVuYW1lRzYiSSxUeXBlc2V0dGluZ0dJKF9zeXNsaWJHRic2JlEoR2VuZXJhbEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnQyo+SSJmRzYiLUklZXZhbEclKnByb3RlY3RlZEc2JC1JKXNpbXBsaWZ5RzYkRihJKF9zeXNsaWJHRiU2IywmSSdDX2hpZ2hHRiUiIiJJJkNfbG93R0YlRjE3Ji8pIiIjSSJrR0YlSSJuR0YlLykiIiVGNyokRjhGNi8pRjYsJiEiIkYxRjdGMSwkRjgjRjFGNi8pRjYsJkkiSEdGJUYxRjdGMSomKUY2RkZGMUY4RjFGQD5GJC1GKzYjRiRGQD5GJC1JKGNvbGxlY3RHRiw2JEYkRjhGMS1JJmxhdGV4R0YsNiNJIiVHRiVGMQ==QzAtSTBjb21wdXRlT3B0aW11bUhHNiI2I0kiZkdGJSIiIj5JK1NwYWNlUmVxU1BHRiUsJi1JJHN1bUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYkKiYtSSdwb2x5bm9HRiU2JEkiaUdGJUkia0dGJUYoLUkrcG9seUxlbmd0aEdGJTYjRjZGKC9GNjsiIiFJIkhHRiVGKC1GLTYkKiZGM0YoLCZGOEYoISIiRihGKC9GNjssJkY+RihGKEYoRjdGKEYoLUkmbGF0ZXhHRi42I0kiJUdGJUYoPkkvU3BhY2VSZXFTUGhpZ2hHRiVGP0YoRkdGKD5JLlNwYWNlUmVxU1Bsb3dHRiVGLEYoRkdGKA==LUkjbWlHNiMvSSttb2R1bGVuYW1lRzYiSSxUeXBlc2V0dGluZ0dJKF9zeXNsaWJHRic2J1E1Tm9+cGxhaW5+YXJpdGhtZXRpYzpGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2ZvcmVncm91bmRHUS5bMTQ0LDE0NCwxNDRdRicvJTBmb250X3N0eWxlX25hbWVHUTAyRH5JbmVydH5PdXRwdXRGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRic=QyYtSSVldmFsRyUqcHJvdGVjdGVkRzYkSSJmRzYiNyUvSSJIR0YoIiIhLykiIiMsJiEiIiIiIkkia0dGKEYxLCQqJEkibkdGKEYxRi8vKUYvLCZGM0YyRjJGMiwkRjZGL0YxLUkoY29sbGVjdEc2JEYlSShfc3lzbGliR0YoNiQtRiQ2JEkiJUdGKDcjLylGL0YzRjZGNkYyeval(f, [H=k]): eval(%, [2^(2 * k) = n^2, 2^(k+1)=2*n]);Evaluation (+subinverse tree) This is the complexity for evaluating a polynomial with existing subproduct tree and traversing in top-down manner. For this we create the subinverse tree from level H to the root. So the threshhold H is going to be determined by the optimum cost for evaluating the polynomial. (we do the plain arithmetics below H and FFT-based arithmetic at levels > H in the top-down approach)LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=Qyo+SS9FdmFsdWF0aW9uQ29zdEc2ImYqNiZJImtHRiVJI2UxR0YlSSNlMkdGJUkiTUdGJUYlRiVGJS1JJ1JFVFVSTkclKnByb3RlY3RlZEc2Iy1JJHN1bUc2JEYuSShfc3lzbGliR0YlNiQsJComLUkncG9seW5vR0YlNiRJImlHRiU5JCIiIiwmLTknNiMtSStwb2x5TGVuZ3RoR0YlNiNGOkY8RkEiIiVGPCIiIy9GOjssJkY7Rjw5JiEiIiwmRjtGPDklRkpGJUYlRiVGSj5JNEV2YWx1YXRpb25Db3N0UGxhaW5HRiVmKjYjSSJIR0YlRiVGJUYlLUYtNiMtRjE2JComLUY4NiRGOkYoRjwtSS1wbGFpbkRpdkNvc3RHRiU2JClGRUY6LCYpRkUsJkY6RjxGPEY8RjxGSkY8RjwvRjo7IiIhLCZGO0Y8RkpGPEYlRiVGJUZKPkkvc3ViaW52ZXJzZUNvc3RHRiVmKjYkRihJImhHRiU2JEklYmFzZUdGJUkiQ0dGJUYlRiVDJT44JComLUY4NiRGTEY7RjwtSS9JbnZGcm9tU2NyYXRjaEdGJTYjLUZCNiNGTEY8PjglLUYxNiQqJkY3RjwsKC1JMm11bHRpY29zdEZGVEZpeGVkR0YlNiMsJilGRSwmRjpGPEZKRjxGPEY8RjxGRUZobkY8LUZocDYjLCZGZm5GPEY8RjxGPEY8L0Y6OywmRkxGPEY8RjxGXW8tRi02IywmRmJwRjxGaG9GPEYlRiVGJUZKPkZdcGYqRlA2I0klY29zdEdGJUYlRiVDJD5GaG8sJiIiJEY8LUYxNiQsKC1JL211bHRpY29zdE5haXZlR0YlNiNGW3FGRUZbcUY8RmZuRjwvRjo7RkVGO0Y8LUYtNiNGaG9GJUYlRiVGSg==Q0A+STRzdWJpbnZlcnNlVG90YWxDb3N0RzYiLUkvc3ViaW52ZXJzZUNvc3RHRiU2JEkia0dGJUkiSEdGJSIiIi1JKXNpbXBsaWZ5RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiNJIiVHRiVGKy1JJmxhdGV4R0YuRjFGKz5JNnN1YmludmVyc2VTY3JhdGNoQ29zdEdGJSomLUkncG9seW5vR0YlNiRGKkYpRistSS9JbnZGcm9tU2NyYXRjaEdGJTYjLUkrcG9seUxlbmd0aEdGJTYjRipGK0YrRixGK0YzRis+STRzdWJpbnZlcnNlVXBwZXJDb3N0R0YlLUkkc3VtR0YuNiQqJi1GOTYkSSJpR0YlRilGKywoLUkybXVsdGljb3N0RkZURml4ZWRHRiU2IywmKSIiIywmRklGKyEiIkYrRitGK0YrRlApRlAsJkZJRitGK0YrRistRkw2IywmKUZQRklGK0YrRitGK0YrL0ZJOywmRipGK0YrRissJkZSRitGKUYrRitGLEYrRjNGKz5JJkVfbG93R0YlLUYtNiMtSS9FdmFsdWF0aW9uQ29zdEdGJTYmRikiIiEsJkYpRitGKkZSRkxGK0YzRis+SSdFX2hpZ2hHRiUtRi02Iy1JNEV2YWx1YXRpb25Db3N0UGxhaW5HRiVGQEYrRjNGKz5JJ0VfY29zdEdGJS1JJWV2YWxHRi82JC1GLTYjLCZGaG5GK0Zhb0YrNyUvKUZQRilJIm5HRiUvKUZQLCZGKkYrRilGKyomKUZQRipGK0ZhcEYrLykiIiVGKSokRmFwRlBGK0YzRis=QyQtSTBjb21wdXRlT3B0aW11bUhHNiI2I0knRV9jb3N0R0YlIiIiInterpolation (Linear Combination)For interpolation we use linear combination in which we build a tree from leaves using subproduct-tree. For computing polynomial at level i, we will cross-multiply every pair of polynomials of the interpolation-tree at level (i-1) with the corresponding pair of polynomials of the subproduct-tree at level (i-1), and add the results together. So we would have kind of the same threshold H as we had for the subproduct tree.Here we compute the complexity of this operation:QyQ+STNMaW5lYXJDb21pYmluYXRpb25HNiJmKjYmSSJrR0YlSSNlMUdGJUkjZTJHRiVJIk1HRiVGJUYlRiUtSSdSRVRVUk5HJSpwcm90ZWN0ZWRHNiMtSSRzdW1HNiRGLkkoX3N5c2xpYkdGJTYkLCYpIiIjOSQiIiIqJi1JJ3BvbHlub0dGJTYkSSJpR0YlRjhGOS05JzYjLUkrcG9seUxlbmd0aEdGJTYjLCZGPkY5ISIiRjlGOUY3L0Y+OywmRjhGOTkmRkYsJkY4Rjk5JUZGRiVGJUYlRkY=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=I_low := simplify(LinearComibination(k, 0, k-H, multicostFFTFixed));simplify(%);latex(%);
I_high := simplify(LinearComibination(k, k-H, k, multicostNaive));simplify(%);latex(%);
I_cost := eval(simplify(I_low+I_high),[2^k=n]);latex(%);
QyQtSTBjb21wdXRlT3B0aW11bUhHNiI2Iy1JL3N1YmludmVyc2VDb3N0R0YlNiRJImtHRiVJIkhHRiUiIiI=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=