Presentation	2014-09-02 On the number of matrix multiplications in the evaluation of the matrix polynomial I+A+A^2+…+A^ Kotaro MATSUMOTO, Naofumi TAKAGI, Kazuyoshi TAKAGI,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	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.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Matrix polynomial / matrix multiplication / computational complexity
Paper #	COMP2014-18
Date of Issue

Conference Information
Committee	COMP
Conference Date	2014/8/26(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	On the number of matrix multiplications in the evaluation of the matrix polynomial I+A+A^2+…+A^
Sub Title (in English)
Keyword(1)	Matrix polynomial
Keyword(2)	matrix multiplication
Keyword(3)	computational complexity
1st Author's Name	Kotaro MATSUMOTO
1st Author's Affiliation	Kyoto University()
2nd Author's Name	Naofumi TAKAGI
2nd Author's Affiliation	Kyoto University
3rd Author's Name	Kazuyoshi TAKAGI
3rd Author's Affiliation	Kyoto University
Date	2014-09-02
Paper #	COMP2014-18
Volume (vol)	vol.114
Number (no)	199
Page	pp.pp.-
#Pages	5
Date of Issue