Given a nxn nonsingular linear system Ax=b, we prove that thesolution x can be computed in parallel time ranging from Omega(logn) to O(log^2 n), provided that the condition number, c(A), of A isbounded by a polynomial in n. In particular, if c(A) = O(1), a timebound O(log n) is achieved. To obtain this result, we reduce thecomputation of x to repeated matrix squaring and prove that a numberof steps independent of n is sufficient to approximate x up to arelative error 2^–d, d=O(1). This algorithm has both theoretical andpractical interest, achieving the same bound of previously publishedparallel solvers, but being far more simple.

Repeated Matrix Squaring for the Parallel Solution of Linear Systems / B., Codenotti; Leoncini, Mauro; G., Resta. - STAMPA. - 605:(1992), pp. 725-732. ((Intervento presentato al convegno International Conference Parallel ARchitectures and Languages Europe, PARLE 92 tenutosi a Paris, France nel June 15-18, 1992.

Repeated Matrix Squaring for the Parallel Solution of Linear Systems

LEONCINI, Mauro;
1992

Abstract

Given a nxn nonsingular linear system Ax=b, we prove that thesolution x can be computed in parallel time ranging from Omega(logn) to O(log^2 n), provided that the condition number, c(A), of A isbounded by a polynomial in n. In particular, if c(A) = O(1), a timebound O(log n) is achieved. To obtain this result, we reduce thecomputation of x to repeated matrix squaring and prove that a numberof steps independent of n is sufficient to approximate x up to arelative error 2^–d, d=O(1). This algorithm has both theoretical andpractical interest, achieving the same bound of previously publishedparallel solvers, but being far more simple.
International Conference Parallel ARchitectures and Languages Europe, PARLE 92
Paris, France
June 15-18, 1992
605
725
732
B., Codenotti; Leoncini, Mauro; G., Resta
Repeated Matrix Squaring for the Parallel Solution of Linear Systems / B., Codenotti; Leoncini, Mauro; G., Resta. - STAMPA. - 605:(1992), pp. 725-732. ((Intervento presentato al convegno International Conference Parallel ARchitectures and Languages Europe, PARLE 92 tenutosi a Paris, France nel June 15-18, 1992.
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/641691
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 0
social impact