2018年2月1日
Algorithms for evaluating the matrix polynomial I + A + A2 + ⋯ + AN-1 with Reduced Number of Matrix Multiplications
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
- ,
- ,
- 巻
- E101A
- 号
- 2
- 開始ページ
- 467
- 終了ページ
- 471
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1587/transfun.E101.A.467
- 出版者・発行元
- Institute of Electronics, Information and Communication, Engineers, IEICE
The problem of evaluating the matrix polynomial I + A + A2 + ⋯ + AN-1 with a reduced number of matrix multiplications has long been considered. Several algorithms have been proposed for this problem, which find a procedure requiring O(log N) matrix multiplications for a given N. Among them, the hybrid algorithm based on the double-base representation of N, i.e., using mixed radices 2 and 3, proposed by Dimitrov and Cooklev is most efficient. It has been suggested by them that the use of higher radices would not bring any more efficient algorithms. In this paper, we show that we can derive more efficient algorithms by using higher radices, and propose several efficient algorithms.
- ID情報
-
- DOI : 10.1587/transfun.E101.A.467
- ISSN : 1745-1337
- ISSN : 0916-8508
- SCOPUS ID : 85041532171