Codenotti B., Leoncini M., Resta G. Repeated matrix squaring for the parallel solution of linear systems. In: PARLE - 4th International PARLE Conference (Paris, France, 06 1992). Proceedings, pp. 725 - 732. D. Etiemble, J.C. Syre (eds.). (Lecture Notes in Computer Science, vol. 605). Springer, 1992. |

Abstract (English) |
Given a n x n nonsingular linear system Ax = b, we prove that the solution x can be computed in parallel time ranging from Ω(log n) to Ω(log^2 n), provided that the condition number, μ(A) of A is bounded by a polynomial in n. In particular, if μ(A) = 0(1), a time bound O(log n) is achieved. To obtain this result, we reduce the computation of x to repeated matrix squaring and prove that a number of steps independent of n is sufficient to approximate x up to a relative error 2^-d, d = 0(1). This algorithm has both theoretical and practical interest, achieving the same bound of previously published parallel solvers, but being far more simple. | |

Subject | Matrix Linear systems G.1.3 Numerical Linear Algebra. Linear systems |

1) Download Document PDF |

Open access Restricted Private