Accès libre

Parallel Solution of Hierarchical Symmetric Positive Definite Linear Systems

José I. Aliaga
José I. Aliaga
, 
Rocío Carratalá-Sáez
Rocío Carratalá-Sáez
 et 
Enrique S. Quintana-Ortí
Enrique S. Quintana-Ortí
   | 22 juin 2017
Applied Mathematics and Nonlinear Sciences's Cover Image
À propos de cet article
Article précédent
Article suivant
Citez
Publié en ligne: 22 juin 2017
Pages: 201 - 212
Reçu: 06 mars 2017
Accepté: 22 juin 2017
DOI: https://doi.org/10.21042/AMNS.2017.1.00017
Mots clés
© 2017 José I. Aliaga, Rocío Carratalá-Sáez, Enrique S. Quintana-Ortí, published by Sciendo
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Fig. 1

Block cluster tree obtained from the index set I = {1, 2, 3,...,12}.
Block cluster tree obtained from the index set I = {1, 2, 3,...,12}.

Fig. 2

ℋ-matrix obtained by applying the partitioning defined by the block cluster tree in Figure 1 over an 12 × 12 matrix.
ℋ-matrix obtained by applying the partitioning defined by the block cluster tree in Figure 1 over an 12 × 12 matrix.

Fig. 3

Operations and data dependencies in the first iteration (k = 1) of the BRL algorithm for the Cholesky factorization.
Operations and data dependencies in the first iteration (k = 1) of the BRL algorithm for the Cholesky factorization.

Fig. 4

Operations and data dependencies in the generalization of the BRL algorithm for the ℋ-Cholesky factorization.
Operations and data dependencies in the generalization of the BRL algorithm for the ℋ-Cholesky factorization.

Fig. 5

Performance of the task-parallel ℋ-Cholesky factorization of a matrix of order 5,000 using OpenMP and OmpSs in the Intel E5-2603v3 server using 4, 8 and 12 threads/cores.
Performance of the task-parallel ℋ-Cholesky factorization of a matrix of order 5,000 using OpenMP and OmpSs in the Intel E5-2603v3 server using 4, 8 and 12 threads/cores.

Fig. 6

Performance of the task-parallel ℋ-Cholesky factorization of a matrix of order 10,000 using OpenMP and OmpSs in the Intel E5-2603v3 server using 4, 8 and 12 threads/cores.
Performance of the task-parallel ℋ-Cholesky factorization of a matrix of order 10,000 using OpenMP and OmpSs in the Intel E5-2603v3 server using 4, 8 and 12 threads/cores.

Sequence of operations for the ℋ-Cholesky factorization of A:
O1 : A1,1=L1,1L1,1T$\begin{array}{} = {L_{1,1}}L_{1,1}^T \end{array}$
O2 : L2,1:= A2,1L1,1−T$\begin{array}{} {\rm{: = }}{A_{2,1}}L_{1,1}^{ - T} \end{array}$
O3 : A2,2:= A2,2−L2,1⋅L2,1T$\begin{array}{} {\rm{: = }}{A_{2,2}} - {L_{2,1}} \cdot L_{2,1}^T \end{array}$
O4 : A2,2= L2,2L2,2T$\begin{array}{} {\rm{ = }}{L_{2,2}}L_{2,2}^T \end{array}$
O5 : L3:4, 1:2:= A3:4,1:2L1:2,1:2−T$\begin{array}{} {\rm{: = }}{A_{3:4,1:2}}L_{1:2,1:2}^{ - T} \end{array}$
O6 : A3:4, 3:4:= A3:4,3:4−L3:4,1:2⋅L3:4,1:2T$\begin{array}{} {\rm{: = }}{A_{3:4,3:4}} - {L_{3:4,1:2}} \cdot L_{3:4,1:2}^T \end{array}$
O7 : A3, 3=L3,3L3,3T$\begin{array}{} = {L_{3,3}}L_{3,3}^T \end{array}$
O8 : L4, 3:= A4,3L3,3−T$\begin{array}{} {\rm{: = }}{A_{4,3}}L_{3,3}^{ - T} \end{array}$
O9 : A4, 4:= A4,4−L4,3⋅L4,3T$\begin{array}{} {\rm{: = }}{A_{4,4}} - {L_{4,3}} \cdot L_{4,3}^T \end{array}$
O10 : A4, 4=L4,4L4,4T$\begin{array}{} = {L_{4,4}}L_{4,4}^T \end{array}$

Configurations for the experimental evaluation of the ℋ − Cholesky factorization.

nnlBlock granularity in each level
5,0002345,000, 1005,000, 500, 1005,000, 2,500, 1,250, 250
10,00023410,000, 50010,000, 500, 10010,000, 1,000, 500, 100

BRL algorithm for the Cholesky factorization.

Require: A ∊ ℝn×n
  1:fork = 1, 2,...,ntdo
  2:     Akk=LkkLkkT$\begin{array}{} {A_{kk}} = {L_{kk}}L_{kk}^T \end{array}$
  3:       fori = k + 1, k + 2...,ntdo
  4:           Lik := AikLkk−T$\begin{array}{} {L_{ik}}{\rm{ : = }}{A_{ik}}L_{kk}^{ - T} \end{array}$
  5:       end for
  6:       fori = k + 1, k + 2,..., ntdo
  7:           forj = k + 1, k + 2,...,ido
  8:                 Aij := Aij−Lik⋅LkjT$\begin{array}{} {A_{ij}}{\rm{ : = }}{A_{ij}} - {L_{ik}} \cdot L_{kj}^T\end{array}$
  9:       end for
10:     end for
11:end for
eISSN:
2444-8656
Langue:
Anglais
Périodicité:
2 fois par an
Sujets de la revue:
Life Sciences, other, Mathematics, Applied Mathematics, General Mathematics, Physics
RSS Feed de la revue