Span Overhead Speedup for polynomial evaluation and interpolation using subproduct treeCore routineWe are given n = 2^k points to evaluatepoints := n;n := 2^k;Given a length 2^i, the fft based multiplications are done such that the result is in length 2^i. FFTmulSpan := proc(i)
return 15*i+2;
end proc;FFTmulOverhead:=proc(i)
return 36*i-21;
end proc;
JSFH2^i > zQyQ+SShGRlRtdWxORzYiZio2JEkiaUdGJUkiekdGJUYlRiVGJU8sJiomKSIiIzkkIiIiOSUhIiJGLiooRi9GMEYtRjBGMUYyIiIpRiVGJUYlRjA=QyQ+SShGRlRtdWxMRzYiZio2JEkiaUdGJUkiekdGJUYlRiVGJU8sJiIiIyIiIjkkIiIpRiVGJUYlRi0=2^i <zQyQ+SS1QbGFpbk11bFNwYW5HNiJmKjYjSSJpR0YlRiVGJUYlTywmKSIiIzkkIiIiRi5GLkYlRiVGJUYuQyQ+STFQbGFpbk11bE92ZXJoZWFkRzYiZio2I0kiaUdGJUYlRiVGJU8iIiNGJUYlRiUiIiI=QyQ+SSpQbGFpbk11bE5HNiJmKjYlSSJpR0YlSSJrR0YlSSJ6R0YlRiVGJUYlTyooOSYiIiIpIiIjLCY5JUYuOSQhIiJGLiwmKUYwLCZGM0YuRi5GLkYuRi5GLkY0RiVGJUYlRi4=QyQ+SSpwbGFpbk11bExHNiJmKjYjSSJpR0YlRiVGJUYlTyIiIkYlRiVGJUYqSubproduct treePlainplain_level := H;JSFHSPtSpanPlain:= sum(PlainMulSpan(i),i=1..H);latex(%);SPtOverheadPlain := sum(PlainMulOverhead(i),i=1..H)*U;latex(%);QyQ+SSpTUHRQbGFpbk5HNiJmKjYlSSJrR0YlSSJ6R0YlSSJIR0YlRiVGJUYlTy1JJHN1bUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYkLUkqUGxhaW5NdWxOR0YlNiVJImlHRiU5JDklL0Y1OyIiIjkmRiVGJUYlRjo=QyQ+SSpTUHRQbGFpbkxHNiItSSRzdW1HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2JC1JKnBsYWluTXVsTEdGJTYjSSJpR0YlL0YvOyIiIkkiSEdGJUYyQyQ+SSpTUHRQbGFpbkNHNiIsJkktU1B0U3BhblBsYWluR0YlIiIiKiZJMVNQdE92ZXJoZWFkUGxhaW5HRiVGKEkiVUdGJUYoRihGKA==FFT
QyY+SStTUHRTcGFuRkZURzYiLUkkc3VtRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiQsJi1JK0ZGVG11bFNwYW5HRiU2I0kiaUdGJSIiIiIiI0YxL0YwOywmSSJIR0YlRjFGMUYxSSJrR0YlRjEtSSZsYXRleEdGKDYjSSIlR0YlRjE=QyY+SS9TUHRPdmVyaGVhZEZGVEc2IiomLUkkc3VtRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiQsJi1JL0ZGVG11bE92ZXJoZWFkR0YlNiNJImlHRiUiIiIiIiVGMi9GMTssJkkiSEdGJUYyRjJGMkkia0dGJUYySSJVR0YlRjJGMi1JJmxhdGV4R0YpNiNJIiVHRiVGMg==QyQ+SShTUHRGRlRuRzYiZio2JUkia0dGJUkiekdGJUkiSEdGJUYlRiVGJU8tSSRzdW1HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2JComLCYtSShGRlRtdWxOR0YlNiRJImlHRiU5JSIiIiomKSIiIywmRjdGOSEiIkY5RjlGOEY+RjlGOSlGPCwmOSRGOUY3Rj5GOS9GNzssJjkmRjlGOUY5RkFGJUYlRiVGOQ==QyQ+SShTUHRGRlRsRzYiLUkkc3VtRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiQsJi1JKEZGVG11bExHRiU2JEkiaUdGJUkiekdGJSIiIkYyRjIvRjA7LCZJIkhHRiVGMkYyRjJJImtHRiVGMg==QyQ+SShTUHRGRlRjRzYiLCZJK1NQdFNwYW5GRlRHRiUiIiIqJkkvU1B0T3ZlcmhlYWRGRlRHRiVGKEkiVUdGJUYoRihGKA==CONCLUSION:
SPAN + OVERHEADQyY+SShTUHRTcGFuRzYiLCZJLVNQdFNwYW5QbGFpbkdGJSIiIkkrU1B0U3BhbkZGVEdGJUYoRigtSSZsYXRleEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYjSSIlR0YlRig=QyY+SSxTUHRPdmVyaGVhZEc2IiwmSTFTUHRPdmVyaGVhZFBsYWluR0YlIiIiSS9TUHRPdmVyaGVhZEZGVEdGJUYoRigtSSZsYXRleEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYjSSIlR0YlRig=QyQ+SSVTUHRORzYiLCYtSSpTUHRQbGFpbk5HRiU2JUkia0dGJUkiekdGJUkiSEdGJSIiIi1JKFNQdEZGVG5HRiVGKUYtRi0=QyQ+SSVTUHRMRzYiLCZJKlNQdFBsYWluTEdGJSIiIkkoU1B0RkZUbEdGJUYoRig=QyQ+SSVTUHRDRzYiLCZJKlNQdFBsYWluQ0dGJSIiIkkoU1B0RkZUY0dGJUYoRig=QyQ+SStTUHRTcGVlZFVwRzYiKiYsJiomSSVTUHROR0YlIiIiSSJQR0YlISIiRipJJVNQdExHRiVGKkYqSSVTUHRDR0YlRipGKg==Subinverse treesratchSItSpanScratch := 2*(2^H -1) + 2*2^H*(2^H +1);simplify(%);latex(%);SItOverheadScratch := (2^H +1 +2^H)*U;simplify(%);latex(%);SItScratchN := 2^(k-H)/z;
QyQ+SSxTSXRTY3JhdGNoTEc2IiIiIkYmQyQ+SSxTSXRTY3JhdGNoQ0c2IiwmSS9TSXRTcGFuU2NyYXRjaEdGJSIiIiomSTNTSXRPdmVyaGVhZFNjcmF0Y2hHRiVGKEkiVUdGJUYoRihGKA==Qyg+SS1TSXRTcGFuT3ZlckhHNiItSSRzdW1HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2JCwoLUkrRkZUbXVsU3BhbkdGJTYjSSJpR0YlIiIkLUYuNiMsJkYwIiIiISIiRjUiIiMiIiVGNS9GMDssJkkiSEdGJUY1RjVGNSwmSSJrR0YlRjVGNkY1RjUtSSlzaW1wbGlmeUdGKDYjSSIlR0YlRjUtSSZsYXRleEdGKEZBRjU=Qyg+STFTSXRPdmVyaGVhZE92ZXJIRzYiKiYtSSRzdW1HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2JCwoLUkvRkZUbXVsT3ZlcmhlYWRHRiU2I0kiaUdGJSIiJC1GLzYjLCZGMSIiIiEiIkY2IiIjIiM3RjYvRjE7LCZJIkhHRiVGNkY2RjYsJkkia0dGJUY2RjdGNkY2SSJVR0YlRjZGNi1JKXNpbXBsaWZ5R0YpNiNJIiVHRiVGNi1JJmxhdGV4R0YpRkNGNg==QyQ+SSpTSXROb3ZlckhHNiJmKjYlSSJrR0YlSSJ6R0YlSSJIR0YlRiVGJUYlTy1JJHN1bUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYkKiYsKC1JKEZGVG11bE5HRiU2JEkiaUdGJTklIiIkLUY1NiQsJkY3IiIiISIiRj1GOCIiIyomKUY/RjxGPUY4Rj4iIiVGPSlGPywmOSRGPUY3Rj5GPS9GNzssJjkmRj1GPUY9RkVGJUYlRiVGPQ==QyQ+SSpTSXRMb3ZlckhHNiItSSRzdW1HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2JCwoLUkoRkZUbXVsTEdGJTYkSSJpR0YlSSJ6R0YlIiIkLUYuNiQsJkYwIiIiISIiRjZGMSIiIyIiJUY2L0YwOywmSSJIR0YlRjZGNkY2SSJrR0YlRjY=QyQ+SSpTSXRDb3ZlckhHNiIsJkktU0l0U3Bhbk92ZXJIR0YlIiIiKiZJMVNJdE92ZXJoZWFkT3ZlckhHRiVGKEkiVUdGJUYoRihGKA==JSFHCONCLUSION
Qyg+SShTSXRTcGFuRzYiLCZJL1NJdFNwYW5TY3JhdGNoR0YlIiIiSS1TSXRTcGFuT3ZlckhHRiVGKEYoLUkpc2ltcGxpZnlHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2I0kiJUdGJUYoLUkmbGF0ZXhHRixGL0YoQyg+SSxTSXRPdmVyaGVhZEc2IiwmSTNTSXRPdmVyaGVhZFNjcmF0Y2hHRiUiIiJJMVNJdE92ZXJoZWFkT3ZlckhHRiVGKEYoLUkpc2ltcGxpZnlHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2I0kiJUdGJUYoLUkmbGF0ZXhHRixGL0YoQyQ+SSVTSXRORzYiLCZJLFNJdFNjcmF0Y2hOR0YlIiIiLUkqU0l0Tm92ZXJIR0YlNiVJImtHRiVJInpHRiVJIkhHRiVGKEYoQyQ+SSVTSXRMRzYiLCZJLFNJdFNjcmF0Y2hMR0YlIiIiSSpTSXRMb3ZlckhHRiVGKEYoQyQ+SSVTSXRDRzYiLCZJLFNJdFNjcmF0Y2hDR0YlIiIiSSpTSXRDb3ZlckhHRiVGKEYoQyY+SStTSXRTcGVlZFVwRzYiKiYsJiomSSVTSXROR0YlIiIiSSJQR0YlISIiRipJJVNJdExHRiVGKkYqSSVTSXRDR0YlRipGKi1JKXNpbXBsaWZ5RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiNJIiVHRiVGKg==EvaluationPlain
Qyo+SS1FdmFQbGFpblNwYW5HNiJmKjYjSSJIR0YlRiVGJUYlTy1JJHN1bUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYkLCYpIiIjSSJpR0YlIiIkIiIiRjUvRjM7IiIhOSRGJUYlRiVGNT5JLkV2YVBsYWluU3BhbkhHRiUtRiRGJ0Y1LUkpc2ltcGxpZnlHRiw2I0kiJUdGJUY1LUkmbGF0ZXhHRixGP0Y1EvaPlainOverhead:= 5*H*U;latex(%);
QyQ+SSpFdmFQbGFpbk5HNiJmKjYlSSJrR0YlSSJ6R0YlSSJIR0YlRiVGJUYlTy1JJHN1bUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYkKigpIiIjLCY5JCIiIkkiaUdGJSEiIkY3LCYpRjRGOEY3RjdGN0Y3OSVGOS9GODtGNzkmRiVGJUYlRjc=QyQ+SSpFdmFQbGFpbkxHNiJJIkhHRiUiIiI=QyQ+SSpFdmFQbGFpbkNHNiIsJi1JLUV2YVBsYWluU3BhbkdGJTYjSSJIR0YlIiIiKiZJMUV2YVBsYWluT3ZlcmhlYWRHRiVGK0kiVUdGJUYrRitGKw==JSFHFFT
Qyg+SStFdmFGRlRzcGFuRzYiLUkkc3VtRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiQsJi1JK0ZGVG11bFNwYW5HRiU2I0kiaUdGJSIiIyIiJSIiIi9GMDssJkkiSEdGJUYzRjNGM0kia0dGJUYzLUkpc2ltcGxpZnlHRig2I0kiJUdGJUYzLUkmbGF0ZXhHRihGO0YzQyg+SS9FdmFGRlRPdmVyaGVhZEc2IiomSSJVR0YlIiIiLUkkc3VtRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiQsJi1JL0ZGVG11bE92ZXJoZWFkR0YlNiNJImlHRiUiIiMiIipGKC9GMzssJkkiSEdGJUYoRihGKEkia0dGJUYoRigtSSlzaW1wbGlmeUdGKzYjSSIlR0YlRigtSSZsYXRleEdGK0Y9Rig=QyQ+SShFdmFGRlRuRzYiZio2JUkia0dGJUkiekdGJUkiSEdGJUYlRiVGJU8tSSRzdW1HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2JComLCYtSShGRlRtdWxOR0YlNiRJImlHRiU5JSIiIyomKUY5RjciIiJGOCEiIiIiJUY8KUY5LCY5JEY8RjdGPUY8L0Y3OywmOSZGPEY8RjxGQUYlRiVGJUY8QyQ+SShFdmFGRlRsRzYiLUkkc3VtRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiQsJi1JKEZGVG11bExHRiU2JEkiaUdGJUkiekdGJSIiIyIiJiIiIi9GMDssJkkiSEdGJUY0RjRGNEkia0dGJUY0QyQ+SShFdmFGRlRjRzYiLCZJK0V2YUZGVHNwYW5HRiUiIiIqJkkvRXZhRkZUT3ZlcmhlYWRHRiVGKEkiVUdGJUYoRihGKA==JSFHTotal
Qyg+SShFdmFTcGFuRzYiLCYtSS1FdmFQbGFpblNwYW5HRiU2I0kiSEdGJSIiIkkrRXZhRkZUc3BhbkdGJUYrRistSSlzaW1wbGlmeUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYjSSIlR0YlRistSSZsYXRleEdGL0YyRis=Qyg+SSxFdmFPdmVyaGVhZEc2IiwmSTFFdmFQbGFpbk92ZXJoZWFkR0YlIiIiSS9FdmFGRlRPdmVyaGVhZEdGJUYoRigtSSlzaW1wbGlmeUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYjSSIlR0YlRigtSSZsYXRleEdGLEYvRig=QyQ+SSVFdmFORzYiLCYtSSpFdmFQbGFpbk5HRiU2JUkia0dGJUkiekdGJUkiSEdGJSIiIi1JKEV2YUZGVG5HRiVGKUYtRi0=QyQ+SSpFdmFUb3RhbExHNiIsJkkqRXZhUGxhaW5MR0YlIiIiSShFdmFGRlRsR0YlRihGKA==QyQ+SSVFdmFDRzYiLCZJKkV2YVBsYWluQ0dGJSIiIkkoRXZhRkZUY0dGJUYoRig=QyQ+SStFdmFTcGVlZFVwRzYiKiYsJiomSSVFdmFOR0YlIiIiSSJQR0YlISIiRipJKkV2YVRvdGFsTEdGJUYqRipJJUV2YUNHRiVGKkYqJSFHInterpolation tree
Plain
Qyg+SS1JUHRQbGFpblNwYW5HNiItSSRzdW1HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2JCwmLUktUGxhaW5NdWxTcGFuR0YlNiNJImlHRiUiIiJGMUYxL0YwO0YxSSJIR0YlRjEtSSlzaW1wbGlmeUdGKDYjSSIlR0YlRjEtSSZsYXRleEdGKEY3RjE=Qyg+STFJUHRQbGFpbk92ZXJoZWFkRzYiLUkkc3VtRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiQsJi1JMVBsYWluTXVsT3ZlcmhlYWRHRiU2I0kiaUdGJSIiIiIiJEYxL0YwO0YxSSJIR0YlRjEtSSlzaW1wbGlmeUdGKDYjSSIlR0YlRjEtSSZsYXRleEdGKEY4RjE=QyQ+SSpJUHRQbGFpbk5HNiJmKjYlSSJrR0YlSSJ6R0YlSSJIR0YlRiVGJUYlTy1JJHN1bUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYkLCYtSSpQbGFpbk11bE5HRiU2JUkiaUdGJTkkOSUiIiIqJikiIiNGNkY5RjghIiJGOS9GNjtGOTkmRiVGJUYlRjk=QyQ+SSpJUHRQbGFpbkxHNiItSSRzdW1HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2JCwmLUkqcGxhaW5NdWxMR0YlNiNJImlHRiUiIiJGMUYxL0YwO0YxSSJIR0YlRjE=QyQ+SSpJUHRQbGFpbkNHNiIsJkktSVB0UGxhaW5TcGFuR0YlIiIiKiZJMUlQdFBsYWluT3ZlcmhlYWRHRiVGKEkiVUdGJUYoRihGKA==JSFHFFT
Qyg+SStJUHRGRlRzcGFuRzYiLUkkc3VtRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiQsJi1JK0ZGVG11bFNwYW5HRiU2I0kiaUdGJSIiIiIiJEYxL0YwOywmSSJIR0YlRjFGMUYxSSJrR0YlRjEtSSlzaW1wbGlmeUdGKDYjSSIlR0YlRjEtSSZsYXRleEdGKEY6RjE=Qyg+SS9JUHRGRlRPdmVyaGVhZEc2Ii1JJHN1bUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYkLCYtSS9GRlRtdWxPdmVyaGVhZEdGJTYjSSJpR0YlIiIiIiIlRjEvRjA7LCZJIkhHRiVGMUYxRjFJImtHRiVGMS1JKXNpbXBsaWZ5R0YoNiNJIiVHRiVGMS1JJmxhdGV4R0YoRjpGMQ==QyQ+SShJUHRGRlRuRzYiZio2JUkia0dGJUkiekdGJUkiSEdGJUYlRiVGJU8tSSRzdW1HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2JComLCgtSShGRlRtdWxOR0YlNiRJImlHRiU5JSIiIiomKSIiIywmRjdGOSEiIkY5RjlGOEY+RjkqJilGPEY3RjlGOEY+RjlGOSlGPCwmOSRGOUY3Rj5GOS9GNzssJjkmRjlGOUY5RkNGJUYlRiVGOQ==QyQ+SShJUHRGRlRsRzYiLUkkc3VtRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiQsJi1JKEZGVG11bExHRiU2JEkiaUdGJUkiekdGJSIiIiIiI0YyL0YwOywmSSJIR0YlRjJGMkYySSJrR0YlRjI=QyQ+SShJUHRGRlRjRzYiLCZJK0lQdEZGVHNwYW5HRiUiIiIqJkkvSVB0RkZUT3ZlcmhlYWRHRiVGKEkiVUdGJUYoRihGKA==JSFHTotal
Qyg+SShJUHRTcGFuRzYiLCZJLUlQdFBsYWluU3BhbkdGJSIiIkkrSVB0RkZUc3BhbkdGJUYoRigtSSlzaW1wbGlmeUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYjSSIlR0YlRigtSSZsYXRleEdGLEYvRig=Qyg+SSxJUHRPdmVyaGVhZEc2IiwmSTFJUHRQbGFpbk92ZXJoZWFkR0YlIiIiSS9JUHRGRlRPdmVyaGVhZEdGJUYoRigtSSlzaW1wbGlmeUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYjSSIlR0YlRigtSSZsYXRleEdGLEYvRig=QyQ+SSVJUHRORzYiLCYtSSpJUHRQbGFpbk5HRiU2JUkia0dGJUkiekdGJUkiSEdGJSIiIi1JKElQdEZGVG5HRiVGKUYtRi0=QyQ+SSVJUHRMRzYiLCZJKklQdFBsYWluTEdGJSIiIkkoSVB0RkZUbEdGJUYoRig=QyQ+SSVJUHRjRzYiLCZJKklQdFBsYWluQ0dGJSIiIkkoSVB0RkZUY0dGJUYoRig=QyQ+SStJUHRTcGVlZFVwRzYiKiYsJiomSSVJUHROR0YlIiIiSSJQR0YlISIiRipJJUlQdExHRiVGKkYqSSVJUHRjR0YlRipGKg==JSFHQyQ+STBjb21wdXRlT3B0aW11bUhHNiJmKjYjSSJGR0YlNihJJE1JTkdGJUkiS0dGJUkibUdGJUkiaEdGJUkiZUdGJUkkaW5kR0YlRiVGJUMkPjgkIjYrKysrKysrKysrIj8oOCUiIiUiIiIiI0JJJXRydWVHJSpwcm90ZWN0ZWRHQyU+OCZGMj8oOCciIiFGN0Y1RjlDJD44KC1JJWV2YWxHRjo2JDkkNyYvSSJIR0YlRj8vSSJrR0YlRjUvSSJuR0YlKSIiI0Y1L0kiVUdGJUY3QCQyRkNGPUMkPkY9RkM+OClGPy1JJnByaW50R0Y6NiNGWEYlRiVGJSEiIg==QyQtSTBjb21wdXRlT3B0aW11bUhHNiI2I0ksU1B0T3ZlcmhlYWRHRiUiIiI=QyQtSTBjb21wdXRlT3B0aW11bUhHNiI2I0koU1B0U3BhbkdGJSIiIg==LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=