Fast methods for computing the p-radius of matrices

The p-radius characterizes the average rate of growth of norms of matrices in a multiplicative semigroup. This quantity has found several applications in recent years. We raise the question of its computability. We prove that the complexity of its approximation increases exponentially with p. We then describe a series of approximations that converge to the p-radius with a priori computable accuracy. For nonnegative matrices, this gives efficient approximation schemes for the p-radius computation. © 2011 Society for Industrial and Applied Mathematics.