My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree3Thanks
  • 1 Post By meditate
  • 2 Post By johng40
Reply
 
LinkBack Thread Tools Display Modes
December 12th, 2017, 06:26 PM   #1
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 383
Thanks: 207

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 non-elegant, 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?
SDK is offline  
 
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.
Thanks from SDK
meditate is offline  
December 13th, 2017, 10:45 AM   #3
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 383
Thanks: 207

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
Originally Posted by meditate View Post
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.
You are of course correct. However, this is what is meant by the brute force solution. In order to find the minimal multiplications, one must exhaust all possible partitions up to the total degree of $f$ and then just count. This most definitely works, but it is computationally infeasible as the number of partitions blows up very fast even in only 1 dimension.
SDK is offline  
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.
Thanks from Joppy and SDK
johng40 is offline  
December 14th, 2017, 06:00 PM   #5
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 383
Thanks: 207

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
Originally Posted by johng40 View Post
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.
What algorithm are you referring to? Whether or not it is useful depends how far from optimal it is. Obviously, I'm not using Horner's method here so the algorithm to beat is the greedy implementation I have now which is near optimal, and still not good enough in some cases.

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.
SDK is offline  
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 non-recursive 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 non-zero coefficient; an overestimate of the number of multiplications required for m non-zero 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
johng40 is offline  
December 16th, 2017, 11:05 AM   #7
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 383
Thanks: 207

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
Originally Posted by johng40 View Post
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 non-recursive 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 non-zero coefficient; an overestimate of the number of multiplications required for m non-zero coefficients is then $3m\lfloor \log_2(n)\rfloor$. For small n, this isn't going to help.
My mistake, I misread your initial post and thought you were referring to asymptotic complexity of order $\log n$ where $n$ was the total degree of some sparse polynomial.

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.
SDK is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2018 My Math Forum. All rights reserved.