We prove that some central problems in computational linear algebra are in the complexity c1ass RNC?1 that is solvable by uniform families of probabilistic boolean circuits of logarithmic depth and polynomial size. In particular, we first show that computing the solution of n x n linear systems in the form x = Bx + c, with ?B??? <= 1 - n?-k, k = 0(1), in the fixed precision model (i.e., computing d = 0(1) digits of the result) is in RNC?1; then we prove that the case of general n x n linear systems Ax = b, with both ?A??? and ?b??? bounded by polynomials in n, can be reduced to the special case mentioned before.
Matrix inversion in RNC1
Codenotti B;
1991
Abstract
We prove that some central problems in computational linear algebra are in the complexity c1ass RNC?1 that is solvable by uniform families of probabilistic boolean circuits of logarithmic depth and polynomial size. In particular, we first show that computing the solution of n x n linear systems in the form x = Bx + c, with ?B??? <= 1 - n?-k, k = 0(1), in the fixed precision model (i.e., computing d = 0(1) digits of the result) is in RNC?1; then we prove that the case of general n x n linear systems Ax = b, with both ?A??? and ?b??? bounded by polynomials in n, can be reduced to the special case mentioned before.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
