On the Complexity of Computing Error Bounds

We consider the cost of estimating an error bound for the computed solution of a system of linear equations, i.e. estimating the norm of a matrix inverse. Under some technical assumptions we show that computing even a coarse error bound for the solution of a triangular system of equations costs at least as much as testing whether the product of two matrices is zero. The complexity of the latter problem is in turn conjectured to be the same as matrix multiplication, matrix inversion, etc. Since most error bounds in practical use have much lower complexity, this means they should sometimes exhibit large errors. In particular, it is shown that condition estimators that 1) perform at least one operation on each matrix entry and 2) are asymptotically faster than any zero tester, must sometimes over or underestimate the inverse norm by a factor of at least 2 δk+τ(n) , where n is the dimension of the input matrix, k is the bitsize, and where either δ ≥.5 or τ(n) grows faster than any polynomia