Time-space tradeoffs for some algebraic problems
Joseph F. JáJá · 1980
We study the time-space relationship of several algebraic problems such as matrix multiplication and matrix inversion. Several results relating the algebraic properties of a set of functions to the structure of the graph of any straight-line program, that computes this set, are shown. Some of our results are the following. Multiplying m × n by n × p matrices with space S requires at least time T ≥ Ω(mnp/S). Inverting an n × n matrix with space S requires at least time T ≥ Ω(n4/S).