On the Complexity of Computing Error Bounds |
| |
Authors: | J Demmel B Diament G Malajovich |
| |
Institution: | (1) Computer Science Division and Mathematics Department University of California Berkeley, CA 94720, USA demmel@cs.berkeley.edu , US;(2) Computer Science Division University of California Berkeley, CA 94720, USA bjd@cs.berkeley.edu , US;(3) Departamento de Matemática Aplicada Universidade Federal do Rio de Janeiro Caixa Postal 68530 CEP 21945, Rio de Janeiro, RJ, Brasil gregorio@labma.ufrj.br, BR |
| |
Abstract: | 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 , where n is the dimension of the input matrix, k is the bitsize, and where either or grows faster than any polynomial in n . Our results hold for the RAM model with bit complexity, as well as computations over rational and algebraic numbers, but
not real or complex numbers. Our results also extend to estimating error bounds or condition numbers for other linear algebra
problems such as computing eigenvectors.
September 10, 1999. Final version received: August 23, 2000. |
| |
Keywords: | AMS Classification 65F35 68Q25 |
本文献已被 SpringerLink 等数据库收录! |
|