数理解析研究所講究録
第 1785 巻 2012 年 123-130123

拡張行列ホーナー法と行列スペクトル分解の並列算法
小原功任

田島 慎一

KATSUYOSHI OHARA

金沢大学理工1SHINICHI TAJIMA

筑波大学数理物質 \dag er\star

行列スペクトル分解
正方行列 $A$ の固有値を$\lambda_{1},$$\cdots,$$\lambda_{m}$とし，固有値いるように、 このとき互いに可換な行列$P_{1},$$\cdots$,$\lambda_{i}$$P_{m},$に関する不変部分空間を$D$$V_{i}$とする。 よく知られてが存在して$E=P_{1}+\cdots+P_{m}$ ,$A=\lambda_{1}P_{1}+\cdots+\lambda_{m}P_{m}+D$$P_{i}$$D$となる。 この,は鷲への射影行列，は巾零行列，$\{P_{1}, \cdot\cdot\cdot , P_{m};D\}$を行列 $A$ のスペクトル分解という。

本研究の目的は、 $Q$ 上の行列のスペクトル分解をできるだけ高速に exact に計算することである。 そのために、数学的にはレゾルベントに関する留数解析を、 計算技術としては並列計算の手法を用いる。 また、$D$ は固有値上の行列のスペクトル分解であるから、 一般に行列の多項式または有理式を成分と$Q$$P_{i},$$\lambda_{i}$する。 このときに冗長な表現で求めてしまうと、スペクトル分解した後に、 simplification の手間を要する。

したがって本研究では最小次数の多項式を成分ととるようにした。本稿でははじめにこれまでの研究を概観してスペクトル分解アルゴリズムについて説明し、 その後に今回工夫を行った拡張行列ホーナー法について述べる。 また、 われわれのアルゴリズムは計算代数システム $Risa/Asir$ に実装しているが、 そのタイミングデータについても述べる。

2レゾルベントと射影行列

定義 1. 正方行列 $A$ に対して、 行列値複素関数 $R(z)=(zE-A)^{-1}$ を $A$ のレゾルベントという。

簡単に分かるように、 レゾルベント $R(z)$ は $C$ 上の行列値有理関数となる。 また $R(z)$ の極はの特性多項式 $\chi(z)=\det(zE-A)$ の根、 すなわち固有値である。 レゾルベントについては次の定理がよく知られ$A$ている。

*ohara@air.s.kanazawa-u.ac.jp’tajima@math.tsukuba.ac.jp

124
定理 1. $A$ の固有値を$\lambda_{1},$$\cdots,$$\lambda_{m}$とする。

におけるローラン展開$\lambda_{i}$$R(z)= \cdots+\frac{1}{(z-\lambda_{i})^{2}}D_{i}+\frac{1}{z-\lambda_{i}}P_{i}+\cdots$

は、 $A$ のスペクトル分解$\{P_{1} , \cdot\cdot\cdot, P_{m};\sum_{i=1}^{m}D_{i}\}$を与える。

したがってスペクトル分解を求めるには、 $R(z)$ の固有値のまわりでのローラン展開について調べればよいことになる。特に、 コーシーの積分定理から次がしたがう。
定理 2. 固有値
影行列

$P_{i}l\ovalbox{\tt\small REJECT}$、$z=\lambda_{i}$のまわりを反時計回りに一周まわる閉曲線を周回積分$P_{i}= \frac{1}{2\pi\sqrt{-1}}\int_{C_{i}}R(z)dz$$C_{i}$

によって与えられるとする。 このとき、$\lambda_{i}$に対する射$\circ$

また、 レゾルベントの有理関数としての構造については次の定理が得られる。

定理 3. 多項式 $f(z)\in C[z]\backslash \{0\}$ が $f(A)=O$ を満たせば、 レ ノ ルベントは$\grave$$\grave$$R(z)= \frac{1}{f(z)}\Psi_{f}(zE, A)$,

ただし$\Psi_{j}(x, y)=\frac{f(x)-f(y)}{x-y}\in C[x, y]$.と表される。

例 1. 行列$A=(\begin{array}{lll}0 4 0-l 4 00 0 3\end{array})$の最小多項式は $\pi(x)=(x-2)^{2}(x-3)$ であり、 固有値は$\lambda_{1}=2,$$\lambda_{2}=3$である。 このとき、 $A$ のレゾルベントは$R(z)= \frac{1}{(z-2)^{2}}(-6E+5A-A^{2})+\frac{1}{z-2}(-3E+4A-A^{2})+\frac{1}{z-3}(4E-4A+A^{2})$と書かれ、 その係数行列$P_{1}=-3E+4A-A^{2}=(\begin{array}{lll}l 0 00 l 00 0 0\end{array})$$D_{1}=-6E+5A-A^{2}=(\begin{array}{lll}-2 4 0-1 2 00 0 0\end{array})$,$P_{2}=4E-4A+A^{2}=(\begin{array}{lll}0 0 00 0 O0 0 l\end{array})$,,$D_{2}=O$

は $A$ のスペクトル分解 $\{P_{1}, P_{2};D_{1}+D_{2}\}$ を与える。

例 2. 行列$A=(\begin{array}{llll}0 2 0 ll 0 0 00 0 0 20 0 l 0\end{array})$の最小多項式は $\pi(x)=(x^{2}-2)^{2}$ であり、 固有値は$\lambda_{1}=\sqrt{2},$$\lambda_{2}=-\sqrt{2}$である。 このとき、 $A$ のスペク

トル分解 $\{P_{1}, P_{2;}D_{1}+D_{2}\}$ は$P_{i}=(\begin{array}{llll}\frac{1}{2} \frac{\lambda}{2} 0 \lambda\vec{8}\frac{\lambda}{4} \frac{1}{2} -\lambda 00 0 \frac{1}{2} \frac{\lambda}{2}0 0 arrow\lambda 4 \frac{1}{2}\end{array})$で与えられる。

$D_{i}=(\begin{array}{llll}0 0 \lambda\vec{8} \frac{1}{4}0 0 \frac{1}{8} \underline{\lambda}_{\Delta}80 0 0 00 0 0 0\end{array})$$(i=1,2)$

125
3

レゾルベントの留数解析とネーター作用素
定理 3 より行列 $A$ を消去する多項式があれば、 レゾルベントを具体的に書き下すことができるが、 計算量的観点からは、 次数が小さな多項式を選ぶべきである。 したがってレゾルベントは最小多項式 $\pi(z)$ を用と表されることになる。 さらに、 定理 2 より、 レゾルベントの周回積分で射影行列は表されるので、 最小多項式で表されたレゾルベントにっいて、 周回積分を exact に求めることができれば、 射影行列の計算はできることになる。 そのために代数的局所コホモロジー群とネーター作用素のいて $R(z)= \frac{1}{\pi(z)}\Psi_{\pi}(zE, A)$概念を導入する。
$f(z)\in Q[z]$ を既約多項式とする。集合 $V(f)=\{z|f(z)=0\}$ に特異点をもつ有理関数の全体 $Q[z, f^{-1}]$に同値関係$\equiv$を次のように入れる。

$r_{1}(z)\equiv r_{2}(z)\Leftrightarrow r_{1}(z)-r_{2}(z)\in Q[z]$この同値類を$[r_{1}]$で表し、 $V(f)$ に台をもっ代数的局所コホモロジー類という。 また，この同値類の全体を$V(f)$ に台をもつ代数的局所コホモロジー群という。 このとき、 与えられた有理関数 $g(z)/f(z)^{p}\in Q[z, f^{-1}]$に対して，次の多項式係数 $l-1$ 階微分作用素$[ \frac{g(z)}{f(z)^{\ell}}]=T[\frac{f’(z)}{f(z)}]$,$T$を計算することができる ([3], [4])。

$\partial_{z})\ell-1$ .

$T= \sum_{k=0}(-\partial_{z})^{\ell-k}t_{k}(z)\in Q\{z,$

この $T$ をネーター作用素という。 より一般には、 $V(fi\cdots f_{m})$えることができ、 有理関数

$r(z)\in Q[z, f_{1}^{-1}, \cdots, f_{\overline{m}}^{1}]$に台をもつ代数的局所コホモロジー群を考の代数的局所コホモロジー類に対して、 既約成分ごとのネーター作用素表示$[r(z)]=T_{1}[ \frac{f_{1}’(z)}{f_{1}(z)}]+\cdots+T_{m}[\frac{f_{m}’(z)}{f_{m}(z)}]$,$T_{i}\in Q\langle z,$$\partial_{z}\rangle$が求まる。
行列 $A$ の固有値$\lambda_{i}$に対する射影行列$P_{i}$を求めるために、 ネーター作用素が使えることを示そう。 いま、 $A$ の最小多項式を $\pi(z)=fi(z)^{p_{m}}\cdots f_{m}(z)^{\ell_{m}}$ とする。 $f_{i}(z)$ は固有値$\lambda_{i}$の最小多項式である。 まず、ネーター作用素$[ \frac{1}{\pi(z)}]=T_{1}[\frac{f_{1}’(z)}{f_{1}(z)}]+\cdots+T_{m}[\frac{f_{m}’(z)}{f_{m}(z)}]$を求める。 ネーター作用素$T_{i}= \sum_{k=0}^{\ell_{t}-1}(-\partial_{z})^{\ell_{i}-k}t_{k}(z)$に対して、 随伴作用素$T_{i}^{*}= \sum_{k=0}^{\ell_{i}-1}t_{k}(z)(\partial_{z})^{p}‘-k$は容易に得られる。部分積分と留数定理により$P_{i}$$=$$\frac{1}{2\pi\sqrt{-1}}\int_{C_{i}}R(z)dz=\frac{1}{2\pi\sqrt{-1}}\int_{C_{t}}\Psi_{\pi}(zE, A)\frac{1}{\pi(z)}dz$$=$$\frac{1}{2\pi\sqrt{-1}}\int_{C_{i}}\Psi_{\pi}(zE, A)\sum_{j=1}^{m}T_{j}\frac{f_{j}’(z)}{f_{j}(z)}dz=\frac{1}{2\pi\sqrt{-1}}\int_{C_{i}}\Psi_{\pi}(zE, A)T_{i}\frac{f_{i}’(z)}{f_{i}(z)}dz$$=$$\frac{1}{2\pi\sqrt{-1}}\int_{C_{i}}\{T_{i}^{*}\Psi_{\pi}(zE, A)\}\frac{f_{i}’(z)}{f_{i}(z)}dz=\{T_{i}^{*}\Psi_{\pi}(zE, A)\}|_{z=\lambda_{i}}$このことから 2 変数多項式$(T_{i}^{*}\Psi_{\pi})(z, y)$$\Psi_{\pi}(z, y)$についての行列多項式に対して、 微分作用素$F_{i}(\lambda_{i}E, A)$が射影行列$\tau_{i}*$$P_{i}$を作用させ、 得られた多項式 $F_{i}(z, y)=$になることが分かった。

126
次に、 巾零行列に亀$D_{i}$をどのように求めるかが問題であるが、実は、が求まる。 すなわち、をとり、 同様の計算をすれば、$T_{i}= \sum_{k=0}^{p_{:-1}}(-\partial_{z})^{\ell_{*}-k}t_{k}(z)$$= \sum_{k=0}^{\ell:-1}(-\partial_{z})^{\ell:-k}kt_{k}(z)$$D_{i}=\{S_{i}^{*}\Psi_{\pi}(zE, A)\}|_{z=\lambda}$の代わり$D_{i}$.となる。 以上より、 スペクトル分解を求めるアルゴリズムは次のようになる。
アルゴリズム 1.
入力: $Q$ 上の正方行列 $A$

出力: スペクトル分解 $\{P_{i;}D_{i}\}$1.

$A$の特性多項式$\chi(z)$2.

$A$の最小多項式$\pi(z)=f_{1}^{\ell_{1}}\cdots f_{m^{m}}^{p}$を求める。

3. $[1/\pi(z)]$ のネーター作用素$T_{1},$$\cdots,$とその既約分解を求める。
$T_{m}$を求める。

4. 多項式 $F_{i}(z,y)=T_{i}^{*}\Psi_{\pi}(z, y)mod f_{i}(z)$ および $G_{i}(z,y)=S_{i}^{*}\Psi_{\pi}(z, y)mod f_{i}(z)$ を求める。
5. 行列多項式 $P_{i}=F_{i}(\lambda_{i}E,A)$ および $D_{i}=G_{i}(\lambda_{i}E, A)$ を求める。
アルゴリズム 1 のステップ 5 では行列多項式を求める。 $F_{i}(z,y)$ のり、 また、$z$に関する次数は、 $\deg\pi-1$ であに関する次数は、 $\deg f_{i}-1$ であることに注意すると、 ホーナー法を用いた行列多項式計算$y$では、月を求めるためには行列同士の乗算が $(\deg f_{i}-1)(\deg\pi-1)$ 回必要である。
ついて、標準的方法では行列積には $O(n^{3})$ 回の乗算が必要であるため、$P_{i}$$n$

次正方行列 $A$ にを求めるための乗算の総数は、回となる。既約因子の次数は下げられないので、計算の効率化のためには、 $\deg\pi$ を下げるように努力することが考えられる。 それが次節に述べる最小消去多項式による高速化である。

$O(n^{3}\deg f_{i}\deg\pi$4

最小消去多項式による高速化

41

最小消去多項式によるスペクトル分解アルゴリズム

定義 2. 正方行列 $A$ とベクトル $v\neq 0$ に対し、 $f(A)v=0$ を満たす次数最小のモニック多項式を、$v$の最小消去多項式という。
定理 4. 第$j$

基本ベクトル $ej$ の最小消去多項式を$\pi_{j}(z)$とする。 このとき、 $A$ のレゾルベント $R(z)$ について$R(z)e_{j}= \frac{1}{\pi j(z)}\Psi_{J}(zE,A)e_{j}$,ただし$\Psi_{j}(x, y)=\frac{\pi_{j}(x)-\pi_{j}(y)}{x-y}\in Q[x,y]$.

が成り立っ。
$A$の最小多項式 $\pi(z)$ と最小消去多項式$\pi_{j}(z)$を比較すると、 $\deg\pi j\leq\deg\pi$ であることは容易に分かる。 したがってアルゴリズム 1 において、 最小多項式を最小消去多項式に置き換えることで、 高速化することができる。 したがって新しいスペクトル分解アルゴリズムは次のようになる。

アルゴリズム 2.
入力: $Q$ 上の正方行列 $A$

出力: スペクトル分解 $\{P_{i};D_{i}\}$

127
1.

$A$

2. 各の特性多項式$e_{j}$を求める。

$\chi(z)$の最小消去多項式$\pi j(z)=f_{1}^{p_{1j}}\cdots f_{m^{mj}}^{\ell}$

3. $[1/\pi_{j}(z)]$ のネーター作用素$T_{1j},$$\cdots,$ $T_{mj}$とその既約分解を求める。

を求める。

4. 多項式 $F_{ij}(z,y)=T_{ij}^{*}\Psi_{j}(z,y)mod f_{i}(z)$ および $G_{ij}(z,y)=S_{ij}^{*}\Psi_{j}(z,y)mod f_{i}(z)$ を求める。
5. 行列多項式 $P_{i}ej=F_{ij}(\lambda_{i}E, A)ej$ および $D_{i}ej=G_{ij}(\lambda_{i}E,A)ej$ を求める。
6.

$P_{i}$および$D_{i}$を得る。

前節と同様にアルゴリズム 2 における計算量を見積もると、となる。

$\frac{1}{n}\sum_{j=1}\deg\pi_{j}n\leq\deg\pi$$P_{i}$を求めるためには、 $O(n^{2} \deg f_{i}\sum_{j=1}^{n}\deg\pi_{j})$であるから、 アルゴリズム 2 のほうが計算量が小さい。 この差が大きければ大きいほど高速化されたことになる (ブロック対角化されている場合など)。

アルゴリズムの並列化の観点から見ると、 ステップ 3 については、 列番号
ステップ 4,5 については、 既約因子番号$i$および列番号$j$$j$でそれぞれ独立に計算でき、でそれぞれ独立に計算できることが分かる。 さらに後述するようにステップ 2 における最小消去多項式の構成においても並列化技法が使用できる。 したがってアルゴリズム 2 は並列化の面からは非常に扱いやすい。

42

最小消去多項式の構成法

特性多項式の既約分解が$\pi_{j}(z)=f_{1}^{\ell_{1j}}$...

$f_{m^{mj}}^{\ell}$$\chi(z)=f_{1}^{p_{1}}\cdots f_{m^{m}}^{\ell}$,であれば、最小消去多項式は$p_{ij}\leq\ell_{i}$の形になる。つまり、既約因子は分かるため指数ベクトル$(\ell_{1j}, \cdots,\ell_{mj})$が問題である。指数ベクトルは次の手順で求めることができる。
アルゴリズム 3.
$k=1,$ $\cdots,m$ について次を行う。

1. $\chi_{k}(z)=\chi(z)/f_{k}(z)^{\ell_{k}}$ とおき、 $b_{kj}=\chi_{k}(A)e_{j}$ をすべて求める。

2. $b_{kj}=0$ ならば、 $\ell_{kj}=0$ である。 $b_{kj}\neq 0$ ならば、順に $f_{k}(A)$ を左からかけて、 $f_{k}(A)^{p}b_{kj}=0$ となる最小の $p>0$ が $l_{kj}=p$ である。
さて、 この方法で最小消去多項式が計算できることは分かったが、問題点は計算量が大きいことである。

したがって、確率的アルゴリズムを導入して高速化を図る。確率的アルゴリズムのポイントは、$\pi_{j}(A)e_{j}=0$という事実である。

ならば
$v$

${}^{t}v\pi_{j}(A)e_{j}=0$を乱数ベクトルにとり、 ${}^{t}v\pi j(A)e_{j}=0$ で最小消去多項式を探索すれば、 ほぼ確率 1で最小消去多項式を発見できることが期待される。
アルゴリズム 4. 乱数ベクトル1.

$\chi_{k}(z)=\chi(z)/f_{k}(z)^{\ell_{k}}$$v$を選び、 $k=1,$ $\cdots,m$ について次を行う。

とおき、 ${}^{t}v_{k}={}^{t}v\chi_{k}(A)$ をすべて求める。

1282.

${}^{t}v_{k}e_{j}=0$ならば、 $\ell_{kj}=0$ と置く。

$0$

でなければ、${}^{t}v$に順に $f_{k}(A)$ を右からかけて、${}^{t}v_{k}f_{k}(A)^{p}$を求め、 ${}^{t}v_{k}f_{k}(A)^{p}b_{kj}=0$ となる最小の $p>0$ で $\ell_{kj}=p$ と置く。

3. 推定した指数ベクトルが最小消去多項式になっているか$\pi J(A)e_{j}$を実際に計算して確認。最小消去多項式でなければアルゴリズム 3 でやり直し。
ステップ 1 では、 すべての

$v_{1},$$\cdots,v_{m}$を求めるには、 ベキ乗算${}^{t}u\mapsto {}^{t}uf_{k}(A)^{\ell_{k}}$が$m^{2}$回必要であるよ

うに思えるが、 2 分探索の方法を用いれば、 およそ $m\log_{2}m$ 回で実行可能である。 また行列するより、 ベクトル${}^{t}v\chi_{k}(A)$の計算の方がはるかに計算量が小さい。 よって、再利用を試みるのは計算量的に危険だが、${}^{t}v\chi_{k}(A)$$\chi_{k}(A)$$\chi_{k}(A)$を計算を計算しておいて、ではそれほどでもない。 しかもアルゴリズム 4 は、全てのステップで並列化できる。

5拡張行列ホーナー法
既に見たように、 アルゴリズム 2 のステップ 5 では、 行列多項式 $F_{ij}(\lambda_{i}E,A)eJ$ の計算を行うことで展開し、 $F_{ij}(z,y)= \sum_{k=0}^{\deg f_{:}-1}F_{ij}^{(k)}(y)z^{k}$ と表されたとすれば、 $P_{i}e_{j}=$になる。 $F_{ij}(z, y)$ を変数$z$$\sum_{k^{eg}}^{d-1}\lambda_{j}^{k}\{F^{(k)}(A)e\}$である。 よって、 一般に多項式 $f(z)\in Q[z]$ と行列 (またはベクトル) $G$ に対して、 $f(A)G$ を計算する必要がある。 これには (行列) ホーナー法と呼ばれる方法が広く利用されている。
アルゴリズム 5(ホーナー法).

入力: $f(x)=a_{0}x^{n}+a_{1}x^{n-1}+\cdots+a_{n},$$A$$G$ ; 行列
: 正方行列，

出力 $:F_{n}=f(A)G$

数列 $\{F_{0}, F_{1}, \cdots, F_{n}\}$ を漸化式$F_{0}=a0G$ ,$F_{i}=AF_{i-1}+a_{i}G$で求める。
よく知られているように、 ホーナー法では、 $A$ が $m$ 次平方行列、 $G$ が $m\cross m’$ 行列のとき、 $m$ 次平方行列と $m\cross m’$ 行列の積計算が $\deg f$ 回必要である。 したがって、 計算量は $O(m^{2}m’\deg f)$ となる。

次にわれわれの提案する拡張行列ホーナー法について述べる。
$k=\lfloor n/d\rfloor$$n$次多項式 $f(x)$ に対し $d<n$ を固定し、と置く。多項式列 $\{b_{i}(x)\}_{i=1,\cdots,k}$ が存在して$f(x)=b_{0}(x)x^{dk}+b_{1}(x)x^{d(k-1)}+\cdots+b_{k-1}(x)x^{d}+b_{k}(x)$ ,$\deg b_{0}=(nmod d)\leq d-1$ ,$\deg b_{1}=\cdots=\deg b_{k}=d-1$と書ける。 この分解を用いれば、 $f(A)G= \sum_{i=0}^{k}(A^{d})^{k-i}(b_{i}(A)G)$ となる。 したがって次のアルゴリズムを得る。
アルゴリズム 6(拡張行列ホーナー法).
$G$ :入力: $A$ : 正方行列，$f(x)$ : 多項式、 自然数 $d<\deg f$行列，

出力: $F_{k}=f(A)G$

1.

$A^{d}$を計算。

2. $AG,$ $\cdots,A^{d-1}G$ を計算。

3. $B_{i}=b_{i}(A)G$ を、 $G,$ $AG,$$\cdots,$$A^{d-1}G$の線形結合で計算。129
4. 数列$\{F_{0},F_{1} , \cdot\cdot\cdot,F_{k}\}$$\ovalbox{\tt\small REJECT}=B_{0}$,を漸化式$F_{i}=A^{d}F_{i-1}+B_{i}$で求める。
さて、 アルゴリズム 6 の計算量はどのくらいであろうか。 まずステップ 1 では、 $m$ 次正方行列の積計算が $\log_{2}d$ 回必要である。 ステップ 2 では $m$ 次平方行列と $m\cross m^{l}$ 行列の積計算が $d-1$ 回、 ステップ

4 では、 $m$ 次平方行列と $m\cross m’$ 行列の積計算が $k=\lfloor(\deg f)/d\rfloor$ 回必要である。 したがって、 計算量は$O(m^{3}\log 2d+m^{2}m’(d+\lfloor(\deg f)/d\rfloor))$である。

よって、 $m=m’$ のときの計算量は、 ホーナー法では $O(m^{3}\deg f)$$O(m^{3}(\log 2d+d+\lfloor(\deg f)/d\rfloor))$、拡張行列ホーナー法ではであるから、 $\deg f$ が十分大きいとき、$d\fallingdotseq\sqrt{\deg f}$程度にとれば、拡張行列ホーナー法が高速であると考えられる。 また、の計算から、 は 2 のべキにとるべきだと考えられる。
われわれは拡張ホーナー法を Risa$/Asir$ 上に実装して実験を行った。 いま、 $A,$を 50 次正方行列と$A^{d}$$d$$G$し、 行列要素は $128bit$ 整数とした。 また、 $\deg f=24,$ $d=4$ とした。実験結果は表 1 の通りであるが、$\log$

2 $d+d+n/d=2+4+6=12,$$\deg f=24$ であることから、 経過時刻については、 理論的な予想と合致していると考えられる。 さらにヒープ使用量の単位は 1 ワード $=4$ バイトであるが、拡張行列ポーナー法がずっと効率的であることは注目すべき点である。

表 1: ホーナー法と拡張ホーナー法の比較 ( $G$ が行列の場合)

一方、 $m’=1$ のときの計算量は、 ホーナー法では $O(m^{2}\deg f)$ 、拡張行列ホーナー法ではである。 したがって、拡張行列ホーナー法では高速化されないと考えられる。 $Risa/Asir$ での実験結果は表 2 の通りであり、従来のホーナー法が高速である。 しかしながら、 拡張$O(m^{2}(m\log_{2}d+d+\lfloor(\deg f)/d\rfloor))$

ホーナー法では、 ステップ 1 の$A^{d}$の計算が支配的であり、 ステップ 2,3,4 は高速である。 したがって、 ス

ペクトル分解のよ’ うに行列多項式計算を繰り返す場合は、特に並列計算を前提とする本研究では、 ステップ1 を前処理として切り放すことで計算を効率化できると考えられる。

表 2: ホーナー法と拡張ホーナー法の比較 ( $G$ がベクトルの場合)

130以上の考察から、 アルゴリズム 2 のステップ 5 において、 ホーナー法と拡張行列ホーナー法をそれぞれ.
.
.

用いたタイミングデータを比較した。
実験環境: Linux/amd642.6.39, Xeon $E5645(6-core,2.4GHz)\cross 2,96GB$ memory$\pi(z)=\prod_{i=1}^{4}f_{i}(z)^{4},$ $\deg f_{i}(z)=3$ .
$A:48$ 次行列，$d=4$

表 3: ホーナー法と拡張ホーナー法の比較 (スペクトル分解)

参考文献[1] 小原功任，田島慎一 : 行列のスペクトル分解・固有ベクトルの分散計算，京都大学数理解析研究所講究録 1666(2008),.
$65\triangleleft 8$[2] K. Ohara and S. Tajima: Spectral Decomposition and Eigenvectors of Matrices by Residue Calculus,
Proceedings of the Joint Conference of ASCM 2009 and MACIS 2009, COE Lecture Note 22 (2009),
Kyushu University, 137-140.
[3] 加藤涼香，田島慎一: 有理関数のローラン展開アルゴリズムと代数的局所コホモロジー，京都大学数理解析研究所講究録 1395(2004), 50-56.
[4] 庄司卓夢，田島慎– 1 変数代数的局所コホモロジー類に対する $Risa/$ Asir 用パッケージ taji-alc,$Risa/$ Asir Journa12 (2007), 1-32.

[5] 田島慎一，飯塚由貴恵: 行列のスペクトル分解アルゴリズムについて，京都大学数理解析研究所講究録
1666(2008), 49-56.

[6] 飯塚由貴恵，田島慎一: 行列のスペクトル分解アルゴリズムー最小多項式が重複因子を持つ場合，数式処理 1 住 2(2009).
[7] 飯塚由貴恵，田島慎一: 行列のスペクトル分解アルゴリズムー最小多項式が複数の重複因子から成る
場合，京都大学数理解析研究所講究録