The computational complexity of a set of quadratic functions

AbstractWe consider the problem of determining the fewest number of nonscalar multiplications needed to compute a set of quadratic functions. We develop mathematical characterizations and lower bound techniques which, when applied to problems related to matrix multiplication or quaternion multiplication, generate bounds similar to those known for the bilinear case. The special case of a pair of quadratic functions is also considered and good lower and upper bounds are established for this case