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.

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

Powered by IRIS-about IRIS-Utilizzo dei cookie

 Copyright © 2021