
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Algorithms for Evaluating the Matrix Polynomial I+A+A^{2}+…+A^{N1} with Reduced Number of Matrix Multiplications
Kotaro MATSUMOTO Kazuyoshi TAKAGI Naofumi TAKAGI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E101A
No.2
pp.467471 Publication Date: 2018/02/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E101.A.467
Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: evaluation of matrix polynomial, matrix multiplication,
Full Text: PDF(565.7KB) >>Buy this Article
Summary:
The problem of evaluating the matrix polynomial I+A+A^{2}+…+A^{N1} 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 doublebase 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.

