We suggested a decomposition algorithm of multidimensional polynomials evaluation performing according to the generalized Horner scheme. The generalized Horner scheme is described in detail; we also demonstrate that in the vast majority of real situations this scheme can be decomposed easily and naturally. As a use-example, we study the problem of evaluation of classic quasipolynomials.
pn(x) =
N N ∑ : : : ∑ i1=0 in=0 ai1:::in xi11 : : : xinn ; (1:1) where x = (x1; : : : ; xn) is an n-dimensional real data vector, ai1:::in are constant real coefficients of the polynomial and N is some natural number representing the maximal degree attained by at least one of the variables x1; : : : ; xn.
The problem of the polynomial evaluation (1.1) is rather popular. It is explained by the fact that different
mathematical objects such as the right sides of ordinary differential equations, constraints of nonlinear
programming problems, initial and boundary conditions of mathematical physics problems and many others are described
by these polynomials
It is well-known that polynomial evaluation of the form (1.1) of one variable is easy to perform in terms of
the Horner scheme allowing in many cases to reduce the number of machine operations resulting in reduction
of computation error
Here we should point out an important work [Dowling, 1990], presenting a multidimensional performance of the generalized Horner scheme, this performance applying parallel computations. Besides, the work [Dowling, 1990] provides an important evaluation of parallel computations steps as a function of n and N parameters and of the number of the processors applied.
The distinctive feature of the indicated algorithms is that the multidimensional analog of Horner scheme,
in contrast to the scalar one, not only reduces the amount of computation and reduces the error, but also
represents additional opportunities. A namely, a possibility of computation process decomposition accompanies
to the advantages of the one-dimensional scheme
The main goal of this paper is the construction and analysis of complete generalized Horner scheme for
multidimensional polynomials evaluation (1.1). Special focus will be on the description of the scheme and the algorithm
related to the scheme, especially oriented on decomposing of computation process
As it will be demonstrated, this variant of the scheme is focused on being performed in a distributed computer
environment. Additionally, we shall note that the stated algorithm was developed to meet the needs of the
optimization theory in connection with the issue of constructing approximate solutions for the problem of control
of nonlinear systems via quadratic criteria within long time intervals
The Horner scheme for one-dimensional polynomials is well known and is under study in many papers
Let’s consider a real one-dimensional polynomials p1(x) =
N ∑ aixi; i=0 where ai are some real numbers and x is a real variable. According to [5], the Horner scheme for polynomial (2.1) appears as follows: (2:1) (2:2) (2:3) (2:4) of x and y real variables. For the polynomial evaluation (2.3) let’s state y variable and assume
N N p2(x; y) = ∑ ∑ aij xiyj
Remark 1. Let’s clarify the meaning of the Horner scheme use. For this purpose let’s consider a complete polynomial, i.e. a polynomial in which all ai coefficients are different from zero.
Let’s assume that for the polynomial evaluation by (2.1) the innermost brackets are expanded first. Further
it is easily seen that N multiplications and N additions are required by the Horner scheme for (2.1) polynomial
evaluation. Therewith, the number of machine operations for the evaluation by (2.1) equal to N (N + 1)=2, if only
each x degree is obtained by sequential multiplication by x, i.e. xk = xk 1x
This means that the greater N value the closer to complete is the polynomial (2.1) the Horner scheme use (2.2) becomes more effective, which allows in similar cases to reduce a number of machine operations essentially and thus to reduce computation error.
Let’s illustrate the generalization of the scheme (2.2) meant for multidimensional polynomials evaluation of the form (1.1) on the following example.
Example 1. Let’s consider a classic real polynomial Then if one consider with y defined as polynomial of one x real variable, then, acting by analogy to (2.1) and (2.2), we hold: p2(x; y) = ((: : : (( N (y)x +
N 1(y))x +
N 2(y))x + : : : : : : + 2(y))x + 1(y))x + 0(y):
It is easily seen that with any y defined the scheme (2.5) is a primitive generalization of the one-dimensional Horner scheme to polynomial (2.3). To obtaining a finer generalization let’s note that each y ! i(y) function is one-dimensional polynomial. Thus, applying the one-dimensional Horner scheme to polynomial (2.4), we assume i(y) = ((: : : ((aiN y + ai;N 1)y + ai;N 2)y + : : : + ai2)y + ai1)y + ai0;
i = 0; : : : ; N:
Thus (2.5) and (2.6) equalities provide generalized Horner scheme (1.1) for polynomial evaluation (2.3). It is apparent from these equalities show that in the general case Horner scheme use allows to considerably reduce computation process in comparison to brute force computation by (2.3).
Going now over to construction of generalized Horner scheme for polynomial (1.1) in the general case let’s state x2; : : : ; xn variables and assume
Let’s now note that each (x2; : : : ; xn) ! i1 (x2; : : : ; xn) function defined by equality (2.7) is a multidimensional polynomial of x2; : : : ; xn variables. For these polynomials evaluation let’s state x3; : : : ; xn variables and assume
Then acting by analogy to (2.1) and (2.2) we hold: (2:5) (2:6) (2:7) (2:8) (2:9) i1 (x2; : : : ; xn) =
ai1i2:::in xi22 : : : xinn ; i1 = 0; : : : ; N: pn(x) = ((: : : (( N (x2; : : : ; xn)x1 + N 1(x2; : : : ; xn))x1+ + N 2(x2; : : : ; xn))x1 + : : : +
2(x2; : : : ; xn))x1+ + 1(x2; : : : ; xn))x1 + 0(x2; : : : ; xn): i1i2 (x2; : : : ; xn) =
ai1i2i3:::in xi33 : : : xinn ; i1; i2 = 0; : : : ; N: i1 (x2; : : : ; xn) = ((: : : (( i1N (x3; : : : ; xn)x2+ + i1;N 1(x3; : : : ; xn))x2 + i1;N 2(x3; : : : ; xn))x2 + : : : : : : + i12(x3; : : : ; xn))x2 + i11(x3; : : : ; xn))x2 + i10(x3; : : : ; xn); Acting in a similar way for k = 1; : : : ; n
N N = ∑ : : : ∑ ik+1=0 in=0 ai1:::ikik+1:::in xikk++11 : : : xinn ; i1; : : : ; ik = 0; : : : ; N: It follows that for all k = 2; : : : ; n
i1:::ik 1 (xk; : : : ; xn) = (: : : (( i1:::ik 1N (xk+1; : : : ; xn)xk+ + i1:::ik 1;N 1(xk+1; : : : ; xn))xk + i1:::ik 1;N 2(xk+1; : : : ; xn))xk + : : :)xk+
+ i1:::ik 10(x3; : : : ; xn); i1; : : : ; ik 1 = 0; : : : ; N: recurrence relation is correct.
Provided that = ((: : : ((ai1:::in 1N xn + ai1:::in 1;N 1)xn + ai1:::in 1;N 2)xn + : : : : : : + ai1:::in 12)xn + ai1:::in 11)xn + i1:::in 10;
i1; : : : ; in 1 = 0; : : : ; N:
The relations (2.8)–(2.10) define the generalized Horner scheme for polynomial evaluation (1.1). In many cases this scheme allows to reduce computation. As will be seen in section 3, in the general case scheme (2.9) and (2.10) admits decomposing, and the validity of the following statement is established by simple computation.
The number of operations for polynomial evaluation (1.1) according to the generalized Horner scheme is equivalent to the number of operations for evaluation of not more than
N = n 1 ∑(N + 1)i i=0 one-dimensional polynomials of the form (2.1) by the Horner scheme. 3
For the purpose of implementation of the above-described generalized Horner scheme we will use an n-steps algorithm focused on the computation process decomposition.
Step 1. Here we evaluate the functions xn ! i1:::in 1 (xn) by (2.10). Evidently, each of these functions can be constructed independently. That’s why the process of construction can be decomposed naturally into parallel evaluations of all these functions.
Steps 2; : : : ; n 1: At these steps for k = n 1; : : : ; 2 by (2.9) we evaluate the functions (xk; : : : ; xn) ! i1:::ik 1 (xk; : : : ; xn): Like at step 1, each of these functions can be built independently, i.e. here the process of construction can be, in the general case, also decomposed naturally into parallel evaluations of all these functions.
Step n: This step is the simplest one: at this step we evaluate the functions x ! pn(x) by (2.8).
Remark 2. Evidently, the higher the values of n and N are, the greater effect is produced by the computation process decomposition on parallel nodes. In other words, the generalized Horner scheme efficiency for the nearly complete polynomials can be additionally boosted by the natural decomposition of the computation process.
Remark 3. In the course of operation the necessity of polynomial evaluation (1.1) at various x vector values can occur. Obviously, every such computation doesn’t depend on others and these computations can be performed in parallel on independent nodes. As it will be shown below in section 4, in some cases the latter ensures essential simplification of the classic problem of finding the zeros of quasipolynomials (see ex. 2). 4
Evaluation of the Simplest Quasipolynomial As one more example of the use of the generalized Horner scheme let’s consider the problem of classical quasipolynomials evaluation.
Example 2. Let’s consider
p˜2(t) = p2(t; exp t)
function of t real variable where p2 is the polynomial of x = t and y = exp t variables described in the example 1.
The study of zeros of this function (in general terms, of a quasipolynomial) is essential to the Lyapunov theory
of stability of motion
Considering that p2 is polynomial of x = t and y = exp t variables then acting by analogy to (2.5) and (2.6), we can write
p˜2(t) = (: : : (( ˜N (t) exp t + ˜N 1(t)) exp t + ˜N 2(t)) exp t + : : :) exp t + ˜0(t); where
˜i(t) = (: : : ((aiN t + ai;N 1)t + ai;N 2)t + : : :)t + ai0; i = 0; : : : ; N; which defines the generalized Horner scheme for the quasipolynomial evaluation.
Thus according to (4.2) and (4.3) relations it is easy to notice that the generalized Horner scheme described in the example 1 can be in some cases used efficiently use for classical quasipolynomial evaluation. (2:10) (2:11) (4:1) (4:2) (4:3)
In order to verify this, let’s suppose that the roots of the quasipolynomial (4.3) are localized within a certain interval [a; b]. Let’s assume some natural number k and state and " = (b
a) k ti = i"; i = 0; : : : ; k: (4:4) It seems clear that evaluation of the quasipolynomial (4.1) at any point of the set (4.4) can be performed independently of the others, i.e. in parallel, for instance, on independent nodes. Thus, providing there are enough independent nodes, finding the zeros of the quasipolynomial (4.1) requires no great timing budgets. Therewith, as it was stated in Ex. 1, performing the evaluation by means of the generalized Horner scheme allows, in many cases, to reduce the number of machine operations. The latter reduces the error and computation time. 5
The distinctive feature of the generalized Horner scheme described herein is the obvious possibility of computation process decomposition.
According to section 2, the computation process decomposition is always possible in case of availability the additive component distinctive in the polynomial (1.1). This condition is simple and natural because its failure means that in practice (1.1) represents a direct analogy of a one-dimensional polynomial.
In other words in almost all real situations the algorithm representing the generalized Horner scheme admits decomposition. Moreover, the level of the algorithm decomposition is easily rated.
Actually, let’s consider for simplicity only the first stage of the algorithm. At step 1 of this stage the symbolic construction of xn ! i1:::in 1 (xn) function is realized provided that each of this functions can be constructed independently. A number of these functions as it is easy to see can get to (N + 1)(n 1). It follows that the computation process at this step can in general terms decompose into (N + 1)(n 1) of parallel computation processes.
In a similar way, at step 2 of the stage 1 the computation process can be decomposed into (N + 1)(n 2) of parallel computation processes and so on.
Thus, according to remark 1, if the total number of one-dimensional polynomials equals to N (see 2.11), then the total number of machine operations of addition and multiplication is 2N N . Proceeding from the above, if there are (N + 1)(n 1) processors, then the total number of parallel addition and parallel multiplication operations, featured during the decomposition of the parallel computation processes, will amount to 2N n, where n << N in the general case.
It should be noted that the number (N + 1)(n 1) can be rather large. That’s why the implementation of the above-described algorithm is focused, in the general case, on a distributed computer environment featuring a rather large number of processors.
Acknowledgements This work was supported by Russian Scientific Foundation, Project 16-11-10352.
Kom[Afanasiev & Tarasov, 2006] Afanasiev, A.P., Tarasov, A.S. (2006). Quasi-analytic system solution of differential equations with polynomial right side. Coll. of works of ISA RAN Problems of estimation in a distributed environment: distributed systems, communications systems, symbolic models and optimization, (25), 165–183. [Afanasiev & Dzyuba, 2015a] Afanas’ev, A.P., Dzyuba, S.M. (2015). Method for constructing approximate analytic solutions of differential equations with a polynomial right-hand side. Comp. Math. and Math. Phys., 55(10), 1665–1673.