数理解析研究所講究録
第 1785 巻 2012 年 162-166

162

Risa / Asir の行列演算と改良について
近藤祐史

兵頭礼子

村尾 裕一

(株) アルファオメガ香川高等専門学校電気通信大学
齋藤 友克(株) アルファオメガ

1

はじめに数式処理システム Risa/Asir には、行列の乗算アルゴリズムとして、内積アルゴリズムと Strassen-Winogradアルゴリズムが実装されている。 Strassen-Winograd アルゴリズムでは、 行列の成分として多項式を持ち、また多項式が密なものに対しては内積アルゴリズムよりも計算量の比率以上に高速に演算を行うことができるが、演算速度の大きな要因とのなるものは、演算の中で使用するメモリ使用量に依存するため、疎な多項式を要素に持っ行列では、 Strassen-Winograd アルゴリズムでは内積アルゴリズムと同程度の演算速度となる [14]。そのため、 $Risa/Asir$ 上では、標準では、 内積アルゴリズムが稼動するようになっており、

ctrl (“ StrassenSi $ze$ “, ) としたときのみ、行列サイズが$n$$n$$n$以下になるまで Strassen-Winograd アルゴリズムを適用し、計算するように実装されている。 また、 アルゴリズムの実装だけでなく、疎行列を扱うのに適したデータ構造を検討、実装実験を行い、演算時間の比較実験から，数式処理に適したデータ型の考察を行なっている ([10],[11],[12],[13])。今回、 $Risa/Asir$ で現行の CPU を使った行列の乗算の実験を行い、その結果報告と、逆行列の演算の実装について報告する。

2

行列の乗算実験
実験対象行列として、$n$$n$であり各成分は表 1 のような成分を持つ行列 $A,$ $B$ を考える。 これらの行列を
表 1: 実験データ使い、 $Risa/Asir$ 上で内積アルゴリズムと Strassen-Winograd アルゴリズムを適用して $A$算時間を計測する。使用するマシンは CPU:AMD Phenom 9750 $X4(2400MHz)$82Stable amd64 上で実験を行った。

、$B$を実行し、演

メモリ : $4GB$、FreeBSD

16321

演算時間と考察

表 1 の行列を用いて、 $Risa/Asir$ 上で内積アルゴリズムと Strassen-Winograd アルゴリズムでのそれぞれの演算時間を表 2、表 3 に示す。 また、 同様の実験を CPU:AMD AthlonXP $3200+(2200MHz)$ メモリ :$512MB$ FreeBSD 5.2 Stable 上で実験を行った結果を表
表 5 に示す [14]。
、、

$4$、

Strassen-Winograd アルゴリズムの適用で、 AthlonXP では十分な速度を得られなかった Case II の場合
でも、現行の CPU である Phenom を使った場合 (表 3) では十分に高速化されている。 CPU 上のキャッシュメモリの増加等、考えられる要因はさまざまであるが、疎な多項式を要素にもつ行列の乗算でも，StrassenWinograd アルゴリズムの適用によって十分高速化されていると考えられる。 アーキテクチャや要素となる多項式行列の要素の密度によって同じアルゴリズム、 同じ要素でも演算速度が変わっており、 今度もアー164
表 5: AthlonXP 上での Case II の演算時間の比較 (単位: 秒)

キテクチャ別、要素別の実験を続け、 アルゴリズム選択のベンチマークとなるような要素の検討などを行いたい。

3

逆行列$Risa/$

Asir には、逆行列の演算では、 ガウスの消去法アルゴリズムが実装されている。今回，Strassen の逆行列アルゴリズムを実装し、演算時間の比較を行った。

3.1

Strassen のアルゴリズム

行列 A を$A=$$($

ただし$=A_{22}$$A_{11}A_{21}$$A_{12}A_{22})=$$A_{21}A_{11}^{1}A_{12})$$A_{21}A_{11}^{1}I$

$0I)$

$0)$

$A_{11}0$$0I$$A_{11_{I}}^{1}A_{12})$のようにブロック LDU 分解可能ならば、逆行列は以下のように計算できる。
$A1$$A_{11}^{1}A_{12}I)$$A_{11}0$

$=$

$I0$

$=$

$A_{11}^{1}+A_{11}^{1}A_{12^{1}}A_{21}A_{11}^{1}1A_{21}A_{11}^{1}$$0_{1})$$A_{21}A_{11}^{1}I$$A_{11}^{1}A_{12}1$$0I)$$1)$となる。 また、 Strassen の方法で逆行列の計算量は、$O(7^{k})\approx O(7^{\log_{2}n})=O(n^{\log_{2}7})\approx O(n^{2.8})$となることが示されている同。
このアルゴリズムを、 Risa$/Asir$ 上に実装し、逆行列の演算時間の計測を行った。

32

実験

実験対象行列として、$n$$n$であり各成分は $a_{ij}=rand\sigma m$$x$となる行列 $A$ を用い、 演算速度の計測を行った。使用マシンは CPU :AMD Phenom 9750 $X4(2400MHz)$ メモリ : $4GB$ FreeBSD S.2 Stableamd64 である。表 6 に演算時間を示す。今回の Strassen の逆行列アルゴリズムの適用実験では、 ガウスの、、消去法アルゴリズムに比べ高速演算を行うことができなかった。今後もアルゴリズムの実装方法や要素となる多項式の種類など、検討を重ねていく必要がある。 また、行列の乗算の実験同様、 アーキテクチャ別、要素別の実験を続け、 アルゴリズム選択のベンチマークとなるような要素の検討などを行いたい。

165

参考文献
[1] D. Bini and V.Y. Pan. Polynomial and Matm, Vol. 1 of Progress in Theoretical Computer Science.

Birkh\"auser, 1994.
[2] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Joumal ofSymbolic Computation, 9:251-280, 1990.
[3] M. L. Griss. The algebraic solution of sparse linear systems via minor expansion. $ACM$ Transactions

on Mathematical Software, Vol. 2, No. 1, pp. 31-49, 1976.
[4] E. Horowitz and S. Sahni. On computing the exact determinant of matrices with polynomial entries.
Joumal of the $ACM$, Vol. 22, No. 1, pp. 38-50, 1975.

[5] M. Noro and T. Takeshima. Risa/Asir –a computer algebra system. In P. S. Wang, editor,
Proceedings of ISSA $C92$, pages 387-396, Berkeley, CA, July 27-291992.
[6] V. Strassen. Gaussian elimination is not optimal. Numer. Math., 13:354-356, 1969.

[7] S. Winograd. On multiplication of 2

2 matrices. Linear Algebra and its Applications, 4:381-388,

1971.
[8] 兵頭礼子，村尾裕一，齋藤友克．Risa/asir の matrix 演算の検討．数式処理，9:10-11, 2002. 第 11 回大会報告．

[9] 兵頭礼子，村尾裕一，齋藤友克．Risa/asir の matrix 演算の新しい実装について．講究録 1295
rComputer Algebra–Algorithms, Implementations and Applications, $2001_{J}$ , pages 213-219. 京都大学数理解析研究所，2002.
[10] 兵頭礼子，村尾裕一，齋藤友克．数式処理のための行列演算の効率的な実装法について．数式処理，
10:18-19, 2003. 第 12 回大会報告．
[11] 兵頭礼子，村尾裕一，齋藤友克．多項式表現と行列演算の改良．講究録 1335 rComputer AlgebraAlgorithms, Implementations and Applications,, pages 28-32. 京都大学数理 m 研究所，2003.
$2002_{\lrcorner}$$\ovalbox{\tt\small REJECT}$[12] 兵頭礼子，村尾裕一，齋藤友克．行列計算と基本線形演算の実装法について．講究録 $1S95$ rComputer
Algebra–Algorithms, Implementations and Applications,, pages 218-223. 京都大学数理解析研究所，2004.
$2003_{\lrcorner}$[13] 兵頭礼子，村尾裕一，齋藤友克．Risa/Asir の行列演算の実装 II. 講究録 1456 rComputer AlgebraDesign of Algorithms, Implementations and Applications,, pages 144-149. 京都大学数理解析研究所，2005.
$2005_{\lrcorner}$166[14] 兵頭礼子，村尾裕一，齋藤友克．Matrix Multiplication Made Fast
Practical View of Fast Matrix
Operation for Computer Algebra System. 数式処理，11:3-19, 2005. Noda2005 論文．
–