A limited disproof to the conjecture of evaluating the matrixpolynomial I+A+A2+···+AN-1

摘要

The problem of evaluating matrix polynomial I+A+A2+···+AN-1, has been considered. The proposed algorithms require at most 3·[log2 N] and 2·[log2 N]-1 matrix multiplications, respectively. If the binary representation of N is (itit-1···i1i 0)2, then the number of the matrix multiplication for the evaluation of this polynomial is at least 2·[log2 N]-2+it-1. In the present communication the authors prove that for many values of N there exists an algorithm requiring a fewer number of matrix multiplications, thus disproving Lei-Nakamura's conjecture