In this paper we present a new parallel algorithm for computing the Cholesky decomposition (LL^T) of real symmetric positive-definite tridiagonal matrices. The algorithm consists of a preprocessing and a factoring stage. In the preprocessing stage it determines a rank-(p-1) correction to the original matrix (p=number of processors) by precomputing selected components x_k of the L factor, k=1... p-1. In the factoring stage it performs independent factorizations of p matrices of order n/p. The algorithm is especially suited for machines with both vector and processor parallelism, as confirmed by the experiments carried out on a Connection Machine CM5 with 32 nodes. Let \hat{x}_k and \hat{x}'_k denote the components computed in the preprocessing stage and the corresponding values (re)computed in the factorization stage, respectively. Assuming that \abs{\hat{x}_k/\hat{x}'_k} is small, k=1... p-1, we are able to prove that the algorithm is stable in the backward sense. The above assumption is justified both experimentally and theoretically. In fact, we have found experimentally that \abs{\hat{x}_k/\hat{x}'_k} is small even for ill-conditioned matrices, and we have proven by an a priori analysis that the above ratios are small provided that preprocessing is performed with suitably larger precision.
A Fast Parallel Cholesky Decomposition Algorithm for Tridiagonal Symmetric Matrices / I., BAR ON; B., Codenotti; Leoncini, Mauro. - In: SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. - ISSN 0895-4798. - STAMPA. - 18(1997), pp. 403-418.
Data di pubblicazione: | 1997 | |
Titolo: | A Fast Parallel Cholesky Decomposition Algorithm for Tridiagonal Symmetric Matrices | |
Autore/i: | I., BAR ON; B., Codenotti; Leoncini, Mauro | |
Autore/i UNIMORE: | ||
Rivista: | ||
Volume: | 18 | |
Pagina iniziale: | 403 | |
Pagina finale: | 418 | |
Codice identificativo ISI: | WOS:A1997WQ48400011 | |
Codice identificativo Scopus: | 2-s2.0-0031531915 | |
Citazione: | A Fast Parallel Cholesky Decomposition Algorithm for Tridiagonal Symmetric Matrices / I., BAR ON; B., Codenotti; Leoncini, Mauro. - In: SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. - ISSN 0895-4798. - STAMPA. - 18(1997), pp. 403-418. | |
Tipologia | Articolo su rivista |
File in questo prodotto:
Pubblicazioni consigliate

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