- Email: [email protected]

13 September 1991

Achim Schweikard * Technische Universitiit Berlin, Berlin, Germany Communicated by D.A. Plaisted Received 4 June 1990 Revised 27 June 1991

Abstract Schweikard, A., Trigonometric polynomials with simple roots, Information

Processing Letters 39 (1991) 231-236.

Trigonometric polynomials frequently occur in applications in physics, numerical analysis and engineering, since each periodic function can be approximated by a trigonometric polynomial. Additionally, there are many analogies between trigonometric and standard algebraic polynomials. Algorithms in computer algebra depend on methods for the square-free decomposition cf polynomials. These methods use polynomial division and cannot be applied directly to trigonometric polynomials. Let P denote the set of odd multiples of a. A trigonometric polynomial T * is a reduced representation of a trigonometric polynomial T if the set of zeros of T in C\ P is the same as the set of zeros of T * in C\ P, and if all zeros of T * are simple zeros. It is shown that a reduced representation of a trigonometric polynomial with rational or algebraic coefficients can be found in polynomial time. Keywords: Analysis of algorithms, computer algebra, trigonometric square-free divisor

and exponential

polynomial,

root multiplicity, greatest

1. Introduction

We will consider expressions of the form n

T(x) =a,+

c

(ai, cos kx + b, sin kx).

k=l

T is called a trigonometric polynomial; n is the degree of T if 1a,, 1 + 1b,, 1 > 0. Trigonometric polynomials are the basis of Fourier analysis and approximation theory; each periodic function can be approximated by a trigcnometric polynomial. The greatest square-free divisor of a standard algebraic polynomial A with integer coefficients is a polynomial having the same roots as A but all roots are simple, i.e. the multiplicity of each root is one; greatest square-free divisor computation for algebraic polynomials is a basic step in many algebraic algorithms. Numeric techniques for root approximation work well if all roots are simple; however, problems arise if there are multiple roots. We consider the problem of reducing root multiplicities for trigonometric polynomials. Let P := ((2k + l)lrr I k integer}. It will be shown that each trigonometric polynomial can be replaced by a trigonometric polynomiai with the same zeros in C \P such that all zeros are simple. The coefficients of the new trigonometric polynomial are rational or algebraic if the coefficients of the input polynomial are rational or algebraic respectively. Asymptotic time bounds for reducing root multiplicities are polynomial but larger than corresponciing bounds for algebraic square-free divisor computation. The method for reducing root multiplicities is simple: The given trigonometric polynomial is * Author’s address: Robotics Laboratory, Computer Science Department, 0020-0190/91/$03.50

Stanford University, Stanford, CA 94305, U.S.A.

0 1991 - Elsevier Science Publishers B.V. All rights reserved

231

INFORMATION

Volume 39, Number 5

PROCESSING

LETTERS

13 September 1991

transformed to an algebraic polynomial while maintaining root multiplicities. The greatest square-free of this algebraic polynomial is then re-transformed to a trigonometric polynomial. A trigonometric polynomial T * will be called a reduced representation of a trigonometric polynomial T, if the set of zeros the set of zeros of T in C \ P and if all zeros of T* are si of T* inC\P is thesamea: Simple examples show that polynomial division for algebraic polynomials cannot be generalized to the case of trigonometric polynomials. However, the subset of trigonometric polynomials of the form (1) with coefficients b, = b, = - - - = bN= 0 is a Euclidean ring [3]. This subset is called the ring of cosine-polynomials. The derivative of a cosine-polynomial is not a cosine-polynomial. Therefore, a reduced representation of a cosine-polynomial cannot be calculated using the arithmetic in this Euclidean ring. divisor

representations of trigonometric

ials

Let S := {x+iyEC] - IT< x < 7~}. Then the set S contains exactly 2n zeros of a trigonometric polynomial T of degree n; if x1,. . . , x2,, are the zeros of T in S, then T can be written in the form

with a constant QL[2,4]. We define an algebraic polynomial A(T) with coefficients trigonometric polynomial T of degree n by setting

co,. . . , cZn corresponding

13/A ZJu,,(j,

cZI = a

I)+

c

1

p(j,k)u,,(j-2k,

Nii

bJ

j=l

for/=0

I)

k=l

c21+ 1 =

to a given

,...,

n,

I

I)/21 c

2.q(j,

k)u,_,(j-(2k+l),

I)

forI=&...,n-1,

k=O

where U,,,(& I) := i

(-l)“(i)(y_-i)

for s=O ,...,

m and I=0 ,...,

m

h=O

and

. Let t 19..., t, be the zeros of the poiynomial A( T ) and q, . . . , Q. be the corresponding multiplicities. The zeros of T in 3:\ ( *R>, where S := ( x + i y E C 1- T < x < T >, are the values x,, where Xi = hCtg( ti ); the vvnultiplicities of the zeros of T are given by q, . ..) &k. . The proof directly follows from the equations lj/A

2cos

jx=(2cosx)‘+

C

(-l)xi

k(

j-(k+l) k_l

)(2c0sx)J-2k,

k=l

sin jx = sin x

232

2’(_l)k(

j-

(i+

1))(2 cos x)j-GX+lJ]

Volume 39, Number 5

INFORMATION PROCESSING LETTERS

and uses the substitution

t = tan x/2.

13 September 1991

•I

Conversely, let m > 0, n := [m/21 and A=c,+c,t+c,t2+

-0. fc,,P

be an algebraic polynomial. If the degree m of A is odd, then we set c2,, := 0. A trigonometric polynomial T(A) with coefficients a,, . . . , a,,, b,, . . . , bn which corresponds to the algebraic polynomial A is defined in the following way. Let

’i

2” j=O 4S.k lJc2j

+=

CL+1 :=

$jn~‘u~_,(

for t=O,...,

j, I )

n,

forI=O,...,n-1,

Czj+l

J=o

n --. 1

I-l fo := i

, 71

cij+l&(

j=O n-l

fk

I-l := ;:

’ c4j+l

122j-1

,

k=l,...,

I?]

+l,

j=k

&:=

c

1 - 2j-2 2

“ij-1

j=k

k

=

3

1

,‘“,

In the above expressions, a sum in which the lower index bound is larger than the upper index bound is set to zero by convention. The coefficients ak and b, of a trigonometric polynomial T(A) are defined by: n 2

II Qo :=

c

j=O

1 2j I clijir7i L-J (\ j

i'

1 22j-1

2j (

j-l

I-l n+l 2

a21-1 :=

c

)

'

1 i

cij-2

m

?

l=l,...,

j=l

2

2j-1 j-l

1

’

1I

I= 1,

,_;,

1= 1,

,

n+l 2

I J ’

b,:=fo_$, b

:=

ST/--gi+1 2

21

;, I

fi -f,+,

b 2/+1 :=-,

2

I=1 ,...)

I

I

n-l --i-

. J 233

13 September 1991

INFORMATION PROCESSING LETTERS

Volume 39, Number 5

mma 2. If t,, . . . , t, are the zeros of A, then the zeros of ?(A) each zero x, occurs with the same multiplicity as the corresponding

in S\ ( T > are the values x, = 2arctg( t,); zero t,.

f. The polynomial co + c,t +

czt2+ - * - +c2,,t2t1

can be written in the form n-1 i

Ii=0

4x-(1

_

t2)k(l

+

t2)“-k

+

ci,+,(l

2t c

tan x/2 for t and dividing by (1 + tan2x/2)”

Substituting

- t2)k(l

+ P)“?

k=O

for x in S\

{err } we obtain

the expression

n-1

i

cik(cos x)” + sin x C cik+,(cos

This expression is a trigonometric

cop-1x

and the trigonometric

x)“.

k=O

k=O

=.

k &,s,(

polynomial

2k-1 k-j

)

and can be written in the form (1) using the equations

cos(2 j - 1)x

addition formulas. The coefficients

of this trigonometric

polynomial

are the values

ah, 6, defined above. If x is not an odd multiple of V, then

T(A)(x)

= (A(tan

x/2))/@

+ tadx/2)“.

Considering sequences of derivatives on both sides of this equation shows that a zero of T(A) occurs with the same multiplicity as the corresponding zero of A. 0 a 3. Let T be a trigonometric polynomial

T * := T(A(T)/gcd(A(T),

polynomial A’(T)))

with rationa[ or algebraic coefficients. is a reduced representation of T.

Then the trigonometric

oaf. Let A* := A( T)/gcd( A( T), A’(T)). A* is square-free. Equation (3) and Lemma 1 show that each zero of T within S\{ a} is a zero of T* and vice versa and that all zeros of T * within S\ { T} are simple. It remains to be shown that T is not a multiple zero of T *, i.e. if v is a zero of T *, then the multiplicity of this zero is always one. Let k be the degree of A *; then the degree of T * = T( A* ) is [k/21. There are exactly 2[k/21 real and complex zeros of T( A * ) in the set S. Each zero of A * corresponds to a zero of T( A * ) in S\ { ‘TT } and 21k/2] < k + 1. Therefore, T cannot occur as multiple zero of T *. •I

Lemma 3 describes an algorithm for the calculation of a reduced representation T *. This algorithm is based on the computation of the greatest common divisor of two algebraic polynomials. Note that 7 can occur as (simple) zero of T * even though T is not a zero of the input polynomial T, and vice versa; this condition can be tested directly because the value T is a zero of a trigonometric polynomial with the coefficients a,, . . . t a,,, b ,,..., bt, if and only if the sum of the values (-l)“& (k=O,...,n) iszero. 234

Volume 39. Number 5

INFORMATION PROCESSING LETTERS

13 September 1991

. The function T(x) defined by

T(x)

:= gsin$

is a trigonometric

polynomial,

x-; -sin2

-sin;

,sinx-?r -

(4

2

since T(x) can be written in the form

T(x)=l-2sinx-cos2x+sin2x by applying the trigonometric addition formulas. The definition of T(x) in (4) shows that the zeros of this polynomial are the values 0, lrr/2 and ?r, where the value 0 occurs as double zero. The corresponding algebraic polynomial is the polynomial A(t)

= 8t2 - 8t3.

The positive greatest square-free divisor of A is A*(t)=t’-t. The corresponding T*(x) The zeros of T*(x) representation.

trigonometric

polynomial

= $ - i cos x-

is given by

$ sin x.

are the values 0 and v/2.

Therefore,

the zero at 7r does not occ Jr in the reduced

ExampIe 5. The four zeros of T(x)=l-2cosx+cos2x are given by 0, 7rr/2 and -~/2,

T*(x)

= sin 2x.

In this case v is a zero of T*(x)

3. Computing

where 0 is again a double zero. Here we obtain the reduced representation

whereas 7~is not a zero of the input polynomial

T(x).

time

We will consider a trigonometric polynomial T of degree n and integer coefficients ao, . . . , a,, b,, . . . , Sn. Let K be a bound for the coefficients of T, i.e. K > max{ 1ai I} and K > max{ 1bi I}. A binomial coefficient of the form (t), n >, k can be evaluated in Q( n2 - (log2n)2) operations using standard integer arithmetic. Then the coefficients of the algebraic polynomial A(T) can be deterimined in 0( n6(log2n)2 + n2(log2 K )2) operations. Let A be an algebraic polynomial of degree n 9 and d be a bound for the sum of the absolute values of the coefficients of A. Then it can be shown [l] that the time required for the calculation of the greatest square-free divisor of A is bounded by Q( n4 - log2(nd)2). The sum of the absolute values of the coefficients of A(T) is bounded by the value K’ := ~z~2~“K. Therefore, the greatest square-free divisor A * of A(T) can be determined in Q( n6 + n4 . (log2K)‘) operations. Finally, considering the polynomial 23”A* instead of A*, we can assume that the coefficients of the corresponding trigonometric polynomial T( A* ) are integers. T( A*) can then be determined in (n6(log2n)2 + n3 * (log2K)2). The total time required for the calculation of the reduced representation is then bounded by O(n6(log2n)2 + n4(log2K)2). 235

Table 1 Computing times for test polynomials T,,(x);

j?r= 2n

m

2

4

8

t

1180 73.7

2250 8.7

1438 3.5

t/m”

13 September 1991

INFORMATION PROCESSING LETTERS

Volume 39. Number 5

Table 1 shows computing times for a set of 7&(x) = 1 - cos 2nx of degree 2n = 2,4, 8 an 1 - cos 2nx = 2 sin nx sfn nx. The computing times in this tabie are stated in Macintosh II Computer with 8 MB main storage.

16

entation

on a

. ~oncl~io~

It was shown that for each trigonometric polynomial ere is a reduced representation with rational coefficients, and this represe O( n6(log,n)2 + n4(logzK)‘) time, whereas the determination of the square-free part of an algebraic polynomial takes at most 0( nb - log,( nK )2) steps. Here n denotes the degree of the in ut polynomial and K is a bound for the size of the coefficients. Numeric methods can be used to find approximations for all real and complex roots of trigonometric polynomials [2]. The application of these methods can be simplified and improved if reduced representations of the input polynomials are used. Since each trigonometric polynomial can be written in the form (2), there is a close analogy between algebraic square-free divisor computation and the described reduction method for trigonometric polynomials. An exponential polynomial is an expression of the form (l), where the sub-expressions cos kx and sin kx are replaced by the expressions exp( kx) and exp( - kx), respectively. With slight modifications the described methods can be applied to the case of exponential polynomials and to trigonometric polynomials with algebraic coefficients, such as coefficients of the form sin( FE) and cos(sa) with rational numbers r and s.

[l] L-E. Heindel, Integer arithmetic algorithms for polynomial red zero determination, J. ACM 1 [2] LV. Makrelov and K.I. Semerdzhiev, Methods of finding simultaneously all the roots of algebraic, trigonometric and exponential equations, U.S.S.R Comput. Math. and Math. Phys. 24 (5) (1984) 99-105.

236

[3] P. Schom, A canonical simplifier for trigonometric expressions in the kinematic equation, Inform. Process. Lett. B (1988) 241-246. [4] H.J. Stoer, Numerische Muthematik (Springer, Berlin, 1980).