<<

. 51
( 83 .)



>>

algorithms. In Section 3 we show that the two algorithms are mathematically equivalent. In Section
4 we give an e cient implementation for the Ford“Sidi algorithm. This implementation is slightly
more economical than the original implementation for the Ford“Sidi algorithm.



2. The E-algorithm and the Ford“Sidi algorithm ” review

Throughout this paper let s = (sn ) be any sequence to be transformed and gj = (gj (n)), j = 1; 2; : : : ;
be any auxiliary sequences. We denote 1 by the constant sequence with 1n = 1, for n = 0; 1; : : : :
Assume that all denominators are nonzero.


2.1. The E-algorithm
(n) (n)
The E-algorithm is deÿned as follows. For n = 0; 1; : : : ; the quantities Ek and gk; j are deÿned by

(n)
E0 = sn ;
(n)
g0; j = gj (n); j = 1; 2; : : : ;


(n) (n+1) (n+1) (n)
Ek’1 gk’1; k ’ Ek’1 gk’1; k
(n)
Ek = ; k = 1; 2; : : : ; (3)
(n+1) (n)
gk’1; k ’ gk’1; k


(n) (n+1) (n+1) (n)
gk’1; j gk’1; k ’ gk’1; j gk’1; k
(n)
gk; j = ; k = 1; 2; : : : ; j = k + 1; : : : : (4)
(n+1) (n)
gk’1; k ’ gk’1; k

The recurrence relations (3) and (4) are called the main rule and the auxiliary rule of the E-algorithm,
respectively. Brezinski [1] proved the following theorem using Sylvester™s determinantal identity.
N. Osada / Journal of Computational and Applied Mathematics 122 (2000) 223“230 225

(n) (n)
Theorem 1. For n = 0; 1; : : : ; and k = 1; 2; : : : ; Ek and gk; j are represented as
sn ··· sn+k 1 ··· 1
g1 (n) · · · g1 (n + k) g1 (n) · · · g1 (n + k)
(n)
Ek = ;
··· ···
gk (n) · · · gk (n + k) gk (n) · · · gk (n + k)

gj (n) · · · gj (n + k) 1 ··· 1
g1 (n) · · · g1 (n + k) g1 (n) · · · g1 (n + k)
(n)
gk; j = ; j ¿ k;
··· ···
gk (n) · · · gk (n + k) gk (n) · · · gk (n + k)
respectively.
(n) (n) (n+1) (n)
If we set ck = gk’1; k =(gk’1; k ’ gk’1; k ), then (3) and (4) become
(n) (n) (n) (n+1) (n)
Ek = Ek’1 ’ ck (Ek’1 ’ Ek’1 ); k ¿ 0; (5)

(n) (n) (n) (n+1) (n)
gk; j = gk’1; j ’ ck (gk’1; j ’ gk’1; j ); k ¿ 0; j ¿ k; (6)
respectively.
(n’k) (n)
, 06n6N; 06k6n, requires 1 N 3 + O(N 2 ) gk; j ™s.
For given s0 ; : : : ; sN , the computation of Ek 3
The number of operation counts for the E-algorithm, as mentioned in [1], is 5 N 3 + O(N 2 ), while
3
that with the implementation using (5) and (6) becomes N 3 + O(N 2 ). More precisely, the latter is
N3 + 5N2 + 3N.
2 2
We remark that Ford and Sidi [4] implemented the E-algorithm by rewriting in the forms
(n+1) (n) (n)
Ek’1 ’ ck Ek’1
(n)
Ek = ; k ¿ 0; (7)
(n)
dk
(n+1) (n) (n)
gk’1; j ’ ck gk’1; j
(n)
gk; j = ; k ¿ 0; j ¿ k; (8)
(n)
dk
(n) (n+1) (n) (n) (n)
where ck = gk’1; k =gk’1; k , and dk = 1 ’ ck . The implementation using (7) and (8) requires exactly
the same number of arithmetic operations as that using (5) and (6). However, one can avoid the
loss of signiÿcant ÿgures by using (5) and (6).

2.2. The Ford“Sidi algorithm

The Ford“Sidi algorithm is deÿned as follows. Let u = (un ) be one of sequences s = (sn ), 1, or
gj = (gj (n)). The quantities k(n) (u) are deÿned by
un
(n)
0 (u) = ; (9)
g1 (n)
226 N. Osada / Journal of Computational and Applied Mathematics 122 (2000) 223“230

(n+1) (n)
k’1 (u) ’ k’1 (u)
(n)
k (u) = ; k ¿ 0: (10)
(n+1) (n)
k’1 (gk+1 ) ’ (gk+1 )
k’1

Ford and Sidi [4] proved the following theorem using Sylvester™s determinantal identity.

(n)
Theorem 2. For n = 0; 1; : : : ; and k = 1; 2; : : : ; k (u) are represented as
un ··· un+k gk+1 (n) · · · gk+1 (n + k)
g1 (n) · · · g1 (n + k) g1 (n) · · · g1 (n + k)
(n)
k (u) = :
··· ···
gk (n) · · · gk (n + k) gk (n) · · · gk (n + k)

By Theorems 1 and 2, Tk(n) can be evaluated by
(n)
k (s)
Tk(n) = : (11)
(n)
(1)
k

Following the implementation by Ford and Sidi [4], the computation of Tk(n’k) , 06n6N , 06k6n,
requires 1 N 3 + 3 N 2 + 7 N subtractions, and 1 N 3 + 5 N 2 + 25 N +2 divisions, a total of 2 N 3 +4N 2 + 16 N +2
3 2 6 3 2 6 3 3
arithmetic operations.

Remark. (1) The Ford“Sidi algorithm requires gk+1 for computing k(n) . However, for computing
Tk(n) the Ford“Sidi algorithm does not require gk+1 . The reason is as follows: Let a1 ; : : : ; ak+1 be any
sequence such that
a1 ··· ak+1
g1 (n) · · · g1 (n + k)
= 0:
···
gk (n) · · · gk (n + k)
Let
u1 ··· uk+1 a1 ··· ak+1
g1 (n) · · · g1 (n + k) g1 (n) · · · g1 (n + k)
(n)
k (u) = :
··· ···
gk (n) · · · gk (n + k) gk (n) · · · gk (n + k)
Then by (11) we have
(n)
k (s)
Tk(n) = :
(n)
k (1)

Using the above trick, when s0 ; : : : ; sN , g1 ; : : : ; gN are given, we can determine all the Tk(n) , 06n +
k6N , by the Ford“Sidi algorithm.
N. Osada / Journal of Computational and Applied Mathematics 122 (2000) 223“230 227


(2) Moreover, neither the value of gk+1 nor sequence a1 ; : : : ; ak+1 is required in computing Tk(n) ,
when we use
(n+1) (n)
k’1 (s) ’ k’1 (s)
(n)
Tk = (n+1) ;
(n)
(1) ’ k’1 (1)
k’1

which is derived from (10) and (11). The implementation of this fact is just the e cient Ford“Sidi
algorithm described in Section 4 of this paper.


3. Mathematical equivalence of the E-algorithm and the Ford“Sidi algorithm

3.1. The Ford“Sidi algorithm is derived from the E-algorithm

Let u = (un ) be any sequence. Suppose that the sequence transformations Ek : u = (un ) ’ Ek (u) =
(n)
(Ek (u)) are deÿned by
(n)
E0 (u) = un ; (12)
(n) (n+1) (n+1) (n)
Ek’1 (u)Ek’1 (gk ) ’ Ek’1 (u)Ek’1 (gk )
(n)
Ek (u) = ; k ¿ 0: (13)
(n+1) (n)
Ek’1 (gk ) ’ Ek’1 (gk )
(n)
Suppose the sequence transformations : u = (un ) ’ k (u) =( k (u)) are deÿned by
k
(n)
Ek (u)
(n)
k (u) = (n) ; k = 0; 1; : : : : (14)
Ek (gk+1 )

(n)
Theorem 3. The quantities k (u) deÿned by (14) satisfy (9) and (10).
(n)
Proof. It follows from (12) and (14) that 0 (u) = un =g1 (n).
(n)
Using the mathematical induction on k, it can be easily proved that Ek (1) = 1. Thus, we have
1
(n)
k (1) = ; k = 0; 1; : : : : (15)
(n)
Ek (gk+1 )
By (14), we have
(n)
Ek (gj )
(n)
k (gj ) = ; k = 0; 1; : : : ; j = k + 1; k + 2; : : : : (16)
(n)
Ek (gk+1 )
From (13) and (16), we obtain
(n+1) (n)
Ek’1 (gk+1 ) Ek’1 (gk+1 )
(n+1) (n)
k’1 (gk+1 ) ’ k’1 (gk+1 ) = ’ (n)
(n+1)
Ek’1 (gk ) Ek’1 (gk )
(n) (n+1) (n+1) (n) (n) (n+1)
Ek’1 (gk+1 )Ek’1 (gk ) ’ Ek’1 (gk+1 )Ek’1 (gk ) Ek’1 (gk ) ’ Ek’1 (gk )
= (n+1) (n) (n+1) (n)
Ek’1 (gk ) ’ Ek’1 (gk ) Ek’1 (gk )Ek’1 (gk )

1 1
(n)
= Ek (gk+1 ) ’ : (17)
(n+1) (n)
Ek’1 (gk ) Ek’1 (gk )
228 N. Osada / Journal of Computational and Applied Mathematics 122 (2000) 223“230

(n)
By dividing the both sides of (13) by Ek (gk+1 ), we have
(n) (n) (n+1) (n+1)
(n)
Ek’1 (u)=Ek’1 (gk ) ’ Ek’1 (u)=Ek’1 (gk )
Ek (u)
= (n) ;
(n) (n) (n+1)
Ek (gk+1 ) Ek (gk+1 )(1=Ek’1 (gk ) ’ 1=Ek’1 (gk ))
therefore from (14) and (17), we obtain
(n+1) (n)
k’1 (u) ’ k’1 (u)
(n)
k (u) = :
(n+1) (n)
k’1 (gk+1 ) ’ (gk+1 )
k’1


We note that Brezinski and Redivo Zaglia [3] derived the relations (14) “ (16) from their deÿnitions
of Ek (u) and k(n) (u).
(n)




3.2. The E-algorithm is derived from the Ford“Sidi algorithm

Suppose that the sequence transformations k satisfy (9) and (10) for any sequence u = (un ). Let
the sequence transformations Ek be deÿned by
(n)
k (u)
(n)
Ek (u) = : (18)

<<

. 51
( 83 .)



>>