講演名 2014-09-02
行列多項式I+A+A^2+…+A^の計算における乗算回数について
松本 耕太郎, 高木 直史, 高木 一義,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 行列多項式I+A+A^2+…+A^の計算は,信号処理やグラフ理論などで現れ,必要な行列乗算の回数の少ない計算法の研究がなされてきた.これまでに,行列乗算回数がlogNに比例する計算法として,Nの素因数分解に基づく計算法,Nの2進表現に基づく計算法,Nの3進表現に基づく計算法,Nの2進2進混合表現に基づく計算法が提案されている.本報告では,Nの素因数分解に基づく計算法において行列乗算回数をより少なくする方法を示し,これを利用した計算法を提案する.1000までのNについて行列乗算回数を調べた結果,171個について従来法よりも少なくなることがわかった.特に,3個については2回少なくなることが分かった.
抄録(英) Evaluation of the matrix polynomial I + A + A^2 + … + A^ appears in signal processing and graph theory. Evaluation methods with smaller number of matrix multiplications have been investigated. As methods with the number of matrix multiplications being proportional to log N, a method based on prime factor decomposition of N, one based on the binary representation of N, one based on the ternary representation of N, and one based on binary-ternary mixed representation of N have been proposed. In this report, we show that the number of matrix multiplications in the first method can be reduced, and propose a new evaluation method. For 171 up to 1000, the number of required matrix multiplications is smaller than that by all of previous methods.
キーワード(和) 行列多項式 / 行列乗算 / 計算量
キーワード(英) Matrix polynomial / matrix multiplication / computational complexity
資料番号 COMP2014-18
発行日

研究会情報
研究会 COMP
開催期間 2014/8/26(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 Theoretical Foundations of Computing (COMP)
本文の言語 JPN
タイトル(和) 行列多項式I+A+A^2+…+A^の計算における乗算回数について
サブタイトル(和)
タイトル(英) On the number of matrix multiplications in the evaluation of the matrix polynomial I+A+A^2+…+A^
サブタイトル(和)
キーワード(1)(和/英) 行列多項式 / Matrix polynomial
キーワード(2)(和/英) 行列乗算 / matrix multiplication
キーワード(3)(和/英) 計算量 / computational complexity
第 1 著者 氏名(和/英) 松本 耕太郎 / Kotaro MATSUMOTO
第 1 著者 所属(和/英) 京都大学
Kyoto University
第 2 著者 氏名(和/英) 高木 直史 / Naofumi TAKAGI
第 2 著者 所属(和/英) 京都大学
Kyoto University
第 3 著者 氏名(和/英) 高木 一義 / Kazuyoshi TAKAGI
第 3 著者 所属(和/英) 京都大学
Kyoto University
発表年月日 2014-09-02
資料番号 COMP2014-18
巻番号(vol) vol.114
号番号(no) 199
ページ範囲 pp.-
ページ数 5
発行日