Codenotti B., Leoncini M. Matrix inversion in RNC1. In: Journal of Complexity, vol. 7 pp. 282 - 295. Academic Press, 1991. |

Abstract (English) |
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 |

1) Download Document PDF |

Open access Restricted Private