5 / / $\mathrm{p}$ $\mathrm{r}$ 8 7 double 4 22 / [10][14][15] 23 P double 1 $\mathrm{m}\mathrm{p}\mathrm{f}\mathrm{u}\mathrm{n}/\mathrm{a

Size: px

Start display at page:

Download "5 / / $\mathrm{p}$ $\mathrm{r}$ 8 7 double 4 22 / [10][14][15] 23 P double 1 $\mathrm{m}\mathrm{p}\mathrm{f}\mathrm{u}\mathrm{n}/\mathrm{a"

しゅんすけいなくら
5 years ago
Views:

1 double $\mathrm{j}\mathrm{s}\mathrm{t}$ $\mathrm{q}$ / (Kinji Kimura) Japan Science and Technology Agency Faculty of Science Rikkyo University 1 / / Kronecker $\mathrm{p}$ 1 double 2 $\mathrm{p}$ $\mathrm{r}$ 3 4 $\mathrm{q}$ $\mathrm{r}$

2 5 / / $\mathrm{p}$ $\mathrm{r}$ 8 7 double 4 22 / [10][14][15] 23 P double 1 $\mathrm{m}\mathrm{p}\mathrm{f}\mathrm{u}\mathrm{n}/\mathrm{a}\mathrm{r}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{c}$ 2 Omni OpenMP Compiler Project(GMP) $D$ 2 $n\cross n$ $X$ 3 $X$ $\mathrm{y}$ $X$ $Z$ 4 $B=\mathrm{Y}D\mathrm{Y}^{T}$ $C=XDZ$ 5 $B$ $C$ double $B $ $C $ 4 5

3 $D$ 2 Jacobi $D$ /2 Lanczos 3 [16] Lanczos [8] 2 Golub-Kahan-Lanczos [4] Jacobi $D$ $0$ Helmholtz 5 2 Poisson (I) [17] $A=$ $x^{[j)}$ $\lambda_{j}$ $\lambda_{j}=b+2\sqrt{ac}\cos\frac{j\pi}{n+1}$ $(1 \leq j\leq n)$ $x^{(j)}=[ \sin\frac{j\pi}{n+1}$ $\sqrt{\frac{a}{c}}\sin\frac{2j\pi}{n+1}$ $\cdots$ $( \rho_{\frac{a}{c}}^{n-1}\sin\frac{nj\pi}{n+1}]^{\mathrm{t}}$

4 $\overline{a}_{n}$ Helmholtz Poisson 5 3 [5] 3 $\check{\tau}$ $A$ $=$ 42 3 (II) [16] $=$ $\tilde{a}_{n}$ $\Gamma_{n}(\lambda)$ $\Gamma_{n}(\lambda)=(2-\lambda)\Gamma_{n-1}(\lambda)-\Gamma_{n-2}(\lambda)$ $\lambda_{j}=4\sin^{2}(\frac{2j-1}{2(2n+1)}\pi)$ $j=12$ $\ldots$ $x^{(j)}$ $=$ $[ \sin(\frac{n(2j-1)}{2n+1}\pi)$ $\sin(\frac{(n-1)(2j-1)}{2n+1}\pi)$ $\cdots$ $\sin(\frac{2j-1}{2n+1}\pi)]^{\mathrm{t}}$

5 $L^{\mathrm{T}}$ (I) $A$ $A=$ $LL^{\mathrm{T}}=$ $L^{\mathrm{T}}$ $\sigma_{j}$ $=$ $2 \sin(\frac{j\pi}{2(n+1)})$ $x^{(j)}=[ \sin\frac{j\pi}{n+1}$ $\sin\frac{2j\pi}{n+1}$ $\cdots$ $\sin\frac{nj\pi}{n+1}]^{\mathrm{t}}j=12$ $\ldots$ 431 $L^{-\mathrm{T}}$ $=$ $k^{\gamma}x\text{ }$ $L^{-\mathrm{T}}$ g Eg $\sigma_{j}$ $=$ $\frac{1}{2\sin(\frac{j\pi}{2(n+1)})}$ $x^{(j)}=[ \sin\frac{j\pi}{n+1}$ $\sin\frac{2j\pi}{n+1}$ $\cdots$ $\sin\frac{nj\pi}{n+1}]^{\mathrm{t}}j=12$ $\ldots$ 44 2 (II) $\tilde{a}_{n}$ $\tilde{a}_{n}$ $=$ $\tilde{l}\tilde{l}^{\mathrm{t}}=$ 1 $-11$ $-11$ $::$ : $-11)$

6 $\tilde{l}^{\mathrm{t}}$ Gregory Karney $\tilde{l}^{-\mathrm{t}}$ 6 $\tilde{l}^{t}$ $\sigma_{j}=2\sin(\frac{2j-1}{2(2n+1)}\pi)$ $j=12$ $\ldots$ $x^{(j)}$ $=$ $[ \sin(\frac{n(2j-1)}{2n+1}\pi)$ $\sin(\frac{(n-1)(2j-1)}{2n+1}\pi)$ $\cdot$ $\sin(\frac{2j-1}{2n+1}\pi)]^{\mathrm{t}}$ 441 $=$ $\tilde{l}^{-\mathrm{t}}$ $\sigma_{j}=\frac{1}{2\sin(\frac{2j-1}{\mathit{2}(2n+1)}\pi)}$ $j=12$ $\ldots$ $x^{(j)}=[ \sin(\frac{n(2j-1)}{2n+1}\pi)$ $\sin(\frac{(n-1)(2j-1)}{2n+1}\pi)$ $\cdots$ $\sin(\frac{2j-1}{2n+1}\pi)]^{\mathrm{t}}$ 45 $\mathrm{t}$ $\mathrm{l}$ Robert David Collection of Matrices for Testing Computational Algorithms Interscience (1969) 5 1 $f(x)=x^{n}+a_{n-1}x^{n-1}+\cdots+a_{0}$

7 7 $C_{n}$ $o_{n}$ $=$ $(0^{:}001$ $:::$ $0001:$ $=_{a_{n}}^{a_{n}}\cdot=_{1}^{2}=_{a_{1}}^{a_{0}} )$ $::$ : $\tilde{a}_{n}c_{n}(\tilde{a}_{n})^{-1}$ $D$ $\tilde{a}_{n}d(\tilde{a}_{n})^{-\mathit{1}}$ 6 Kronecker 61 $m$ $A$ $B$ Kronecker $A\otimes B$ $mn$ $A$ $\lambda_{m}$ $B$ $\lambda_{1}$ $\ldots$ $\mu_{1}$ $\mu_{n}$ $A\otimes B$ $\lambda_{i}\mu_{j}(i=1 \ldots m:j=1 \ldots n)$ $\ldots$ $m$ $A$ $v_{1}$ $v_{m}$ $A$ $\ldots$ $w_{1}$ $w_{n}$ $\ldots$ Kronecker $A\otimes B$ $v_{i}\otimes w_{j}(i=1 \ldots m:j=1 \ldots n)$ $(A\otimes B)\cross(v:\otimes w_{j})=(a\cross v_{\mathrm{t}})\otimes(b\cross w_{j})=(\lambda_{i}v_{i})\otimes(\mu_{j}w_{j})=(\lambda_{1}\mu_{j})(v_{1}\otimes w_{j})$ $(A\mathrm{x}v_{i})\otimes(B\cross w_{j})=(\lambda_{i}v_{i})\otimes(\mu_{j}w_{j})$ $A\otimes B$ $A^{-1}\otimes B^{-1}$ $\cross$ [9] 62 Kronecker $\otimes$ $U=$ $V=$ $W=U\otimes V=(_{gj}^{aj}$ $djaldlgl$ $amdmgmdkgkakhjejbjhlelbl$ $hmembmhkekbkfjcjflijclil$ $fmcmimfkckik$ ) $W$ $U$ 1 $V$ $f(x)=\det(u-xi)$ $=$ $-x^{3}+(a+e+i)x^{2}+(-ea-ia+db+gc-ie+hf)x$ $+(ie-hf)a+(gf-id)b+(hd-ge)c$ $g(x)=\det(v-xi)$ $=$ $x^{2}+(-j-m)x+mj-lk$

8 8 2 $h(x y)= \mathrm{n}\mathrm{u}\mathrm{m}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{r}(g(\frac{x}{y}))$ 3 $W$ $\det(w-xi)=\mathrm{r}\mathrm{e}\mathrm{s}_{y}(f(y) h(x y))$ or $-\mathrm{r}\mathrm{e}\mathrm{s}_{y}(f(y) h(x y))$ $\mathrm{r}\mathrm{e}\mathrm{s}_{y}(f(y) h(x y))$ $\mathrm{r}\mathrm{e}\mathrm{s}_{y}$ $y$ 7 71 Ax=v Hensel [2] ( ) $x=x_{0}+px_{1}+p^{\mathit{2}}x_{2}+\cdots$ $P$ $A(x_{0}+px_{1}+p^{2}x_{2}+\cdots)=v$ mod $p^{\alpha}$ $A$ $\mathrm{m}\mathrm{o}\mathrm{d} p$ $\mathrm{l}\mathrm{u}$ $Ax_{0}$ $=v$ mod $p$ $Ax_{1}$ $=$ $\frac{v-ax_{0}}{p}$ mod $p$ $Ax_{2}$ $=$ $(v-ax_{0})/p-ax_{1}$ $p$ mod $p$ $P$ 72 $n\cross n$ $A$ $\det(a)$ [11] $A=$ ( $a_{n1}a_{11}:$ $::$ : $a_{\mathrm{n}n}a_{1n}:$ )

9 9 $u_{1}=(a_{11} \ldots a_{1n})$ $\ldots$ $u_{n}=(a_{n1} \ldots a_{nn})$ $v_{1}=(a_{11} \ldots a_{n1})$ $\ldots$ $v_{n}=(a_{1n} \ldots a_{nn})$ Hadamard $\leq$ $\det(a)$ $\min( u_{1} _{\mathit{2}} u_{2} _{2}\ldots u_{n-1} _{2} u_{n} _{2} v_{1} _{2} v_{2} _{2}\ldots v_{n-1} _{\mathit{2}} v_{n} _{2})\equiv H$ 73 1 Hadamard $H_{1}$ $\leq H_{1}$ [3] 731 : Hadamard $H_{2}$ $H_{2}$ I $H_{2}$ $\mathbb{z}/p\mathbb{z}$ Hessenberg Hessenberg pivot $a(k k)$ $\alpha=\frac{a(ik)}{a(kk)}$ $a(ij)arrow a(ij)-\alpha a(kj)$ $j=k+1$ $\ldots$

10 10 $a(m k)arrow a(m k)+\alpha a(m i)$ $m=1$ $\ldots$ $\mathbb{z}/p\mathbb{z}$ Hessenberg \theta ] $[-$ $\text{ ^{}p_{i}}\preceq \mathit{2}$ $\mathrm{l}_{\frac{p_{i}-1}{2}}]$ $H_{2}$ [7] Danilevsky $\mathbb{z}/p\mathbb{z}$ [8] 742 II $-$ I GMRES $v$ $A^{k}v$ $\mathbb{z}/p\mathbb{z}$ $(v Av \cdots A^{n-1}v)=-A^{n}v$ $c_{n-1}$ $\cdots$ $\mathrm{c}_{0}$ Hensel $0$ $[-^{\mathrm{l}^{-\underline{1}}e}2 \frac{-1}{2}]$ $0$ $j$ Strum 2 3 Uspensky

11 $\bullet$ $\bullet$ $f_{j}(x)$ $\bullet$ $j=12$ [1] Pdearson [13] 8 1 Strum Strum [11] $f(x)$ $f (x)$ $f(x)$ 1 real root finding [12] 822 $f(x)$ $f_{1}(x)$ $f_{2}(x)_{)}\ldots$ $f_{k}(x)$ 1 $f1(x)=f(x)/\mathrm{g}\mathrm{c}\mathrm{d}(f(x) f (x))$ 2 $f_{j}(x)$ $f_{j}(x)$ 1 $f_{\mathrm{j}+1}(x)=f_{j} (x)/\mathrm{g}\mathrm{c}\mathrm{d}(f_{j} (x) f_{j} (x))$ 3 $f_{j+1}(x)$ 1 $f_{j}(x)$ $f1(x)$ $f(x)$ $f_{j+1}(x)$ $\beta$ $\ldots$ $k-1$ $\alpha$ $f_{j+1}(x)$ $f_{j}(x)$ $(\alpha\beta)$ 1 $f_{j}(x)$ $f_{j}(\alpha)$ $f_{j}(\beta)$ [12]

12 12 83 Uspensky (Descarte ) $f(x)=a_{0}x^{n}+a_{1}x^{n-1}+\cdots+a_{n}$ $a_{0}$ $a_{1}$ $\cdots$ $a_{n}$ ( ) $0$ $W$ $f(x)$ ( ) $0$ $W$ $W$ $0$ $W$ 1 1 $W$ 2 $xarrow 1/(x+1)$ $x$ $(0 \infty)$ $(01)$ $xarrow x+1$ $x$ $(0 \infty)$ $(1 \infty)$ $x=1$ $xarrow x+1$ check $0$ 1 $x=10^{ }$ 831 $x^{n}+a_{1}x^{n-1}+\cdots+a_{n}=0$ $a_{\alpha}$ $\cdots$ $a_{\beta}$ $a_{\gamma}$ $G_{4}=2 \max[( a_{\alpha} )^{1/\alpha} ( a_{\beta} )^{1/\beta} ( a_{\gamma} )^{1/\gamma} \cdots]$ [6] $xarrow 1/x$ $x=10^{100\mathfrak{x}000}$ 9 $8\mathrm{G}\mathrm{H}\mathrm{z}$ $2\mathrm{G}\mathrm{B}\mathrm{y}\mathrm{t}\mathrm{e}$ Intel Xeon 2 Memory $1000\cross 1000$ 1 10 II I Uspensky

13 13 [1] GECollins and Alkiviadis GAkritas Polynomial Real Root Isolation Using Decarte s Rule of Signs Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation [2] K O Geddes Stephen R Czapor George Labahn Keith O Geddes S R Czapor G Labahn Algorithms for Computer Algebra Kluwer Academic Pub United States (1992) [3] AJ Goldstein RL Graham A Hadamard-type bound on the coefficient of a determinant of polynomials SIAM Review (1974) [4] G Golub W Kahan Calculating the singular values and pseude-inverse of a matrix SIAM J Numeri Anal Vol 2 pp (1965) [5] E Ishiwata Y Muroya K Isogai Adaptive improved block SOR method with orderings JJIAM vol16 No3 pp (1999) [6] JRJohnson Algorithms for Polynomial Real Root Isolation Quantifier Elimination and Cylindrical Algebraic Decomposition SpringerWienNewYork Austria (1998) [7] S Lo M Monagan A Wittkopf A Modular Algorithm for Computing the Characteristic Polynomial of an Integer Matrix in Maple $//\mathrm{w}\mathrm{w}\mathrm{w}$ http: cecm pdf $\mathrm{s}\mathrm{f}\mathrm{u}\mathrm{c}\mathrm{a}/\mathrm{c}\mathrm{a}\mathrm{g}/\mathrm{p}\mathrm{a}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{s}/\mathrm{c}\mathrm{p}\mathrm{p}\mathrm{a}\mathrm{p}\mathrm{e}\mathrm{r}$ [8] (I) 1997 [9] 2003 [10] 2000 [11] ( ) 1965 [12] 2003 [13] 2003 [14] 15(3) pp (2005) [15] 18 [16] [17] [ 2003