We prove that some central problems in computational linear algebra are in the complexity class RNC1 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 × n linear systems in the form x = Bx + c, with |B|∞ ≤ 1 − n^(−k), k = O(1), in the fixed precision model (i.e., computing d = O(1) digits of the result) is in RNC1 ; then we prove that the case of general n × 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 / B., Codenotti; Leoncini, Mauro. - In: JOURNAL OF COMPLEXITY. - ISSN 0885-064X. - STAMPA. - 7:(1991), pp. 282-295.
Matrix Inversion in RNC1
LEONCINI, Mauro
1991
Abstract
We prove that some central problems in computational linear algebra are in the complexity class RNC1 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 × n linear systems in the form x = Bx + c, with |B|∞ ≤ 1 − n^(−k), k = O(1), in the fixed precision model (i.e., computing d = O(1) digits of the result) is in RNC1 ; then we prove that the case of general n × n linear systems Ax = b, with both |A|∞ and |b|∞ bounded by polynomials in n, can be reduced to the special case mentioned before.Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris