Optimal number of required points for Evaluation - Interpolation
technique in complex basis
DIMITRIOS VARSAMIS, ANGELIKI KAMILALI
Department of Computer, Informatics and Telecommunications Engineering
International Hellenic University - Serres Campus
Terma Magnisias, Serres - 62124
GREECE
Abstract: - According to polynomial evaluation-interpolation technique, first of all, the set of required points, in
which interpolation will be executed, must be defined in evaluation part. Taking into account that working in
complex domain provides as with the advantage of conjugate properties, the number of evaluations at these points
could be reduced. This paper presents the appropriate form of required points, aiming to an optimal reduction of
their amount. The appropriate form of points for two variable polynomials depends on the degree of each variable.
As a repercussion the number of evaluations could be reduced even up to the half.
Key-Words: - complex domain, Evaluation - Interpolation technique, two-variable polynomials, polynomial
degrees
Received: July 9, 2021. Revised: April 12, 2022. Accepted: May 14, 2022. Published: June 8, 2022.
1 Introduction
Through years, many numerical computational
methods have been developed in the need of solving
systems and control theory problems, especially
those that consists of polynomials in one or even
in several variables, [1], [2]. Such problems are
calculation of the determinant of a polynomial matrix
[3], [4], computation of the generalised inverse [5],
[6], Moore-Penrose inverse [7] and Drazin inverse
of a polynomial matrix [8], as well as calculation of
the great common divisor among polynomials [9],
transfer function computation for multidimensional
systems [10] and solution of diophantine and matrix
equations [11].
Newton evaluation - interpolation technique is
one of these methods. In this method instead of
finding coefficients of the polynomial by solving a
system of equations (analytical solution), numer-
ical analysis is used. It consists of two parts. In
evaluation part, first of all, a set of distinct required
points is defined. The number of points depends on
the degree of polynomial. In interpolation part, the
unique polynomial that passes through these points
is defined [12].
According to [13] choosing the appropriate form
of points is less expensive both in memory and in
computational cost. Taking into account that working
in complex domain provides us with the opportunity
of using conjugate properties and according to [4],
we can reduce the number of evaluations in the first
part of this technique, in the means of choosing the
form of the required points by setting abscissa or
ordinate as complex number. Points that are defined
by conjugate numbers give conjugate results as well,
when they are evaluated. That is why the number
of the needed operations in evaluation part can be
reduced.
The purpose of this work is to indicate the most
appropriate form of points according to the degree of
each variable of the polynomial. That’s why we study
two variable polynomials. The upper bound of the de-
gree of each variable is already known, so we use rect-
angular basis. First of all an example is given to show
the significance of choosing the appropriate form of
points in complex domain. After that, the cases de-
pending on the degrees of each variable are presented.
In addition to that, we prove our claim with a short
proof and examples for each case.
2 The advantage of working in
complex domain
2.1 Real domain
Let the determinant of a polynomial matrix A(x, y)
which is a polynomial p(x, y)whose degrees are k1=
degx(p(x, y)) = 3 and k2=degy(p(x, y)) = 2 re-
spectively. According to [12], working in rectangular
basis, we need to define N= (k1+ 1)·(k2+1) = 12
required fixed points. The set of these points is
S(3,2) ={(x1, y2)|1= 0, . . . , 32= 0, . . . , 2}
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.37
Dimitrios Varsamis, Angeliki Kamilali
E-ISSN: 2224-2880
319
Volume 21, 2022
and a set of S(3,2) is showing in figure 1.
Figure 1: Real domain
We evaluate these points to the matrix
A(x, y)to find the constant determinants at the
fixed points and construct the zero order table
(k= 0) of divided differences. (12 evaluations)
y0=2y1= 0 y2= 2
x0=3P0,0(0) =24 P0,1(0) =28 P0,2(0) =38
x1=1P1,0(0) =4P1,1(0) =2P1,2(0) =8
x2= 1 P2,0(0) =6P2,1(0) = 0 P2,2(0) =2
x3= 3 P3,0(0) = 16 P3,1(0) = 26 P3,2(0) = 28
For k= 1 to n, where n=max{k1, k2}= 3 we
compute the k-th order table of divided differences
according to [14]. The Newton polynomial (the
determinant of A(x, y)) is:
p(x, y) = x3+x·yy21
It occurs from the following:
p(x, y) = XT·P·Y
where
X=
1
x+ 3
(x+ 3)(x+ 1)
(x+ 3)(x+ 1)(x1)
,
Y="1
y+ 2
y(y+ 2)#,
P=
26 11
11 1 0
3 0 0
1 0 0
Pis the n-th order table of divided differences.
2.2 Complex domain
Let the same determinant of a polynomial matrix
A(x, y)which is a polynomial p(x, y)and lets define
the 12 required points in complex domain. The set of
these points is
e
S(3,2) ={(a1, b2)|1= 0, . . . , 3, 2= 0, . . . , 2}
According to [4] and due to the conjugate properties,
the number of evaluations can be reduced. We can
distinguish two subcases.
2.2.1 First case
Points of the form (a1·i, b2)where 1= 0, . . . , 3,
2= 0, . . . , 2and iis the imaginary unit. We have
to evaluate only the circle points as they are showing
in figure 2. The square ones can occur as conjugate
numbers of them. (6 evaluations) We evaluate these
Figure 2: Complex domain, points of the form (a1·
i, b2), circles and squares
points to the matrix A(x, y)to find the constant
determinants at the fixed points and construct the
zero order table (k= 0) of divided differences.
b0=2b1= 0 b2= 2
a0=3i P0,0(0) =5 + 33i P0,1(0) =1 + 27i P0,2(0) =5 + 21i
a1=i P1,0(0) =5 + 3i P1,1(0) =1 + i P1,2(0) =5i
a2=i P2,0(0) =53i P2,1(0) =1iP2,2(0) =5+i
a3= 3i P3,0(0) =533i P3,1(0) =127i P3,2(0) =521i
Conjugate numbers are denoted by bold
For k= 1 to n, where n=max{k1, k2}= 3 we
compute the k-th order table of divided differences.
The Newton polynomial (the determinant of A(x, y))
is:
p(x, y) = x3+x·yy21
It occurs from the following:
p(x, y) = e
XT·e
P·e
Y
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.37
Dimitrios Varsamis, Angeliki Kamilali
E-ISSN: 2224-2880
320
Volume 21, 2022
where
e
X=
1
x+ 3i
(x+ 3i)(x+i)
(x+ 3i)(x+i)(xi)
,
e
Y="1
y+ 2
y(y+ 2)#,
e
P=
5 + 33i23i1
15 1 0
3i0 0
1 0 0
Pis the n-th order table of divided differences.
2.2.2 Second case
Points of the form (a1, b2·i)where 1= 0, . . . , 3,
2= 0, . . . , 2and iis the imaginary unit. We have
to evaluate both round and asterisk points as they are
showing in figure 3. The square points can occur as
conjugate numbers of the round ones. (8 evaluations)
We evaluate these points to the matrix A(x, y)to
Figure 3: Complex domain,points of the form
(a1, b2·i)
find the constant determinants at the fixed points and
construct the zero order table (k= 0) of divided
differences.
k= 0 b0=2i b1= 0 b2= 2i
a0=3P0,0(0) =24 + 6i P0,1(0) =28 P0,2(0) =24 6i
a1=1P1,0(0) = 2 + 2i P1,1(0) =2P1,2(0) =22i
a2= 1 P2,0(0) = 4 2i P2,1(0) = 0 P2,2(0) =4+2i
a3= 3 P3,0(0) = 30 6i P3,1(0) = 26 P3,2(0) =30 +6i
For k= 1 to n, where n=max{k1, k2}= 3 we
compute the k-th order table of divided differences.
The Newton polynomial (the determinant of A(x, y))
is:
p(x, y) = e
XT·e
P·e
Y
It occurs from the following:
e
X=
1
x+ 3
(x+ 3)(x+ 1)
(x+ 3)(x+ 1)(x1)
,e
Y="1
y+ 2i
y(y+ 2i)#,
e
P=
24 + 6i3+2i1
13 2i1 0
3 0 0
1 0 0
the n-th order table of divided differences.
From the above we can conclude that the number of
necessary evaluations that have to be computed in
the evaluation part, depends on the form of points.
Whether abscissa or ordinate are complex number,a
different number of evaluations must be executed in
each case. That’s why we are going to indicate the
best form, depending on the degree of each variable.
3 Analysing cases.
For every polynomial p(x,y) where k1=degPx,k2=
degPy. We have the following cases:
k1even, k2odd
If we choose points of the form (a·i, b)we
have e
N=N/2 + (k2+ 1)/2
If we choose points of the form (a, b ·i)we
have e
N=N/2
k1odd, k2even
If we choose points of the form (a·i, b)we
have e
N=N/2
If we choose points of the form (a, b ·i)we
have e
N=N/2 + (k1+ 1)/2
k1odd, k2odd
If we choose points of the form (a·i, b)we
have e
N=N/2
If we choose points of the form (a, b ·i)we
have e
N=N/2
k1even, k2even
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.37
Dimitrios Varsamis, Angeliki Kamilali
E-ISSN: 2224-2880
321
Volume 21, 2022
if k1< k2
*If we choose points of the form (a·i, b)
we have e
N= (N(k2+ 1))/2 + k2+
1 = N/2 + (k2+ 1)/2
*If we choose points of the form (a, b ·i)
we have e
N= (N(k1+ 1))/2 + k1+
1 = N/2 + (k1+ 1)/2
if k1> k2
*If we choose points of the form (a·i, b)
we have e
N= (N(k2+ 1))/2 + k2+
1 = N/2 + (k2+ 1)/2
*If we choose points of the form (a, b ·i)
we have e
N= (N(k1+ 1))/2 + k1+
1 = N/2 + (k1+ 1)/2
The cases are summarized in the following
scheme:
k1odd k2odd (a·i, b)or (a, b ·i)
k2even (a·i, b)
k1even
k2odd (a, b ·i)
k2even k1< k2(a, b ·i)
k1> k2(a·i, b)
4 Examples
4.1 k1even, k2odd
Let the determinant of a polynomial matrix
A(x, y)which is a polynomial p(x, y)whose de-
grees are k1=degx(p(x, y)) = 2 and k2=
degy(p(x, y)) = 9 respectively.
N= (k1+ 1) ·(k2+ 1) = 30 the number of
required points.
We choose the required points from real domain.
The set of these points is:
S(2,9) ={(x1, y2)|1= 0, . . . , 22= 0, . . . , 9}
S(2,9) is showing in figure 4. In this case we need
to evaluate 30 points.
Let the same polynomial, and lets define now the
required points in complex domain.
The set of these points is:
e
S(2,9) ={(a1, b2)|1= 0, . . . , 22= 0, . . . , 9}
There are two subcases.
Figure 4: Real domain
Points of the form (a1·i, b2)where 1=
0, . . . , 22= 0, . . . , 9, i is the imaginary
unit. We need to evaluate both asterisk and
round points as they are showing in figure
5. The square ones occurs automatically due
to the conjugate properties. In this case we
need to evaluate 20 points.
Figure 5: Complex domain,points of the form (a1·
i, b2)
Points of the form (a1, b2·i)where 1=
0, . . . , 22= 0, . . . , 9, i is the imaginary
unit. We need to evaluate only the round
points as they are showing in figure 6. The
square ones occurs automatically due to the
conjugate properties. In this case we need
to evaluate 15 points.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.37
Dimitrios Varsamis, Angeliki Kamilali
E-ISSN: 2224-2880
322
Volume 21, 2022
Figure 6: Complex domain,points of the form
(a1, b2·i)
4.2 k1odd, k2even
Let the determinant of a polynomial matrix
A(x, y), which is a polynomial p(x, y)whose de-
grees are k1=degx(p(x, y)) = 9 and k2=
degy(p(x, y)) = 2 respectively.
N= (k1+ 1) ·(k2+ 1) = 30 the number of
required points.
We choose the required points from real domain.
The set of these points is:
S(9,2) ={(x1, y2)|1= 0, . . . , 92= 0, . . . , 2}
S(9,2) is showing in figure 7. In this case we need
Figure 7: Real domain
to evaluate 30 points.
Let the same polynomial, and lets define now the
required points in complex domain.
The set of these points is:
e
S(9,2) ={(a1, b2)|1= 0, . . . , 92= 0, . . . , 2}
There are two subcases.
Points of the form (a1·i, b2)where 1=
0, . . . , 92= 0, . . . , 2, i is the imaginary
unit. We need to evaluate only the round
points as they are showing in figure 8. The
square points occurs automatically due to
the conjugate properties. In this case we
need to evaluate 15 points.
Figure 8: Complex domain,points of the form (a1·
i, b2)
Points of the form (a1, b2·i)where 1=
0, . . . , 92= 0, . . . , 2, i is the imaginary
unit. We need to evaluate both asterisk and
round points as they are showing in figure
9. The square ones occurs automatically due
to the conjugate properties. In this case we
need to evaluate 20 points.
4.3 k1odd, k2odd
Let the determinant of a polynomial matrix
A(x, y), which is a polynomial p(x, y)whose de-
grees are k1=degx(p(x, y)) = 5 and k2=
degy(p(x, y)) = 7 respectively.
N= (k1+ 1) ·(k2+ 1) = 48 the number of
required points.
We choose the required points from real domain.
The set of these points is:
S(5,7) ={(x1, y2)|1= 0, . . . , 52= 0, . . . , 7}
S(5,7) is showing in figure 10. In this case we
need to evaluate 48 points.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.37
Dimitrios Varsamis, Angeliki Kamilali
E-ISSN: 2224-2880
323
Volume 21, 2022
Figure 9: Complex domain,points of the form
(a1, b2·i)
Figure 10: Real domain
Let the same polynomial, and lets define now the
required points in complex domain.
The set of these points is:
e
S(5,7) ={(a1, b2)|1= 0, . . . , 52= 0, . . . , 7}
There are two subcases.
Points of the form (a1·i, b2)where 1=
0, . . . , 52= 0, . . . , 7, i is the imaginary
unit. We need to evaluate only the round
points as they are showing in figure 11. The
square ones occurs automatically due to the
conjugate properties. In this case we need
to evaluate 24 points.
Points of the form (a1, b2·i)where 1=
0, . . . , 52= 0, . . . , 7, i is the imaginary
unit. We need to evaluate only the round
Figure 11: Complex domain, points of the form (a1·
i, b2)
points as they are showing in figure 12. The
square ones occurs automatically due to the
conjugate properties. In this case we need
to evaluate 24 points.
Figure 12: Complex domain, points of the form
(a1, b2·i)
As we can see, if both k1and k2are odd we can
reduce the number of evaluated points even up
to the half by choosing points of either the form
(a·i, b)or (a, b ·i)where a, b ϵ Rand i is the
imaginary unit.
4.4 k1even, k2even, k1< k2
Let the determinant of a polynomial matrix
A(x, y), which is a polynomial p(x, y)whose de-
grees are k1=degx(p(x, y)) = 4 and k2=
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.37
Dimitrios Varsamis, Angeliki Kamilali
E-ISSN: 2224-2880
324
Volume 21, 2022
degy(p(x, y)) = 12 respectively.
N= (k1+ 1) ·(k2+ 1) = 65 the number of
required points.
We choose the required points from real domain.
The set of these points is:
S(4,12) ={(x1, y2)|1= 0, . . . , 42= 0, . . . , 12}
S(4,12) is showing in figure 13 In this case we
Figure 13: Real domain
need to evaluate 65 points.
Let the same polynomial, and lets define now the
required points in complex domain.
The set of these points is:
e
S(4,12) ={(a1, b2)|1= 0, . . . , 42= 0, . . . , 12}
There are two subcases.
Points of the form (a1·i, b2)where 1=
0, . . . , 42= 0, . . . , 12, i is the imagi-
nary unit. We need to evaluate both round
and asterisk points as they are showing in
figure 14. The square points occurs auto-
matically due to the conjugate properties. In
this case we need to evaluate 39 points.
Points of the form (a1, b2·i)where 1=
0, . . . , 42= 0, . . . , 12, i is the imagi-
nary unit. We need to evaluate both round
and asterisk points as they are showing in
figure 15. The square points occurs auto-
matically due to the conjugate properties. In
this case we need to evaluate 35 points.
4.5 k1even, k2even, k1> k2
Let the determinant of a polynomial matrix
A(x, y), which is a polynomial p(x, y)whose de-
grees are k1=degx(p(x, y)) = 12 and k2=
Figure 14: Complex domain, points of the form (a1·
i, b2)
Figure 15: Complex domain, points of the form
(a1, b2·i)
degy(p(x, y)) = 4 respectively.
N= (k1+ 1) ·(k2+ 1) = 65 the number of
required points.
We choose the required points from real domain.
The set of these points is:
S(12,4) ={(x1, y2)|1= 0, . . . , 12 2= 0, . . . , 4}
S(12,4) is showing in figure 16. In this case we
need to evaluate 65 points.
Let the same polynomial, and lets define now the
required points in complex domain.
The set of these points is:
e
S(12,4) ={(a1, b2)|1= 0, . . . , 12 2= 0, . . . , 4}
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.37
Dimitrios Varsamis, Angeliki Kamilali
E-ISSN: 2224-2880
325
Volume 21, 2022
Figure 16: Real domain
There are two subcases.
Points of the form (a1·i, b2)where 1=
0, . . . , 12 2= 0, . . . , 4, i is the imagi-
nary unit. We need to evaluate both round
and asterisk points as they are showing in
figure 17. The square points occurs auto-
matically due to the conjugate properties. In
this case we need to evaluate 35 points.
Figure 17: Complex domain,points of the form (a1·
i, b2)
Points of the form (a1, b2·i)where 1=
0, . . . , 12 2= 0, . . . , 4, i is the imagi-
nary unit. We need to evaluate both round
and asterisk points as they are showing in
figure 18. The square points occurs auto-
matically due to the conjugate properties. In
this case we need to evaluate 39 points.
Figure 18: Complex domain,points of the form
(a1, b2·i)
5 Results
To put it concisely, we present the number of cal-
culations that have to be made in evaluation part,
according to the degrees of each variable k1, k2.
The number in parentheses represents the number of
required evaluations while working in real domain.
The number in brackets represents the number of
required evaluations in complex domain, when points
are of the form (a·i, b), where a, b Rand iis the
imaginary unit. The number in curly brackets repre-
sents the number of required evaluations in complex
domain, when points are of the form (a, b ·i), where
a, b Rand iis the imaginary unit.:
k1= 10, k2= 10 : (121)[66]{66}
k1= 10, k2= 15 : (176)[96]{88}
k1= 10, k2= 20 : (231)[126]{121}
k1= 15, k2= 10 : (176)[88]{96}
k1= 15, k2= 15 : (256)[128]{128}
k1= 15, k2= 20 : (336)[168]{176}
k1= 20, k2= 10 : (231)[121]{126}
k1= 20, k2= 15 : (336)[176]{168}
k1= 20, k2= 20 : (441)[231]{231}
In the following matrix, all these cases are pre-
sented. Numbers in bold indicate the optimal case
according to the degree of each variable.
k2= 10 k2= 15
k1= 10 (121)[66]{66}(176)[96]{88}
k1= 15 (176)[88]{96}(256)[128]{128}
k1= 20 (231)[121]{126}(336)[176]{168}
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.37
Dimitrios Varsamis, Angeliki Kamilali
E-ISSN: 2224-2880
326
Volume 21, 2022
k2= 20
k1= 10 (231)[126]{121}
k1= 15 (336)[168]{176}
k1= 20 (441)[231]{231}
6 Conclusion
Taking advantage of working in complex domain,
a way to reduce the number of evaluations in
evaluation-interpolation technique has been pro-
posed. This way is to determine the specific form
of required points. Choosing the best form depends
on the degree of each variable, whether it is even or
odd. As we can see it can lead to an optimal reduc-
tion of computations in evaluation part, even up to the
half. Consequently, less necessary operations have to
be made and the execution time of the process will
also be reduced.
References:
[1] Gasca M. and Sauer T., Polynomial Interpola-
tion in Several Variables, Advances in Compu-
tational Mathematics, Vol.12, No.4, 2000, pp.
377-410.
[2] Neidinger R., Multivariate Polynomial Interpo-
lation in Newton Forms, Society for Industrial
and Applied Mathematics, Vol.61, No.2, 2019,
pp. 361-381.
[3] Henrion, D. and Sebek M., Improved polyno-
mial matrix determinant computation. Circuits
and Systems I: Fundamental Theory and Ap-
plications, IEEE Transactions , Vol.46, No.10,
1999, pp. 1307-1308.
[4] Varsamis D., Calculation of Determinant of a
polynomial Matrix in Complex Basis, Contem-
porary Engineering Sciences, Vol. 13, No.1,
2020, pp. 351-358.
[5] Karampetakis, N., Computation of the general-
ized inverse of a polynomial matrix and applica-
tions. Linear Algebra and its Applications, Vol.
252, No.1-3, 1997, pp. 35-60.
[6] Vologiannidis S. and Karampetakis N.: Inverses
of multivariable polynomial matrices by discrete
fourier transforms, Multidimensional Systems
and Signal Processing, Vol. 15, No.4, 2004, pp.
341-361.
[7] Kafetzis I. and Karampetakis N.: On the alge-
braic stucture of the Moore - Penrose inverse of
a polynomial matrix, IMA Journal of Mathemat-
ical Control and Information, 2021.
[8] Petkovic M. and Stanimirovic P.: Interpolation
algorithm for computing Drazin inverse of poly-
nomial matrices, Linear Algebra nad its Appli-
cations, Vol. 422, No.2-3, 2007, pp. 526-539.
[9] Tzekis P., Karampetakis N., and Terzidis H., On
the computation of the gcd of 2-d polynomials,
International Journal of Applied Mathematics
and Computer Science, Vol. 17, No.4, 2007, pp.
463-470.
[10] Antoniou, E. G., Transfer function computation
for generalized n-dimensional systems. Journal
of the Franklin Institute, Vol. 338, No.1, 2001,
pp. 83-90.
[11] Antsaklis P. and Gao Z.: Polynomial and ra-
tional matrix interpolation: theory and control
applications, International Journal of Control,
Vol. 58, No.2, 1993, pp. 349-404.
[12] Varsamis D. and Karampetakis N., On a Special
Case of the two - variable Newton Interpolation
Polynomial, IEEE, 2012, pp. 1-6.
[13] Varsamis D. and Karampetakis N. and Mas-
torocostas P.: An optimal bivariate polyno-
mial interpolation basis for the application of
the evaluation-interpolation technique, Applied
Mathematics & Information Sciences, Vol. 8,
No.1, 2014, pp. 117-125.
[14] Varsamis D. and Karampetrakis N., On the New-
ton bivariate polynomial Interpolation with ap-
plications, Multidimensional Systems and Sig-
nal Processing, Vol.25, No.1, 2014, pp. 179-
209.
Contribution of individual authors to
the creation of a scientific article
(ghostwriting policy)
Author Contributions: Please, indicate the role
and the contribution of each author:
Example
In this paper the authors has working equally
Sources of funding for research
presented in a scientific article or
scientific article itself
Report potential sources of funding if there is any
This work is supported by MSc in Applied Informat-
ics, of the Department of Computer, Informatics and
Telecommunications Engineering, International Hel-
lenic University.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.37
Dimitrios Varsamis, Angeliki Kamilali
E-ISSN: 2224-2880
327
Volume 21, 2022
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the Creative
Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en_US
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.37
Dimitrios Varsamis, Angeliki Kamilali
E-ISSN: 2224-2880
328
Volume 21, 2022