• Non ci sono risultati.

Ramanujan in his first paper states that the Bernoulli numbers satisfy the following equations

N/A
N/A
Protected

Academic year: 2021

Condividi "Ramanujan in his first paper states that the Bernoulli numbers satisfy the following equations"

Copied!
13
0
0

Testo completo

(1)

Ramanujan in his first paper states that the Bernoulli numbers satisfy the following equations

 1 0 1

0 0 1

1

3

0 0 1

0

52

0 0 1

0 0 11 0 0 1

1

5

0 0

1434

0 0 1

0 4 0 0

2863

0 0 1

0 0

2045

0 0 221 0 0 1

1

7

0 0

19387

0 0

32307

0 0 1

0

112

0 0

71065

0 0

35534

0 0 1

· · · · · · · · · · · ·

 B

2

(0) B

4

(0) B

6

(0) B

8

(0) B

10

(0) B

12

(0) B

14

(0) B

16

(0) B

18

(0) B

20

(0) B

22

(0)

·

=

 1/6

−1/30 1/42 1/45

−1/132 4/455 1/120

−1/306 3/665 1/231

−1/552

·

(actually, since Ramanujan Bernoulli numbers are the moduli of ours, his equa- tions are a bit different).

Call

R

 B

2

(0) B

4

(0) B

6

(0)

.. .

=

 f

1

f

2

f

3

.. .

(RamanSyst)

such semi-infinite Ramanujan linear system. We observe that such system is equivalent to the following linear systems:

R

2!

x 4!

x2

. . .

x 2!

x2 4!

. . .

 B

2

(0) B

4

(0) B

6

(0)

.. .

=

 f

1

f

2

f

3

.. .

2!

x 4!

x2

. . .

 R ˜

x 2!

x2 4!

. . .

 B

2

(0) B

4

(0) B

6

(0)

.. .

=

 f

1

f

2

f

3

.. .

R ˜

x 2!

x2 4!

. . .

 B

2

(0) B

4

(0) B

6

(0)

.. .

=

x 2!

x2 4!

. . .

 f

1

f

2

f

3

.. .

 , ˜ R =

+∞

X

j=0

α

j

Z

j

=

+∞

X

s=0

2 x

3s

(6s + 2)!(2s + 1) Z

3s

,

α 0 = 1, α 1 = α 2 = 0, α 3 = 8!3 2 x 3 , α 4 = α 5 = 0, α 6 = 14!5 2 x 6 , α 7 = α 8 = 0, α 9 = 20!7 2 x 9 , . . . . The symbol Z denotes the semi-infinite lower shift matrix:

Z =

 0 1 0

1 0

· ·

So, the Ramanujan system is equivalent to a lower triangular Toeplitz (sparse)

linear system. Can the latter system be obtained from the lower triangular

Toeplitz (dense) even and odd linear systems introduced in toe 1n ? First let

us prepare things.

(2)

Theorem.

Let Z n−1 and Z n be the upper-left n − 1 × n − 1 and n × n submatrices of Z.

Then

n−1

X

j=0

α

j

Z

jn

B

0

(0)

x 2!

B

2

(0)

x2 4!

B

4

(0)

·

xn−1

(2(n−1))!

B

2(n−1)

(0)

=



x 2!

f

1 x2 4!

f

2

·

xn−1 (2(n−1))!

f

n−1

 +B

0

(0)

 ARB

α

1

α

2

· α

n−1



=

w

0 x 2!

w

1 x2

4!

w

2

·

xn−1 (2(n−1))!

w

n−1



if and only if

n−2

X

j=0

α

j

Z

jn−1

x 2!

B

2

(0)

x2 4!

B

4

(0)

·

xn−1

(2(n−1))!

B

2(n−1)

(0)

=

x 2!

f

1 x2 4!

f

2

·

xn−1 (2(n−1))!

f

n−1



=

x 2!

w

1 x2

4!

w

2

·

xn−1 (2(n−1))!

w

n−1

−B

0

(0)

 α

1

α

2

· α

n−1



The implication “⇐” holds if α 0 B 0 (0) =  + B 0 (0) · ARB (α 0 B 0 (0) = w 0 ).

Application of the Theorem:

We have shown that the Ramanujan system is equivalent to the system

(∗) P

n−2

j=0

α

j

Z

n−1j

x 2!

B

2

(0)

x2 4!

B

4

(0)

·

xn−1

(2(n−1))!

B

2(n−1)

(0)

=

x 2!

f

1 x2

4!

f

2

·

xn−1 (2(n−1))!

f

n−1

, α

j

= δ

j=0

mod

3 2xj (2j+2)!(23j+1)

,

f

1

=

16

, f

2

= −

301

, f

3

=

421

, f

4

=

451

, f

5

= −

1321

, f

6

=

4554

, f

7

=

1201

, f

8

=, −

3061

f

9

=

6653

, f

10

=

2311

, f

11

= −

5521

, . . .

Then, by the Theorem,

n−1

X

j=0

α

j

Z

nj

B

0

(0)

x 2!

B

2

(0)

x2 4!

B

4

(0)

·

xn−1

(2(n−1))!

B

2(n−1)

(0)

=



x 2!

f

1

x2 4!

f

2

·

xn−1 (2(n−1))!

f

n−1

 +B

0

(0)

 ARB

α

1

α

2

· α

n−1

, +B

0

(0)·ARB = α

0

B

0

(0),

(I+ 2

8!3 x

3

Z

3

+ 2

14!5 x

6

Z

6

+ 2

20!7 x

9

Z

9

+. . .)

B

0

(0)

x 2!

B

2

(0)

x2 4!

B

4

(0)

x3 6!

B

6

(0)

x4 8!

B

8

(0)

x5 10!

B

10

(0)

x6 12!

B

12

(0)

.. .

=

 1

x 2!

1 6 x2

4!

(−

301

)

x3 6!

1 42

+

2x8!33

x4 8! 1

45 x5 10!

(−

1321

)

x6 12! 4

455

+

14!52x6

x7 14!

1 120 x8 16!

(−

3061

)

x9 18!

3 665

+

20!72x9

x10 20!

1 231 x11

22!

(−

5521

) .. .

=

1 0!

(

1·11

)

x 2!

(

3·21

)

x2

4!

(

5·31

5·21

)

x3 6!

(

7·41

)

x4 8!

(

9·51

)

x5

10!

(

11·61

11·41

)

x6 12!

(

13·71

)

x7 14!

(

15·81

)

x8

16!

(

17·91

17·61

)

x9 18!

(

19·101

)

x10 20!

(

21·111

)

x11

22!

(

23·121

23·81

) .. .

 ,

+∞

X

j=0

α j Z j D x b = D x q R ,

α j = δ j=0 mod 3

2x j

(2j + 2)!( 2 3 j + 1) , q R = ( 1

(2i + 1)(i + 1) (1−δ i=2 mod 3 3

2 )), i = 0, 1, 2, 3, . . . .

(3)

Note that from the explicit expression of q R it follows an explicit expression for the f i of the Ramanujan system:

f i = 1

(2i + 1)(i + 1) (1 − δ i=2 mod 3 3

2 − δ i=0 mod 3 1

2

3 i + 1 ), i = 1, 2, 3, . . . . Note also that (*) can be rewritten as

L(α n−1 )I n 2 D x b = diag (z i , i = 1, 2, . . . , n − 1)I n 2 D x q R for suitable z i . Let us look for such z i :

(1 − δ i=2 mod 3 3

2 − δ i=0 mod 3 1

2

3

i+1 ) = z i (1 − δ i=2 mod 3 3 2 ), z i = 1 −

δ

i=0

mod

323i+11

1−δ

i=2

mod

332

= 1 − δ i=0 mod 3

23

i+1 1 .

Now let us consider the two even and odd systems introduced in toe 1n whose solution is again the vector of Bernoulli numbers:

+∞

X

j=0

x j

(2j + 2)! Z j D x b = D x q e , q e =

1 2 1 6 1 10

·

 ,

+∞

X

j=0

x j

(2j + 1)! Z j D x b = D x q o , q o =

 1

1 2 1 2

·

;

n−1

X

j=0

x j

(2j + 2)! Z n j D x b = D x q e ,

n−1

X

j=0

x j

(2j + 1)! Z n j D x b = D x q o . And apply to them the Theorem:

n−2

X

j=0

x

j

(2j + 2)! Z

n−1j

x 2!

B

2

(0)

x2 4!

B

4

(0)

·

xn−1

(2(n−1))!

B

2(n−1)

(0)

=

x 2!

1 6 x2

4!

1 10

·

xn−1 (2(n−1))! 1

4n−2

−B

0

(0)

x 4!

x2 6!

·

xn−1 (2n)!

=

 x

4!1

x

2 26!

x

3 38!

· x

n−1 n−1(2n)!

n−2

X

j=0

x

j

(2j + 1)! Z

n−1j

x 2!

B

2

(0)

x2 4!

B

4

(0)

·

xn−1

(2(n−1))!

B

2(n−1)

(0)

=

x 2!1

2 x2

4!1 2

·

xn−1 (2(n−1))!

1 2

−B

0

(0)

x 3!

x2 5!

·

xn−1 (2n−1)!

=

x

3!21

x

2 35!2

x

3 57!2

· x

n−1(2n−1)!22n−3

from which it follows

n−2

X

j=0

x

j

(2j + 2)! Z

n−1j

x 2!

B

2

(0)

x2 4!

B

4

(0)

·

xn−1

(2(n−1))!

B

2(n−1)

(0)

=

x 2!

1 4·3 x2 4!

2 6·5 x3 6! 3

8·7

·

xn−1 (2(n−1))!

n−1 2n(2n−1)

= diag ( i

i + 1 , i = 1 . . . n−1)I

n−11

(Z

nT

D

x

q

e

)

n−2

X

j=0

x

j

(2j + 1)! Z

n−1j

x 2!

B

2

(0)

x2 4!

B

4

(0)

·

xn−1

(2(n−1))!

B

2(n−1)

(0)

=

x 2!

1 2·3 x2

4! 3 2·5 x3

6! 5 2·7

·

xn−1 (2(n−1))!

2n−3 2(2n−1)

= diag ( 2i − 1

2i + 1 , i = 1 . . . n−1)I

n−11

(Z

nT

D

x

q

o

)

(4)

Set

b =

 B 0 (0) B 2 (0) B 4 (0)

.. .

, D x = diag ( x i

(2i)! , i = 0, 1, 2, . . .).

Then

L(α)D x b = D x q, L(α)Z T D x b = d(z)Z T D x q,

where the vectors α = (α i ) +∞ i=0 , q = (q i ) +∞ i=0 , and z = (z i ) +∞ i=1 , can assume respectively the values:

α R i = δ i=0 mod 3 2x

i

(2i+2)!(

23

i+1) , q R i = (2i+1)(i+1) 1 (1 − δ i=2 mod 3 3 2 ), i = 0, 1, 2, 3, . . . z i R = 1 − δ i=0 mod 3

1

2

3

i+1 , i = 1, 2, 3, . . . , α e i = (2i+2)! x

i

, q e i = 2(2i+1) 1 , i = 0, 1, 2, 3, . . .

z i e = i+1 i , i = 1, 2, 3, . . . ,

α o i = (2i+1)! x

i

, i = 0, 1, 2, 3, . . . , q 0 o = 1, q i o = 1 2 , i = 1, 2, 3, . . . z i o = 2i−1 2i+1 , i = 1, 2, 3, . . . .

( Z is the semi-infinite lower shift matrix

Z =

 0 1 0

1 0

· ·

 ,

L(α) is the semi-infinite lower triangular Toeplitz matrix with first column α, i.e.

L(α) =

+∞

X

i=0

α i Z i =

 α 0

α 1 α 0

α 2 α 1 α 0

α 3 α 2 α 1 α 0

· · · · ·

 . )

Exercise.

Try to prove that the system L(α R )D x b = D x q R (the lower triangular Toeplitz sparse system equivalent to the Ramanujan lower triangular sparse system) can be obtained as a consequence of the system L(α o )D x b = D x q o (or L(α e )D x b = D x q e ).

For example, try to find β e , β o such that L(β e )L(α e ) = L(α R ) = L(β o )L(α o ) [?? L(β e )D x q e = D x q R = L(β o )D x q o ??], i.e. L(α ee = α R = L(α oo . Find γ such that L(γ)L(α e ) = L(α) (or L(γ)L(α o ) = L(α)) with α more sparse than α R .

Exercise.

Prove that d(z)Z T L(α)(D x b) = L(α)Z T (D x b).

(5)

Note that

L(a) =

 1 a

1

1 a

2

a

1

1 a

3

a

2

a

1

1 a

4

a

3

a

2

a

1

1 a

5

a

4

a

3

a

2

a

1

1

· · · · · · ·

 1

−a

1

a

2

−a

3

a

4

−a

5

·

=

1 0 2a

2

− a

21

0 2a

4

− 2a

1

a

3

+ a

22

0

2a

6

− 2a

1

a

5

+ 2a

2

a

4

− a

23

0

2a

8

− 2a

1

a

7

+ 2a

2

a

6

− 2a

3

a

5

+ a

24

0

·

 ,

L(a)  e

1

+

+∞

X

i=1

(−1)

i

a

i

e

i+1

 = e

1

+

+∞

X

i=1

δ

i=0

mod

2

 2a

i

+

i−1

X

j=1

(−1)

j

a

j

a

i−j

 e

i+1

. If we introduce the following two semi-infinite matrices,

I ± = diag ((−1) i , i = 0, 1, 2, 3, . . .), E =

 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0

· · · · ·

 ,

then the previous equality can be rewritten as

L(a)I ± a = Ea (1) , a (1) 0 = 1, a (1) s = 2a 2s +

2s−1

X

j=1

(−1) j a j a 2s−j , s = 1, 2, 3, . . . .

Of course, L(a)L(I ± a) = L(I ± a)L(a) = L(Ea (1) ), so, for example, a lower triangular Toeplitz (l.t.T.) system of the type L(a)z = c is equivalent to the l.t.T. system L(Ea (1) )z = L(I ± a)c whose coefficient matrix has null diagonals alternating with non-null ones. We shall introduce, as a consequence of this result, an algorithm of complexity O(n(log 2 n) 2 ) for solving a lower triangular Toeplitz system (of order n = 2 k ).

Exercise. Apply the above result to the odd (even) system (the one solved by Bernoulli numbers) in order to obtain a system where null diagonals alternate with the non-null ones. Is it possible to write an explicit formula for the entries of the non-null diagonals?

Exercise. Use twice the above result in order to show that a l.t.T. system of the

type L(a)z = c is equivalent to a l.t.T. system where the coefficient matrix has

three-null diagonals alternating with non-null ones.

(6)

Exercise. Answer to the quotation marks in the following equality:

L(a) =

 1 a

1

1 a

2

a

1

1 a

3

a

2

a

1

1 a

4

a

3

a

2

a

1

1 a

5

a

4

a

3

a

2

a

1

1

· · · · · · ·

 1

?

?

?

?

?

·

=

 1 0 0

? 0 0

? 0 0

?

·

 .

As a consequence of this result,

(i) introduce an algorithm of complexity O(n(log 3 n) 2 ) for solving a lower triangular Toeplitz system (for example, in case the system has order n = 27 such algorithm is more efficient rather than embed the system in one of order n = 32 and use the algorithm ok for n = 2 k );

(ii) obtain the Ramanujan system solved by Bernoulli numbers as a conse- quence of the odd (even) system.

A lower triangular Toeplitz system solver of complexity O(n(log 2 n) 2 ) Set

n = 2

k

, a = a

(0)

=

 1 a

1

· a

n−1

=

 1 a

(0)1

· a

(0)n−1

, L(a) =

 1 a

1

1 a

2

a

1

1

· · · ·

a

n−1

· a

2

a

1

1

 ,

and let I ± and E denote the n × n upper-left submatrices of the previously defined semi-infinite matrices I ± and E. In the following we multiply L(a) on the left by suitable l.t.T matrices so to reduce the number of its non-null diagonals; we do this in k = log 2 n steps:

step 1

L(a)I ± a =: Ea (1) ,

a (1) 0 = 1, a (1) s = 2a (0) 2s + P 2s−1

j=1 (−1) j a (0) j a (0) 2s−j , s = 1, . . . , n 2 − 1, a (1) s = 0, s = n 2 , . . . , n − 1, L(a)L(I ± a) = L(I ± a)L(a) = L(Ea (1) )

Note: One here needs to compute a (1) , i.e. ( n 2 − 1 odd entries of) the vector L(a) · I ± a . Denote by ϕ n the cost (the number of multiplications) of such operation.

step 2

L(Ea (1) )EI ± a (1) =: E 2 a (2) , a (2) 0 = 1, a (2) s = 2a (1) 2s + P 2s−1

j=1 (−1) j a (1) j a (1) 2s−j , s = 1, . . . , n 4 − 1, a (2) s = 0, s = n 4 , . . . , n − 1, L(Ea (1) )L(EI ± a (1) ) = L(EI ± a (1) )L(Ea (1) ) = L(E 2 a (2) )

Note: One here needs to compute a (2) , i.e. ( n 4 − 1 odd entries of) the order n 2

non null first part of the vector L(a (1) ) · I ± a (1) . Denote by ϕ

n2

the cost of such

operation.

(7)

step 3

L(E 2 a (2) )E 2 I ± a (2) =: E 3 a (3) , a (3) 0 = 1, a (3) s = 2a (2) 2s + P 2s−1

j=1 (−1) j a (2) j a (2) 2s−j , s = 1, . . . , n 8 − 1, a (3) s = 0, s = n 8 , . . . , n − 1, L(E 2 a (2) )L(E 2 I ± a (2) ) = L(E 2 I ± a (2) )L(E 2 a (2) ) = L(E 3 a (3) )

Note: One here needs to compute a (3) , i.e. ( n 8 − 1 odd entries of) the order n 4 non null first part of the vector L(a (2) ) · I ± a (2) . Denote by ϕ

n

4

the cost of such operation.

. . .

step k − 1 = log 2 n − 1

L(E

k−2

a

(k−2)

)E

k−2

I

±

a

(k−2)

=: E

k−1

a

(k−1)

, a

(k−1)0

= 1,

a

(k−1)s

= 2a

(k−2)2s

+ P

2s−1

j=1

(−1)

j

a

(k−2)j

a

(k−2)2s−j

, s = 1, . . . ,

2k−1n

− 1, a

(k−1)s

= 0, s =

2k−1n

, . . . , n − 1,

L(E

k−2

a

(k−2)

)L(E

k−2

I

±

a

(k−2)

) = L(E

k−2

I

±

a

(k−2)

)L(E

k−2

a

(k−2)

) = L(E

k−1

a

(k−1)

) Note: One here needs to compute a (k−1) , i.e. ( 2

k−1

n − 1 odd entries of) the order

n

2

k−2

non null first part of the vector L(a (k−2) ) · I ± a (k−2) . Denote by ϕ

n

2k−2

the cost of such operation.

step k = log 2 n

L(E

k−1

a

(k−1)

)E

k−1

I

±

a

(k−1)

=: E

k

a

(k)

, a

(k)0

= 1,

a

(k)s

= 0, s =

2nk

, . . . , n − 1,

L(E

k−1

a

(k−1)

)L(E

k−1

I

±

a

(k−1)

) = L(E

k−1

I

±

a

(k−1)

)L(E

k−1

a

(k−1)

) = L(E

k

a

(k)

) (E k = e 1 e T 1 , a (k) = e 1 , L(E k a (k) ) = I)

Note: One here needs to compute a (k) , i.e. ( 2 n

k

− 1 odd entries of) the order

n

2

k−1

non null first part of the vector L(a (k−1) ) · I ± a (k−1) . Denote by ϕ

n

2k−1

the cost of such operation (ϕ

n

2k−1

= 0).

Finally note that the following equality holds

L(E

k−1

I

±

a

(k−1)

)L(E

k−2

I

±

a

(k−2)

) · · · L(E

2

I

±

a

(2)

)L(EI

±

a

(1)

)L(I

±

a ) h L(a) i

= I, in other words we have transformed L(a) into the identity matrix.

Example: n = 8

n = 2

3

, a = a

(0)

=

 1 a

1

a

2

a

3

a

4

a

5

a

6

a

7

=

 1 a

(0)1

a

(0)2

a

(0)3

a

(0)4

a

(0)5

a

(0)6

a

(0)7

, L(a) =

 1 a

1

1 a

2

a

1

1 a

3

a

2

a

1

1 a

4

a

3

a

2

a

1

1 a

5

a

4

a

3

a

2

a

1

1 a

6

a

5

a

4

a

3

a

2

a

1

1 a

7

a

6

a

5

a

4

a

3

a

2

a

1

1

 ,

and let I ± and E denote the 8 × 8 upper-left submatrices of the previously

defined semi-infinite matrices I ± and E.

(8)

step 1

L(a)I

±

a =

 1 a

1

1 a

2

a

1

1 a

3

a

2

a

1

1 a

4

a

3

a

2

a

1

1 a

5

a

4

a

3

a

2

a

1

1 a

6

a

5

a

4

a

3

a

2

a

1

1 a

7

a

6

a

5

a

4

a

3

a

2

a

1

1

 1

−a

1

a

2

−a

3

a

4

−a

5

a

6

−a

7

=: Ea

(1)

=

 1 0 a

(1)1

0 a

(1)2

0 a

(1)3

0

 ,

a

(1)0

= 1, a

(1)s

= 2a

(0)2s

+ P

2s−1

j=1

(−1)

j

a

(0)j

a

(0)2s−j

, s = 1, . . . ,

82

− 1, a

(1)s

= 0, s =

82

, . . . , 8 − 1, a

(1)1

= 2a

2

− a

21

, a

(1)2

= 2a

4

− 2a

1

a

3

+ a

22

, a

(1)3

= 2a

6

− 2a

1

a

5

+ 2a

2

a

4

− a

23

,

L(a)L(I

±

a ) = L(I

±

a )L(a) = L(Ea

(1)

)

Note: One here needs to compute a (1) , i.e. ( 8 2 − 1 odd entries of) the vector L(a) · I ± a . Denote by ϕ 8 the cost of such operation (ϕ 8 ≤ 6 if multiplications by 2 are not counted).

step 2

L(Ea

(1)

)EI

±

a

(1)

=

 1

1 a

(1)1

1

a

(1)1

1 a

(1)2

a

(1)1

1

a

(1)2

a

(1)1

1 a

(1)3

a

(1)2

a

(1)1

1

a

(1)3

a

(1)2

a

(1)1

1

 1 0

−a

(1)1

0 a

(1)2

0

−a

(1)3

0

=: E

2

a

(2)

=

 1 0 0 0 a

(2)1

0 0 0

 ,

a

(2)0

= 1, a

(2)s

= 2a

(1)2s

+ P

2s−1

j=1

(−1)

j

a

(1)j

a

(1)2s−j

, s = 1, . . . ,

84

− 1, a

(2)s

= 0, s =

84

, . . . , 8 − 1, a

(2)1

= 2a

(1)2

− (a

(1)1

)

2

,

L(Ea

(1)

)L(EI

±

a

(1)

) = L(EI

±

a

(1)

)L(Ea

(1)

) = L(E

2

a

(2)

)

Note: One here needs to compute a (2) , i.e. ( 8 4 − 1 odd entries of) the order 8 2 non null first part of the vector L(a (1) ) · I ± a (1) . Denote by ϕ

8

2

the cost of such operation (ϕ

8

2

≤ 1 if multiplications by 2 are not counted).

step 3 = log 2 8

L(E 2 a (2) )E 2 I ± a (2) =

 1

1 1

1

a (2) 1 1

a (2) 1 1

a (2) 1 1

a (2) 1 1

 1 0 0 0

−a (2) 1 0 0 0

=: E 3 a (3) =

 1 0 0 0 0 0 0 0

 ,

a (3) 0 = 1, a (3) s = 2a (2) 2s + P 2s−1

j=1 (−1) j a (2) j a (2) 2s−j , s = 1, . . . , 8 8 − 1, a (3) s = 0, s = 8 8 , . . . , 8 − 1, L(E 2 a (2) )L(E 2 I ± a (2) ) = L(E 2 I ± a (2) )L(E 2 a (2) ) = L(E 3 a (3) )

(E 3 = e 1 e T 1 , a (3) = e 1 , L(E 3 a (3) ) = I) Note: One here needs to compute a (3) , i.e. ( 8 8 − 1 odd entries of) the order 8 4 non null first part of the vector L(a (2) ) · I ± a (2) . Denote by ϕ

8

4

the cost of such operation (ϕ

8

4

= 0).

(9)

By using the obtained identities, one realizes that

L(E 2 I ± a (2) )L(EI ± a (1) )L(I ± a) L(a)  = I, i.e. we have performed a kind of Gaussian elimination . . . . Upper bounds for the cost P 1

j=k ϕ 2

j

of the computation of a (1) , a (2) , . . . , a (k−1) , a (k) Since the cost of a matrix-vector product involving a generic vector and a 2 j × 2 j lower triangular Toeplitz matrix with ones on the diagonal is obviously bounded by 1 + 2 + 3 + . . . + (2 j − 1) = 1 2 2 j (2 j − 1), we can say that

k

X

j=1

ϕ

2j

≤ 1 2

k

X

j=1

(2

2j

− 2

j

) = 2

3 (2

k

)

2

− 2

k

+ 1 3 .

However, by exploiting the particularity of our matrix-vector products, we observe that ϕ 2 = 0, ϕ 4 ≤ 1, ϕ 8 ≤ 3 + 1 + 2, ϕ 16 ≤ 7 + 1 + 2 + 3 + 4 + 5 + 6, ϕ 2

j

1 2 2 j−1 (2 j−1 − 1). So,

k

X

j=1

ϕ

2j

≤ 1 2

k

X

j=2

(2

2j−2

− 2

j−1

) = 1

6 (2

k

)

2

− 1 2 2

k

+ 1

3 .

Finally, since a matrix-vector product involving a generic vector and a 2 j × 2 j lower triangular Toeplitz matrix can be computed by means of the three FFT of order 2 j+1 , i.e. with a cost O((j + 1)2 j+1 ), we have

k

X

j=1

ϕ

2j

= O(k

2

2

k

) = O(n(log

2

n)

2

) prove this!

Computing the first column of L(a) −1 Now observe that

L(E

k−1

I

±

a

(k−1)

)L(E

k−2

I

±

a

(k−2)

) · · · L(E

2

I

±

a

(2)

)L(EI

±

a

(1)

)L(I

±

a ) h L(a) i

= I, L(a)z = c,

z = L(E

k−1

I

±

a

(k−1)

)L(E

k−2

I

±

a

(k−2)

) · · · L(E

2

I

±

a

(2)

)L(EI

±

a

(1)

)L(I

±

a ) c

= L(I

±

a )L(EI

±

a

(1)

)L(E

2

I

±

a

(2)

) · · · L(E

k−2

I

±

a

(k−2)

)L(E

k−1

I

±

a

(k−1)

) c, L(a)z = ue

1

+ ve

n

2+1

,

z = L(I

±

a )L(EI

±

a

(1)

)L(E

2

I

±

a

(2)

) · · · L(E

k−2

I

±

a

(k−2)

)L(E

k−1

I

±

a

(k−1)

) (ue

1

+ ve

n

2+1

)

= L(I

±

a )EL(I

±

a

(1)

)EL(I

±

a

(2)

) · · · EL(I

±

a

(k−2)

)EL(I

±

a

(k−1)

) (ue

1

+ ve

2

).

The latter identity, whose proof is left to the reader, implies that the solution of the system L(a)z = ue 1 + ve

n2

+1 (the first column of L(a) −1 , if u = 1, v = 0) can be computed by performing k = log 2 n l.t.T.matrix-vector products where the matrices are, respectively, 2 × 2 (no operation, if u = 1, v = 0), 4 × 4 (one multiplication, if u = 1, v = 0), 8 × 8, . . ., 2 k × 2 k , i.e. 2 j × 2 j , j = 1, 2, . . . , k.

If we perform such products by means of FFT (as soon as j becomes so large

that using FFT is cheaper than the economized direct product), then the total

amount of operations is O(n(log 2 n) 2 ) (prove it!).

(10)

Example: n = 8 = 2 3 , k = 3

 z

0

z

1

z

2

z

3

z

4

z

5

z

6

z

7

 :=

 1

−a

1

1 a

2

−a

1

1

−a

3

a

2

−a

1

1 a

4

−a

3

a

2

−a

1

1

−a

5

a

4

−a

3

a

2

−a

1

1 a

6

−a

5

a

4

−a

3

a

2

−a

1

1

−a

7

a

6

−a

5

a

4

−a

3

a

2

−a

1

1

 1

1

−a

(1)1

1

−a

(1)1

1 a

(1)2

−a

(1)1

1

a

(1)2

−a

(1)1

1

−a

(1)3

a

(1)2

−a

(1)1

1

−a

(1)3

a

(1)2

−a

(1)1

1

 1

1 1

1

−a

(2)1

1

−a

(2)1

1

−a

(2)1

1

−a

(2)1

1

 u 0 0 0 v 0 0 0

=

 1

−a

1

1 a

2

−a

1

1

−a

3

a

2

−a

1

1 a

4

−a

3

a

2

−a

1

1

−a

5

a

4

−a

3

a

2

−a

1

1 a

6

−a

5

a

4

−a

3

a

2

−a

1

1

−a

7

a

6

−a

5

a

4

−a

3

a

2

−a

1

1

 1 0

0 1 0

0 1 0

0 1 0

0 0 0 0

 1

−a

(1)1

1 a

(1)2

−a

(1)1

1

−a

(1)3

a

(1)2

−a

(1)1

1 0

0 0

0

 1 0

0 1 0

0 1 0

0 1 0

0 0 0 0

 1

−a

(2)1

1 0

0 0

0 0

0

 u v 0 0 0 0 0 0

is such that

 1 a

1

1 a

2

a

1

1 a

3

a

2

a

1

1 a

4

a

3

a

2

a

1

1 a

5

a

4

a

3

a

2

a

1

1 a

6

a

5

a

4

a

3

a

2

a

1

1 a

7

a

6

a

5

a

4

a

3

a

2

a

1

1

 z

0

z

1

z

2

z

3

z

4

z

5

z

6

z

7

=

 u 0 0 0 v 0 0 0

.

Riferimenti

Documenti correlati

It remains to show that the partition exists when n is multiple of 8 and n ≥ 16.. For any non-negative integer x, we have a partition of {1

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

Since we are comparing two polynomials, it follows that the identity holds for all x

[r]

Thus c stays inside D and since it reaches the maximal distance from the boundary, it belongs to

[r]

Landy, A generalization of Ceva’s theorem to higher

Some topics on modular functions, elliptic functions and transcendence theory. Sheet of