Istituto di Scienza e Tecnologie dell'Informazione     
Codenotti B., Leoncini M. Matrix inversion in RNC1. In: Journal of Complexity, vol. 7 pp. 282 - 295. Academic Press, 1991.
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.
Subject Matrix

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional