Матрицалар устинде әмеллер

P-Matrix-Multiply-Recursive(C, А, В)

1. 
   п = A. rows
   
2. 
   if n == 1
   
3. 
   с₁₁ = а₁₁b₁₁
   
4. 
   else Т пп өлшемли матрицаларын cәўлелендиреди
   
5. 
   Бөлиў А, В, С ҳәм Т ның п/2п/2 ҳ.т.б. матрицаларға сәйкес турде бөлиниўи
   

A₁₁, А₁₂, А₂₁, А₂₂; В₁₁, В₁₂, В₂₁, В₂₂; С₁₁, С₁₂, С₂₁, С₂₂; Т₁₁, Т₁₂, Т₂₁, Т₂₂ .

6. 
   spawn P-Matrix-Multiply-Recursive_(_C_21'>P-Matrix-Multiply-Recursive_(_C_11'>P-Matrix-Multiply-Recursive(C₁₁, А₁₁,В₁₁)
   
7. 
   spawn P-Matrix-Multiply-Recursive(C₁₂, А₁₁,В₁₂)
   
8. 
   spawn P-Matrix-Multiply-Recursive(C₂₁, А₂₁,В₁₁)
   
9. 
   spawn P-Matrix-Multiply-Recursive(C₂₂, А₂₁,В₁₂)
   
10. 
    spawn P-Matrix-Multiply-Recursive(T₁₁, А₁₂,В₂₁)
    
11. 
    spawn P-Matrix-Multiply-Recursive(T ₁₂, А₁₂,В₂₂)
    
12. 
    spawn P-Matrix-Multiply-Recursive(T ₂₁, А₂₂,В₂₁)
    
13. 
    P-Matrix-Multiply-Recursive(T₁₂₂, А₂₂,В₂₂)
    
14. 
    sync
    
15. 
    parallel for i = 1 to n
    
16. 
    parallel for j = 1 to n
    
17. 
    c_ij= c_ij + t_ij
    

Бул алгоритмди анализлеў ушын, оны сериализациялаўшы P-Matrix-Multiply- RECURSIVE процедурасы болып, Square-Matrix-Multiply ўақыт бойынша орынланыў алгоритмини 8 п/2п/2 өлшемли матрицаларының орынланыўына тийкарланып M₁(n) ўақыт бойынша орынланыў алгоритмини төмендегише көрсетиледи.

M₁(n)=8 M₁(n/2)+(n²)= (n³)