=Paper=
{{Paper
|id=Vol-1987/paper2
|storemode=property
|title=Decomposition Algorithm of Generalized Horner Scheme for Multidimensional Polynomial Evaluation
|pdfUrl=https://ceur-ws.org/Vol-1987/paper2.pdf
|volume=Vol-1987
|authors=Alexander P. Afanasiev,Sergei M. Dzyuba,Irina I. Emelyanova,Elena V. Putilina,Alexander P. Afanasiev,Vladimir E. Krivonozhko,Andrey V. Lychev,Oleg V. Sukhoroslov,Alexander A. Ageev,Alexander V. Kel'manov,Artem V. Pyatkin,Sergey A. Khamidullin,Vladimir V. Shenmaier,Kamil R. Aida-zade,Yegana R. Ashrafova,Kamil R. Aida-zade,Vugar A. Hashimov,Alla F. Albu,Vladimir I. Zubov,Yedilkhan Amirgaliyev,Maksat Kalimoldayev,Rassul Yunussov,Boris I. Ananyev,Anatoly S. Antipin,Elena V. Khoroshilova,Sergey N. Astrakov,Yurii Averboukh,Levon A. Beklaryan,Armen L. Beklaryan,Milena Bieniek,Vadim Bulavintsev,Pavel Petrov,Mikhail Posypkin,Oleg Zaikin,Alexander S. Buldaev,Igor A. Bykadorov,Igor A. Bykadorov,Alexander G. Chentsov,Alexey M. Grigoryev,Alexey A. Chentsov,Ilya Chernykh,Artem Pyatkin,Marina V. Chervyakova,Robert V. Namm,Ellina M. Vikhtenko,Aladin Crnkić,Vladimir Jaćimović,Vasily V. Dikusar,Nicholas N. Olenev,Askhat I. Diveev,Elizaveta Yu. Shmalko,Erkan Dogan,Aybike O. Ciftcioglu,Ferhat Erdal,Michael Dreyfuss,Irit Nowik,Olga V. Druzhinina,Vladimir N. Shchennikov,Elena V. Shchennikova,Adil I. Erzin,Roman V. Plotnikov,Damir N. Gainanov,Dmitriy A. Berenov,Edward Kh. Gimadi,Edward Kh. Gimadi,Anna Kurochkina,Oxana Tsidulko,Dmitry Golembiovsky,Dmitry Denisov,Evgeny Antonov,Evgeny G. Golshteyn,Ustav Kh. Malkov,Nikolay A. Sokolov,Victor Gorelik,Tatiana Zolotova,Natalia S. Grigoreva,Tatiana V. Gruzdeva,Alexander S. Strekalovsky,Viktor S. Izhutkin,Anton A. Sharapov,Viktor S. Izhutkin,Alexander Zonov,David Kalaj,Arsen Zlatičanin,Maksat Kalimoldayev,Maksat Akhmetzhanov,Assel Abdildayeva,Fariza Galiyeva,Igor Kaporin,Alexander Kel'manov,Alexander Kel'manov,Vladimir Khandeev,Alexander Kel'manov,Anna Motkova,Alexander Kel'manov,Artem Pyatkin,Michael Khachay,Katherine Neznakhina,Michael Khachay,Vasiliy Pankratov,Daniel Khachay,Dmitry V. Khlopin,Vladimir E. Krivonozhko,Andrey V. Lychev,Eugene A. Kalashnikov,Konstantin N. Kudryavtsev,Irina S. Stabulit,Viktor I. Ukhobotov,Konstantin N. Kudryavtsev,Vladislav I. Zhukovskiy,Alexander Lazarev,German Tarasov,Dmitry Arkhipov,Alexander Lazarev,Nail Khusnullin,Elena Musatova,Denis Yadrentsev,Konstantin Ponomarev,Sergey Lupin,Aye Min Thike,Hein Tun,Valeriy M. Marakulin,Olga N. Masina,Olga V. Druzhinina,Alexey A. Petrov,Vladimir D. Mazurov,Alexander I. Smirnov,Nevena Mijajlović,Milojica Jaćimović,Igor E. Mikhailov,Ivan A. Suvorov,Leonid I. Minchenko,Daniil E. Berezhnov,Nataliia K. Obrosova,Alexander A. Shananin,Nicholas N. Olenev,Andrei V. Orlov,Nicolás Majorel Padilla,Pedro Araujo,Adrián Will,Sebastián Rodríguez,Alexander V. Pesterev,Lev F. Petrov,Nikolay Pogodaev,Boris T. Polyak,Andrey A. Tremba,Yuri S. Popkov,Larisa Rybak,Elena Gaponenko,Viktoria Kuzmina,Olga N. Samsonyuk,Natalya Sedova,Vadim I. Shmyrev,Ruslan Yu. Simanchev,Inna V. Urazova,Alexander K. Skiba,Stepan P. Sorokin,Maxim V. Staritsyn,Alexander S. Strekalovsky,Anna Tatarczak,Nikolay P. Tikhomirov,Dmitry V. Aron,Alexey A. Tret'yakov,Sergey Trofimov,Aleksey Ivanov,Yury Fettser,Tatiana S. Zarodnyuk,Alexander Yu. Gornov,Anton S. Anikin,Evgeniya A. Finkelstein,Elena S. Zasukhina,Sergey V. Zasukhin,Vitaly Zhadan,Anna V. Zykina,Olga N. Kaneva
}}
==Decomposition Algorithm of Generalized Horner Scheme for Multidimensional Polynomial Evaluation==
https://ceur-ws.org/Vol-1987/paper2.pdf
Decomposition Algorithm of Generalized Horner Scheme
for Multidimensional Polynomial Evaluation
Alexander P. Afanasiev1,2,3,4 Sergei M. Dzyuba5 Irina I. Emelyanova5
Elena V. Putilina1
1
Institute for Information Transmission Problems,
Russian Academy of Sciences, Nakhimovsky Prospekt 36-1, Moscow 117218, Russia
2
National Research University Higher School of Economics, Myasnitskaya str., 20, Moscow 101000, Russia
3
National University of Science and Technology MISiS, Leninskiy Prospekt 4, Moscow 119049, Russia
4
Lomonosov Moscow State University, GSP-1, Vorobievy Gory, Moscow 119991, Russia
5
Tver State Technical University, Af. Nikitin emb. 22, Tver 170026, Russia
E-mail: apa@iitp.ru, sdzyuba@mail.ru, emelyanova-123@yandex.ru, elena@iitp.ru
Abstract
We suggested a decomposition algorithm of multidimensional poly-
nomials 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.
1 Introduction
Let’s consider a multidimensional polynomial
∑
N ∑
N
pn (x) = ... ai1 ...in xi11 . . . xinn , (1.1)
i1 =0 in =0
where x = (x1 , . . . , xn ) is an n-dimensional real data vector, ai1 ...in are constant real coefficients of the polyno-
mial 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 program-
ming problems, initial and boundary conditions of mathematical physics problems and many others are described
by these polynomials (see [Afanasiev, 2005]–[Afanasiev & Dzyuba, 2015b]).
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 (see [Afanasiev, 2005], [McCracken & Dorn, 1965]–[Cormen et al., 2009]). As for multidi-
mensional polynomials several computational algorithms representing different generalizations of Horner scheme
to a multidimensional case are known nowadays (see [Afanasiev, 2005]).
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of
the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org
7
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 (see [Afanasiev, 2005]). However, all known results either are
attributed to special cases of polynomial or have no detailed extended characterization.
The main goal of this paper is the construction and analysis of complete generalized Horner scheme for multidi-
mensional 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 (see [Afanasiev, 2005]).
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 (see [Afanasiev et al., 2016]).
2 Generalized Horner Scheme
The Horner scheme for one-dimensional polynomials is well known and is under study in many papers (see
[Afanasiev, 2005]). The point is as follows.
Let’s consider a real one-dimensional polynomials
∑
N
p1 (x) = ai xi , (2.1)
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:
p1 (x) = ((. . . ((aN x + aN −1 )x + aN −2 )x + . . . + a2 )x + a1 )x + a0 . (2.2)
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−1 x (see [McCracken & Dorn, 1965]).
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
∑
N ∑
N
p2 (x, y) = aij xi y j (2.3)
i=0 j=0
of x and y real variables. For the polynomial evaluation (2.3) let’s state y variable and assume
∑
N
αi (y) = aij y j , i = 0, . . . , N. (2.4)
j=0
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 + . . .
8
. . . + α2 (y))x + α1 (y))x + α0 (y). (2.5)
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. (2.6)
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
∑
N ∑
N
αi1 (x2 , . . . , xn ) = ... ai1 i2 ...in xi22 . . . xinn , i1 = 0, . . . , N. (2.7)
i2 =0 in =0
Then acting by analogy to (2.1) and (2.2) we hold:
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 ). (2.8)
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
∑
N ∑
N
αi1 i2 (x2 , . . . , xn ) = ... ai1 i2 i3 ...in xi33 . . . xinn , i1 , i2 = 0, . . . , N.
i3 =0 in =0
Then we hold
αi1 (x2 , . . . , xn ) = ((. . . ((αi1 N (x3 , . . . , xn )x2 +
+αi1 ,N −1 (x3 , . . . , xn ))x2 + αi1 ,N −2 (x3 , . . . , xn ))x2 + . . .
. . . + αi1 2 (x3 , . . . , xn ))x2 + αi1 1 (x3 , . . . , xn ))x2 + αi1 0 (x3 , . . . , xn ),
i1 = 0, . . . , N.
Acting in a similar way for k = 1, . . . , n − 1 arbitrary value, let’s assume
αi1 ...ik (xk+1 , . . . , xn ) =
∑
N ∑
N
i
= ... k+1
ai1 ...ik ik+1 ...in xk+1 . . . xinn , i1 , . . . , ik = 0, . . . , N.
ik+1 =0 in =0
It follows that for all k = 2, . . . , n − 1 values
αi1 ...ik−1 (xk , . . . , xn ) = (. . . ((αi1 ...ik−1 N (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−1 0 (x3 , . . . , xn ), i1 , . . . , ik−1 = 0, . . . , N. (2.9)
recurrence relation is correct.
Provided that
∑
N
αi1 ...in−1 (xn ) = ai1 ...in xinn =
in =0
9
= ((. . . ((ai1 ...in−1 N xn + ai1 ...in−1 ,N −1 )xn + ai1 ...in−1 ,N −2 )xn + . . .
. . . + ai1 ...in−1 2 )xn + ai1 ...in−1 1 )xn + αi1 ...in−1 0 ,
i1 , . . . , in−1 = 0, . . . , N. (2.10)
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−1
N = (N + 1)i (2.11)
i=0
one-dimensional polynomials of the form (2.1) by the Horner scheme.
3 Algorithm
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 quasipoly-
nomials evaluation.
Example 2. Let’s consider
p̃2 (t) = p2 (t, exp t) (4.1)
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 (see [Pontryagin, 1955]). Let’s here turn to more simple problem of its evaluation.
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), (4.2)
where
α̃i (t) = (. . . ((aiN t + ai,N −1 )t + ai,N −2 )t + . . .)t + ai0 , i = 0, . . . , N, (4.3)
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.
10
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
(b − a)
ε=
k
and
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 Discussion
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.
References
[Afanasiev, 2005] Afanasiev, A.P. (2005). Extension of trajectory toward optimal control. Moscow: Kom-
Kniga/URSS.
[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 an-
alytic solutions of differential equations with a polynomial right-hand side. Comp. Math. and Math.
Phys., 55(10), 1665–1673.
11
[Afanasiev & Dzyuba, 2015b] Afanas’ev, A.P., Dzyuba, S.M. (2015). Construction of minimal sets of differential
equations with a polynomial right hand-side. Diff. Eqns, 51(11), 1403–1412.
[McCracken & Dorn, 1965] McCracken, D., Dorn, W. (1965). Numerical methods and FORTRAN programming.
New York: John Willey and Sons.
[Levitin, 2006] Levitin, A.V. (2006). Algorithms. Introduction into development and analysis. Moscow: Williams.
[Cormen et al., 2009] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C. (2009). Intorduction to the algo-
rithms. New York: MIT Press and McGraw-Hill.
[Dowling, 1990] Dowling M. L. (1990). A fast parallel Horner algorithm. SIAM Journal on Computing, 19(1),
133–142.
[Afanasiev et al., 2016] Afanasiev, A.P., Dzyuba, S.M., Emelyanova, I.I., Ramazanov, A.B. (2016). Optimal
control with feedback of some class of nonlinear systems via quadratic criteria. Appl. Comp. Math.,
19(1), 78–87.
[Pontryagin, 1955] Pontryagin, L.S. (1955). On the zeroes of some elementary transcendental functions. Amer.
Math. Soc. Transl. Ser., 2(1), 95–110.
12