Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org

Abstract

.. 2,

-

∗ αi = αiT = BT AiB, < Q1, Q2 >= Q1T AQ2

P(s)(x), ßαi Q(s+1)(x) = xQ(s)(x) + Q(s)(x)ν0 + Q(s−1)(x)ν1, P(s+1)(x) = xP(s)(x) + P(s)(x)ν0 + P(s−1)(x)ν1, R(s+1)(x) = xR(s)(x) + R(s)(x)ν0 + R(s−1)(x)ν1,

Q(s+t)(x) = Q(s)(x)H1(ts)(x) + Q(s−1)(x)H0(ts)(x), ρ(ss++k1+)1 = ρ(ss+)k+2 + ρ(ss+)k+1ν0 + ρ(ss+−k1+)1ν1.

Q(s+1)(x) Q(s+1)(x) = Q(s)(x) (Ix + ν0) + Q(s−1)(x)ν1.

ρ(ss+)1 + ρ(ss−1)ν1 = ρ(s+1) = 0,

s ρ(ss+)2 + ρ(ss+)1ν0 + ρ(ss+−11)ν1 = ρ(ss++11) = 0.

Q(s+t)(x)

H1(s+1)(x) = H1(s)(x) (Ix + ν0) + H1(s−1)(x)ν1 H0(s+1)(x) = H0(s)(x) (Ix + ν0) + H0(s−1)(x)ν1,    

0 0 H1(s) =  H1(·s(0·)s−·1)  , H0(s) =  · 00··  .

 HHH1(·s(·)11s((ss−01·))2)   HHH0(·s(·)00s((ss−01·))2)   

⋆  (s⋆)   ρ2 Kn −s   R(s) =  · · ·  ,    ρ(ss+)1    · 0··   0   0 Ik 0 · · · 0   0 0 Ik · · · 0  Z =  · · · · · · · · · · · · · · ·  .

 0 0 0 · · · Ik   0 0 0 · · · 0 

Z ∈ Fn×n

R(s+1) =  

I ZT R(s) R(s) R(s−1)  ν0      ν1 

R(s).

R(s+1) s s−1 Qs+1 = X AiQ1H1(si+1) + X AiQ0H0(si+1),

i=0 i=0 Qs+1 = K0H0(s+1) + K1H1(s+1).

Kn −1 X Kn = X Qi QiT AQi −1 QiT B.

i=0

Zi = QiT AQi −1 QiT B,

Kn −1 Kn −1 X Kn = X QiZi = X i=0 i=0

K0H0(i) + K1H1(i) Zi

Kn −1 X Kn = X QiZi.

i=0  Kn −1   Kn −1  = K0  X H0(i)Zi + K1  X H1(i)Zi .

i=0 i=0 A Kn −1Q0 A Kn −2Q0 · · · AQ0 Q0

s G(0s) = X H0(i)Zi = G(0s−1) + H0(s)Zs; i=0 s G(1s) = X H1(i)Zi = G(1s−1) + H1(s)Zs,

i=0 X Kn = K0G(0Kn −1) + K1G(1Kn −1). X Kn QiT B

QiT AQi

QiT AQi

1 QiT B = X νjT QiT−j−1B = ν0QiT−1B + ν1QiT−2B.

j=0

QiT AQi = Q(i) T ρi(+i)1

i Q0 = B;

Q1 = AB − Bα1−1α2; Z0 = α0−1ψ0 = (Q0T AQ0)−1ψ0, Z1 = (Q1T AQ1)−1ψ1; K×K

Zs, QsT AQs ψs = ν0T ψs−1 + ν1T ψs−2 G(1) = H0(0)Z0;

0 G(1) = H1(1)Z1;

1  (s−1)     (s) 

0 ρs ν0 ρs+1     = −   .  (s) (s−1)     (s)  ρs+1 ρs+1 ν1 ρs+2 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Hi(s) = ZHi(s−1) + Hi(s−1)ν0 + Hi(s−2)ν1, (i = 0, 1);

R(s) = ZT R(s) + R(s)ν0 + R(s−1)ν1; G(s) = G(s−1) + H0(s)Zs, G(s) = G(s−1) + H1(s)Zs.

0 0 1 1 X Kn = K0G(0Kn −1) + AK0G(1Kn −1) − K0Gˆ(1Kn −1),

R(s) K × K 2 n −1

K 2.9. ˛ ª Ł ) ˜

Z

R(s+1) = ZT R(s) + R(s)ν0 + R(s−1)ν1,

R(s) li ŁŁABGi,

G( Kn −1) 0 3. Gutkne ht M.H. A ompleted theory of the unsymmetri Lan zos pro ess and related algorithms. Part I. // SIAM J. Matrix Anal. Appl. 1992. Vol. 13. N. 2. P. 594 639. 1. Lan zos C. An iteration method for the solution of the eigenvalue problem of linear di erential and integral operators // J. Res. Nat. Bur. Standards. 1950. Vol. 45, P. 255 282. 10. . . . Version of blo k Lan zos-type algorithm for solving sparse linear systems. http://rms.unibu .ro/bulletin.

Bull.Math.So .S i.Math.Roumanie, V.53(101), N.3, 2010, p.225-230, Ł ª tae - º t 1 ƺ ŒŁ X˜ti t-ßØ º Universal block Lanczos-Pade method for linear systems over large finite fields Nikolay Zamarashkin and Mihail Cherepnev In this paper we propose a universal algorithm designed for solving large sparse linear systems over finite fields with large prime number of elements. Such systems arise in the solution of the discrete logarithm problem modulo a prime number. Parallel algorithms and effective data distributions are proposed.

References