
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
December 12th, 2017, 06:26 PM  #1 
Senior Member Joined: Sep 2016 From: USA Posts: 435 Thanks: 247 Math Focus: Dynamical systems, analytic function theory, numerics  Fast polynomial evaluation
Short version: Consider a polynomial, $f: \mathbb{R}^d \to \mathbb{R}$ and suppose you are (and I am) interested in evaluation of $f(x)$ which utilizes a minimal number of multiplications. Is there an algorithm for determining the optimal manner in which to construct each monomial product? Here optimal means the minimum number of multiplications. Example: If $d=1$ and $f = \sum_{i=0}^n a_ix^i$, and every $a_i \neq 0$, then Horner's algorithm can be proved to satisfy the problem. In general, if $f$ is "dense" (most coefficients nonzero), Horner is expected to be optiimal or nearly optimal. Now, suppose $f$ is "sparse" meaning most coefficients are zero. Now it isn't clear how to proceed. Example: Let $f(x) = x^5 + x^{16}$. One particularly bad idea is to do the following: \[x^5 = x*x*x*x*x \ (5 \text{ multiplications})\] \[x^{16}= x^5*x*x*x*x*x*x*x*x*x*x*x \ (11 \text{ multiplications}) \] A better idea would be the following which was generated by a (pseudo) greedy algorithm I implemented to try and solve this problem: \[x^2 = x*x \] \[x^3 = x^2*x \] \[x^5 = x^2*x^3 \] \[x^{10} = x^5*x^5 \] \[x^{15} = x^{10}*x^5 \] \[x^{16} = x^{15}*x \] which requires only 6 multiplications. However, if you look closely you notice this is still not optimal. Consider \[x^2 = x*x \] \[x^4 = x^2*x^2 \] \[x^5 = x^4*x \] \[x^8 = x^4*x^4 \] \[x^{16} = x^8*x^8 \] which requires only 5 multiplications. The key here being (what the algorithm missed) that even though $x^5$ must be constructed at some point, it is still not the optimal path by which to obtain the $x^{16}$ term. Now, the question is, is there a known optimal solution to this problem? I'll settle for any problem isomorphic to this (I'm sure this is a graph theory problem in disguise) even if its slow. Additional Info (for those interested): The need here is motivated by 3 reasons: 1. My polynomials are not defined on $\mathbb{R}$, but rather in a Banach algebra, $X$, where multiplication is much much more expensive than addition. 2. My polynomials are not functions of 1 variable, but typically more like 10 variables. This makes brute forcing an optimal solution unlikely since a "typical" polynomial has an absurd number of terms and brute force algorithm would amount to traversing every possible tree of this size. 3. My polynomials are extremely sparse. This not only makes a brute force algorithm (even if it were possible) extremely nonelegant, but gives significant hope that there is a clever algorithm which doesn't need to exhaust every possible configuration. So anyone have some clever ideas? 
December 13th, 2017, 10:31 AM  #2 
Newbie Joined: Nov 2017 From: US Posts: 5 Thanks: 4 
Thinking out loud, one approach is to see how to use partition of a number to arrive at optimal set of computations. For example, partition of 5 is 7 (https://www.wolframalpha.com/input/?i=partition+of+5). 5 (Size =1) 4+1 (Size =2) 3+2 (Size =2) 3+1+1 (Size =3) 2+2+1 (Size =3) 2+1+1+1 (Size =4) 1+1+1+1+1 (Size =5) From here, if we push along these lines in recursive manner ,we may get an option for optimal solution. 
December 13th, 2017, 10:45 AM  #3  
Senior Member Joined: Sep 2016 From: USA Posts: 435 Thanks: 247 Math Focus: Dynamical systems, analytic function theory, numerics  Quote:
 
December 13th, 2017, 12:11 PM  #4 
Member Joined: Jan 2016 From: Athens, OH Posts: 89 Thanks: 47 
I don't know if this helps, but a standard algorithm of order log(n) to evaluate $x^n$ will probably have many fewer multiplications than Horner's method applied to a (sparse) polynomial of degree n. This idea doesn't lead to an optimal solution, but it might be of practical use for your application.

December 14th, 2017, 06:00 PM  #5  
Senior Member Joined: Sep 2016 From: USA Posts: 435 Thanks: 247 Math Focus: Dynamical systems, analytic function theory, numerics  Quote:
I'm happy to obtain something which is still not optimal but improves on this. I'd appreciate some details if you have an idea.  
December 15th, 2017, 08:34 AM  #6 
Member Joined: Jan 2016 From: Athens, OH Posts: 89 Thanks: 47 
I was referring to the algorithm based on the binary representation of the positive integer n. The easiest implementation is recursive (c language), which has the same efficiency as a nonrecursive version. Code: double power(double x, int n) { double v; if (n == 1) { return (x); } v = power(x, n / 2); v *= v; if (n & 1) { // n is odd v *= x; } return (v); } It is obvious that the number of multiplications is at most $2\lfloor \log_2(n)\rfloor$. So I was thinking of polynomials of large degree n and just evaluate each term with a nonzero coefficient; an overestimate of the number of multiplications required for m nonzero coefficients is then $3m\lfloor \log_2(n)\rfloor$. For small n, this isn't going to help. Last edited by johng40; December 15th, 2017 at 09:28 AM. Reason: corrections 
December 16th, 2017, 11:05 AM  #7  
Senior Member Joined: Sep 2016 From: USA Posts: 435 Thanks: 247 Math Focus: Dynamical systems, analytic function theory, numerics  Quote:
The computation for a single term is of course not a problem and already a greedy algorithm has this as a lower bound. Unfortunately, this is still pretty bad since applying it to every term of a sparse polynomial with total degree of $k$ terms you have something on the order of $\log(k!)$ multiplications. In fact, this algorithm is in some sense what I need to do better than. Obviously, you can't do better for every polynomial since $f(x) = x^n$ would be among these competitors. In this case better here loosely means: If the polynomial admits an evaluation method which utilizes far fewer multiplications, then this method is utilized. After poking around a bit on google/arxiv, I'm beginning to think that no such algorithm is known but I still hope this isn't the case.  

Tags 
evaluation, fast, polynomial 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Evaluation of (sin x)^m (cos x)^n dx  Rejjy  Calculus  11  December 25th, 2016 08:56 PM 
Evaluation of surds  Hezekiah  Elementary Math  7  October 19th, 2016 07:40 AM 
int(1/n^n) evaluation  mathbalarka  Calculus  5  February 18th, 2013 12:53 AM 
Fast evaluation of integral function  LionAM  Calculus  2  August 18th, 2010 08:09 AM 
Evaluation Help  Soha  Algebra  2  February 3rd, 2007 06:33 AM 