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

ТЕМА: СЫЗЫҚЛЫ АЛГОРИТМЛЕР. МАТРИЦАЛАР УСТИНДЕ ӘМЕЛЛЕР.
Бул темада матрицаларды көп ағымлы көбейтиўди көрип өтемиз. Бунда уш ағымлы цикл орнатыў жәрдеминде «бөлиў ҳәм ийелеў» алгоритминен пайдаланыўды уйренемиз.
Цикл орнатыў жәрдеминде матрицаларды көп ағымлы көбейтиниң әпиўайы алгоритми, SQUARE-MATRIX-MULTIPLY процедцра циклын паралеллестириў төмендегише жазылады.
P-SQUARE-MATRIX-MULTIPLY (A,B)
1 п = A. rows
2 С — жаңадан жаратылған п п өлшемли матрица
3 parallel for i= 1 to n
4 parallel for j= 1 to n
5 c_ij= 0
6 for к = 1 to n
7 c_ij = c_ij + a_ik  b_kj
8 return С
Бул алгоритмди анализлеў ушын, оны сериализациялаўшы Square-Matrix-Multiply алгоритми болып, Square-Matrix-Multiply ўақыт бойынша орынланыў алгоритмини Т₁(п)=0(п³) өлшеми менен көрсетиледи.
Көп ағымлы «бөлиў ҳәм ийелеў» алгоритми жәрдеминде матрицаларды көбейтиў
Келеси ўйренилетуғын Square-Matrix-Multiply-Recursive процедурасы, еки А ҳәм В пп өлшемли матрицаларын көбейтиўде параллелизм алгоритминен пайдаланылады, яғный ҳәр бир п/2п/2 ҳ.т.б. матрицаларға бөлинген турдеги избе-изликте есаплаўлардың қолланылыўы көп ағымлы алгоритмлердиң мысаллары бола алады.

Буны биз матрицаларды көбейтиўди төмендегише жазыўымыз мумкин

Бунда еки пп өлшемли матрицасын сегиз п/2п/2 өлшемли матрицалардың көбеймеси тўринде орынланады. Буны әмелге асырыўда көп ағымлы «бөлиў ҳәм ийелеў» алгоритми стратегиясын MATRIX-MULTIPLY-RECURSIVE'>SQUARE-MATRIX-MULTIPLY-RECURSIVE процедцрасы жәрдеминде есаплаймыз. Бундағы тийкарғы идиясы әдеттеги еки матрицаны көбейтиўге кететуғын компьютер ядын унемлеўге алып келиўши P-MATRIX-MULTIPLY-RECURSIVE процедцрасы ислеп шығылады.