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.
7
282
295
Matrix Inversion in RNC1 / B., Codenotti; Leoncini, Mauro. - In: JOURNAL OF COMPLEXITY. - ISSN 0885-064X. - STAMPA. - 7:(1991), pp. 282-295.
B., Codenotti; Leoncini, Mauro
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/454050
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact