Publication
Information Processing Letters
Paper

On the arithmetic complexity of matrix Kronecker powers

View publication

Abstract

In this paper we study the arithmetic complexity of computing the pth Kronecker power of an n × n matrix. We first analyze a straightforward inductive computation which requires an asymptotic average of p multiplications and p - 1 additions per computed output. We then apply efficient methods for matrix multiplication to obtain an algorithm that achieves the optimal rate of one multiplication per output at the expense of increasing the number of additions, and an algorithm that requires O(log p) multiplications and O(log2p) additions per output. © 1983.

Date

05 Oct 1983

Publication

Information Processing Letters

Authors

Topics

Share