Additive complexity in directed computations

AbstractA straight-line additive computation which computes a set A of linear forms can be presented as a product of elementary matrices (one instruction of such a computation corresponds to a multiplication by an elementary matrix). For the general complexity measure no methods for obtaining nonlinear lower bounds for concrete natural sets of linear forms are known at the moment (under the general complexity measure of A we mean the minimal number of multipliers in products computing A). In the paper three complexity measures (triangular, directed and a modification of the latter—reduced directed complexity) close in spirit each to others are defined and investigated. For these measures some nonlinear lower bounds are obtained. Moreover, the problem of the exact explicit calculation of the directed complexity is solved for which a suitable algebraic apparatus (the generalized Bruhat decomposition) is developed. Apparatus is exposed in the appendix to the paper