(I) GotoBALS, http://www-is.amp.i.kyoto-u.ac.jp/ kkimur/charpoly.html 2

sdmp Maple - (Ver.2) ( ) September 27, 2011 1

(I) GotoBALS, http://www-is.amp.i.kyoto-u.ac.jp/ kkimur/charpoly.html 2

(II) Nehalem CPU GotoBLAS Intel CPU Nehalem CPU, GotoBLAS, Hyper-Thread technology off 3

Windows BIOS off Mac Hyper-Thread technology off Mac OS root, terminal, nvram SMT=0 OFF 4

Maple,, 4, sdmp http://www.cecm.sfu.ca/ rpearcea/ 4,? 5

4 (1) (2) (3)Cylindrical Algebraic Decomposition Projection (4)Dixon (5), 6

Dixon f(x, y) = x 2 + y 2 3, g(x, y) = xy 1 f(x, y) g(x, y) f(α, y) g(α, y) x α = ( α 1 ) y 1 1 y 3 + 3y = 0 x 1 α 7

y = λ, v = x 1, λ 1 1 λ 3 + 3λ v = 0 λ 1 1 λ 3 + 3λ = 0, y,, 3 8

(1) (2) 1 (2+3x)(14+15x) 8 9+10x 4+5x (6+7x)(14+15x) 11+12x+13x 3 (2+3x)(16+17x) 6 + 7x (2 + 3x)(4 + 5x) 8(2 + 3x)(16 + 17x) (9 + 10x)(11 + 12x + 13x 3 ) (3) a b(4 + 5x) 8c ad(11 + 12x + 13x 3 ) a = 1 2 + 3x, b = 1 6 + 7x, c = 1 9 + 10x, d = 1 16 + 17x, 9

1., O(2 n ), 2. -,???, 3.fraction-free Gauss, O(n 3 ), 4.,???, mod 5.Berkowitz, Fadeev, O(n 4 ), 10

fraction-free Gauss n n C, ĉ ( 1) 0,0 = 1, ĉ (0) i,j = C i,j, ĉ (k) i,j = (ĉ(k 1) k,k ĉ (k 1) i,j ĉ (k 1) k,j ĉ (k 1) i,k )/ĉ (k 2) k 1,k 1 k + 1 i n, k + 1 j n, k = 1,, n 1, ĉ n,n (n 1), 0,, Jacobi,, 11

fraction-free Gauss n n C, τ 0,0 ( 1) = 1, τ i,j (0) = C i,j, τ i,j (k) = (τ k,k (k 1) τ i,j (k 1) τ k,j (k 1) τ i,k (k 1) )/τ k 1,k 1 (k 2) k + 1 i n, k + 1 j n, k = 1,, n 1, τ (n 1) n,n, 0,, Jacobi,, 12

Berkowitz (I) A = T A = A r S R a r+1,r+1 1 0 0 a r+1,r+1 1 0 RS a r+1,r+1 0...... RA r 2 r S RA r 3 r S 1 RA r 1 r S RA r 2 r S a r+1,r+1 13

Berkowitz (II) [procedure Berkowitz(A)] if dim A=1 then return [1, A 1,1 ] else r (dim A) 1 Decompose A = A r S R a r+1,r+1 Compute T A [X r+1,, X 1 ] Berkowitz(A r ) [X r+2,, X 1 ] T A [X r+1,, X 1 ] return [X r+2,, X 1 ] 14

? 1., 2. - 4., 15

Resultant( ) 1.Collins subresultant 2. 3. 16

f = a 2 x 2 + a 1 x + a 0,g = b 1 x + b 0 Sylvester res x (f, g) = a 2 a 1 a 0 b 1 b 0 0 0 b 1 b 0 m n (m + n) (m + n) 17

f = a 2 x 2 + a 1 x + a 0,g = b 1 x + b 0 Bezout res x (f, g) = b 0 b 1 b 1 a 0 b 0 a 2 b 1 a 1 m n (m > n) m m 18

1., 2. - Quantifier Elimination Q.E., Cylindrical Algebraic Decomposition C.A.D., Resultant( ) 19

a 1 a 2 a 3 a 4 b 1 b 2 b 3 b 4 c 1 c 2 c 3 c 4 d 1 d 2 d 3 d 4 = +a 1 (b 2 (c 3 d 4 d 3 c 4 ) c 2 (b 3 d 4 d 3 b 4 ) +d 2 (b 3 c 4 c 3 b 4 )) b 1 (a 2 (c 3 d 4 d 3 c 4 ) c 2 (a 3 d 4 d 3 a 4 ) + d 2 (a 3 c 4 c 3 a 4 )) +c 1 (a 2 (b 3 d 4 d 3 b 4 ) b 2 (a 3 d 4 d 3 a 4 ) +d 2 (a 3 b 4 b 3 a 4 )) d 1 (a 2 (b 3 c 4 c 3 b 4 ) b 2 (a 3 c 4 c 3 a 4 ) + c 2 (a 3 b 4 b 3 a 4 )) (bottom up),! 20

- L 1 = a 4,4 a 5,5 a 4,5 a 5,4, L 2 = a 4,3 a 5,5 a 4,5 a 5,3, L 3 = a 4,3 a 5,4 a 4,4 a 5,3, L 4 = a 4,2 a 5,5 a 4,5 a 5,2, L 5 = a 4,2 a 5,4 a 4,4 a 5,2, L 6 = a 4,2 a 5,3 a 4,3 a 5,2, L 7 = a 4,1 a 5,2 a 4,2 a 5,1, L 8 = a 4,1 a 5,5 a 4,5 a 5,1, L 9 = a 4,1 a 5,4 a 4,4 a 5,1, L 10 = a 4,1 a 5,3 a 4,3 a 5,1 det(a) = +(a 1,1 a 2,2 a 1,2 a 2,1 )(a 3,3 L 1 a 3,4 L 2 + a 3,5 L 3 ) (a 1,1 a 2,3 a 1,3 a 2,1 )(a 3,2 L 1 a 3,4 L 4 + a 3,5 L 5 ) +(a 1,1 a 2,4 a 1,4 a 2,1 )(a 3,2 L 2 a 3,3 L 4 + a 3,5 L 6 ) (a 1,1 a 2,5 a 1,5 a 2,1 )(a 3,2 L 3 a 3,3 L 5 + a 3,4 L 6 ) +(a 1,2 a 2,3 a 1,3 a 2,2 )(a 3,1 L 1 a 3,4 L 8 + a 3,5 L 9 ) (a 1,2 a 2,4 a 1,4 a 2,2 )(a 3,1 L 2 a 3,3 L 8 + a 3,5 L 10 ) +(a 1,2 a 2,5 a 1,5 a 2,2 )(a 3,1 L 3 a 3,3 L 9 + a 3,4 L 10 ) +(a 1,3 a 2,4 a 1,4 a 2,3 )(a 3,1 L 4 a 3,2 L 8 + a 3,5 L 7 ) (a 1,3 a 2,5 a 1,5 a 2,3 )(a 3,1 L 5 a 3,2 L 9 + a 3,4 L 7 ) +(a 1,4 a 2,5 a 1,5 a 2,4 )(a 3,1 L 6 a 3,2 L 10 + a 3,3 L 7 ) 21

=, Lisp Lisp Hash Hash,? 22

5 5 3 3 index, 3 4 5 1 2 4 5 2 1 4 5 3 2 3 5 4 1 3 5 5 1 2 5 6 2 3 4 7 1 3 4 8 1 2 4 9 1 2 3 10 23

w[k], index, (2 3 4), c[i][j] = i j 1 n=5; i=3; u=1; b1=n-1; for(k=i;k>0;k--){ for(b2=b1;b2>=w[k];b2--){ u=u+c[b2][k]; } b1=b2-1; } 24

geobucket,, 25

, 1 heap (sdmp ) (Singular ) (f 1 + f 2 ) (g 1 + g 2 ) = f 1 g 1 + f 1 g 2 + f 2 g 1 + f 2 g 2 26

?, f = 5x 2 y + 6x + 7y + 8 (5, [2, 1]) (6, [1, 0]) (7, [0, 1]) (8, [0, 0]) 27

(heap ) X j, Y j,, m n (X 1 + X 2 + + X m )(Y 1 + Y 2 + + Y n ) = X 1 (Y 1 + Y 2 + + Y n ) + X 2 (Y 1 + Y 2 + + Y n ) + X m (Y 1 + Y 2 + + Y n ) 28

(X 1 Y 1 + X 1 Y 2 + + X 1 Y n ) + (X 2 Y 1 + X 2 Y 2 + + X 2 Y n ) + (X m Y 1 + X m Y 2 + + X m Y n ) Y 1, Y 2,, Y n,, X j,, m 29

, =m, 1,, =1, 2, 2 root,, 2, root 2, 2,, 2, 30

sdmp, 31

heap u = ( a 1 b 1 c 1 ) v = b 2 b 3 c 2 c 3 a 2 a 3 c 2 c 3 a 2 a 3 b 2 b 3 a 1 a 2 a 3 b 1 b 2 b 3 c 1 c 2 c 3 = a 1 b 2 b 3 c 2 c 3 b 1 a 2 a 3 c 2 c 3 + c 1 a 2 a 3 b 2 b 3 = u v 32

u[1] v[1], u[2] v[2], u[3] v[3], u[1] v[1], u[2] v[2], u[3] v[3],, 1 33

sdmp Maple, http://www-is.amp.i.kyoto-u.ac.jp/ kkimur/susemi etc.html 1.sdmp 2. 1,, 34

sdmp sdmp, exponent vector 1 word (pack ) f = 5x 2 y + 6x + 7y + 8 (5, [2, 1]) (6, [1, 0]) (7, [0, 1]) (8, [0, 0]) 35

32bit, pack=2 16bit 16bit 2 1,, exponent vector 36

sdmp 1 + x 2 + 2x 2 + 2x 4 + 4x = 0,, 37

a 1 + a 2 x a 3 + a 4 x a 5 + a 6 x a 7 + a 8 x generic position ( ) 38

, O(n 2 ) 39

, Linear Assignment Problem 40

Hungarian algorithm 5 2 4 1 2 1 4 2 3,, Hungarian algorithm, O(n 3 ) bound cf. http://en.wikipedia.org/wiki/ Hungarian algorithm, maple, 41

1., 2. - http://www-is.amp.i.kyoto-u.ac.jp/ kkimur/susemi etc.html 4. http://www-is.amp.i.kyoto-u.ac.jp/ kkimur/susemi interpolation.html,, 42