Istituto di Scienza e Tecnologie dell'Informazione     
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.
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

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