Guruh: Bajardi: Tekshirdi: Toshkent 2021

O’zbekiston Respublikasi Axborot Texnologiyalari va Кommunikatsiyalarini Rivojlantirish Vazirligi

Muhammad Al-Xorazmiy nomidagi

Toshkent Axborot Texnologiyalari Universiteti.

MUSTAQIL ISH

Mavzu: Matritsalar bilan ishlash.

Guruh: _______________
Bajardi:________________
Tekshirdi:________________

Toshkent 2021

Reja:

1. 
   Matritsalar bilan ishlash.
   
2. 
   Kvadrat bo'lmagan matritsalar
   
3. 
   Kvadrat bo'lmagan matritsalar
   
4. 
   Xulosa
   
5. 
   Foydalanilgan adabiyotlar
   

Matritsalarni har xil turdagi apparatlar, shu jumladan, ko'paytirish uchun juda ko'p turli xil algoritmlar ishlab chiqilgan parallel va tarqatildi hisoblash ishlari bir nechta protsessorlarga (ehtimol tarmoq orqali) tarqaladigan tizimlar.

Matritsani ko'paytirishning matematik ta'rifini bevosita qo'llash algoritmni beradi vaqt talab etadi tartibida n3 ikkitasini ko'paytirish n × n matritsalar (Θ (n3) yilda katta O yozuvlari). Matritsalarni ko'paytirish uchun zarur bo'lgan vaqtni yaxshiroq asimptotik chegaralar 60-yillarda Strassen ishlaganidan beri ma'lum bo'lgan, ammo optimal vaqt nima ekanligi hali ham noma'lum (ya'ni, muammoning murakkabligi bu).
Takroriy algoritm
The matritsani ko'paytirishning ta'rifi agar shunday bo'lsa C = AB uchun n × m matritsa A va an m × p matritsa B, keyin C bu n × p yozuvlar bilan matritsa
v men j = ∑ k = 1 m a men k b k j {displaystyle c_ {ij} = sum _ {k = 1} ^ {m} a_ {ik} b_ {kj}} .
Bundan oddiy algoritm tuzilishi mumkin, u indekslarni ko'rib chiqadi men 1 dan n va j 1 dan p, ichki o'rnatilgan pastadir yordamida yuqoridagilarni hisoblash:
Ushbu algoritm oladi vaqt Θ (nmp) (ichida.) asimptotik yozuv).[1] Maqsadida umumiy soddalashtirish algoritmlarni tahlil qilish kirishlarning barchasi kvadrat kattalikdagi matritsalar deb taxmin qilishdir n × n, bu holda ish vaqti Θ (n3), ya'ni o'lchamdagi kubik.[2]
Kesh harakati

Qator va ustunli buyruqlar tasviri
Matritsani ko'paytirishda uchta tsiklni o'zboshimchalik bilan almashtirish mumkin, bu to'g'ri yoki asimptotik ish vaqtiga ta'sir qilmaydi. Biroq, buyurtma amaliy ishlarga sezilarli ta'sir ko'rsatishi mumkin xotiraga kirish naqshlari va kesh algoritmdan foydalanish;[1]qaysi tartib eng yaxshi bo'lishi, shuningdek, matritsalarning saqlanishiga bog'liq asosiy tartib, ustunli buyurtma yoki ikkalasining aralashmasi.
Xususan, a-ning idealizatsiyalangan holatida to'liq assotsiativ kesh iborat M bayt va b kesh satrida bayt (ya'ni M/b kesh satrlari), yuqoridagi algoritm uchun eng maqbul hisoblanadi A va B qator tartibida saqlanadi. Qachon n > M/b, ichki tsiklning har bir iteratsiyasi (bir qatorda bir vaqtning o'zida siljish A va ning ustuni B) elementiga kirishda keshni yo'qotishga olib keladi B. Bu shuni anglatadiki, algoritm paydo bo'ladi Θ (n3) kesh eng yomon holatda o'tkazib yuboradi. 2010 yildan boshlab[yangilash], protsessorlar bilan taqqoslaganda xotiralar tezligi shundan iboratki, katta hisoblangan matritsalar uchun ish vaqtini haqiqiy hisob-kitoblarga emas, balki kesh o'tkazib yuboradi.[3]
Uchun takroriy algoritmning optimal varianti A va B asosiy tartibda a plitka bilan qoplangan versiya, bu erda matritsa aniq kvadrat kattalikdagi plitkalarga bo'linadi √M tomonidan √M:[3][4]
Idealizatsiya qilingan kesh modelida ushbu algoritm faqat o'z ichiga oladi Θ (n3/b √M) keshni o'tkazib yuborish; bo'luvchi b √M zamonaviy mashinalarda bir nechta kattalik buyurtmalarini tashkil etadi, shuning uchun keshni o'tkazib yubormaslik o'rniga, haqiqiy hisob-kitoblar ish vaqtini boshqaradi.[3]
Algoritmni ajrating va yutib oling
Promoted Content
Takrorlanadigan algoritmga alternativa bu algoritmni ajratish va yutish matritsani ko'paytirish uchun. Bu quyidagilarga asoslanadi blokirovka qilish
C = ( C 11 C 12 C 21 C 22 ) , A = ( A 11 A 12 A 21 A 22 ) , B = ( B 11 B 12 B 21 B 22 ) {displaystyle C = {egin {pmatrix} C_ {11} & C_ {12} C_ {21} & C_ {22} end {pmatrix}} ,, A = {egin {pmatrix} A_ {11} & A_ {12} A_ {21} & A_ {22} end {pmatrix}} ,, B = {egin {pmatrix} B_ {11} va B_ {12} B_ {21} va B_ {22} end {pmatrix}}} ,
o'lchamlari ikkitadan kuchga ega bo'lgan, ya'ni shakllar bo'lgan barcha kvadrat matritsalar uchun ishlaydigan 2n × 2n kimdir uchun n. Matritsa mahsuloti hozir
( C 11 C 12 C 21 C 22 ) = ( A 11 A 12 A 21 A 22 ) ( B 11 B 12 B 21 B 22 ) = ( A 11 B 11 + A 12 B 21 A 11 B 12 + A 12 B 22 A 21 B 11 + A 22 B 21 A 21 B 12 + A 22 B 22 ) {displaystyle {egin {pmatrix} C_ {11} & C_ {12} C_ {21} & C_ {22} end {pmatrix}} = {egin {pmatrix} A_ {11} & A_ {12} A_ {21} & A_ {22} end {pmatrix}} {egin {pmatrix} B_ {11} & B_ {12} B_ {21} & B_ {22} end {pmatrix}} = {egin {pmatrix} A_ {11} B_ {11 } + A_ {12} B_ {21} va A_ {11} B_ {12} + A_ {12} B_ {22} A_ {21} B_ {11} + A_ {22} B_ {21} va A_ {21} B_ {12} + A_ {22} B_ {22} end {pmatrix}}}
submatrices juftligini sakkiz marta ko'paytirishdan iborat bo'lib, keyin qo'shilish bosqichi. Bo'lish va yutish algoritmi kichikroq ko'paytmalarni hisoblab chiqadi rekursivyordamida skalar ko'paytmasi v11 = a11b11 uning asosiy ishi sifatida.
Funktsiyasi sifatida ushbu algoritmning murakkabligi n takrorlanish bilan beriladi[2]
T ( 1 ) = Θ ( 1 ) {displaystyle T (1) = Theta (1)} ;
T ( n ) = 8 T ( n / 2 ) + Θ ( n 2 ) {displaystyle T (n) = 8T (n / 2) + Theta (n ^ {2})} ,
o'lchamdagi matritsalar bo'yicha sakkizta rekursiv qo'ng'iroqlarni hisobga olish n/2 va Θ (n2) natijada olingan matritsalarning to'rt juftligini sarhisob qilish. Ning qo'llanilishi bo'linish va zabt etish takrorlanishining master teoremasi echimga ega bo'lish uchun ushbu rekursiyani ko'rsatadi Θ (n3), takrorlanadigan algoritm bilan bir xil.[2]
Kvadrat bo'lmagan matritsalar
Ushbu algoritmning ixtiyoriy shakllarning matritsalarida ishlaydigan va amalda tezroq bo'lgan varianti[3] matritsalarni to'rtta submatrikaning o'rniga ikkiga ajratadi, quyidagicha.[5]Matritsani ajratish endi uni teng o'lchamdagi ikki qismga bo'linishni yoki g'alati o'lchamlarda iloji boricha teng o'lchamlarga yaqin bo'lishni anglatadi.
Kirish: matritsalar A hajmi n × m, B hajmi m × p.
Asosiy ish: agar maksimal (n, m, p) ostonadan past bo'lsa, dan foydalaning ro'yxatdan o'tmagan takrorlanadigan algoritmning versiyasi.
Rekursiv holatlar:
Agar maksimal (n, m, p) = n, Split A gorizontal ravishda:
C = ( A 1 A 2 ) B = ( A 1 B A 2 B ) {displaystyle C = {egin {pmatrix} A_ {1} A_ {2} end {pmatrix}} {B} = {egin {pmatrix} A_ {1} B A_ {2} Bend {pmatrix}}}
Boshqa, agar shunday bo'lsa maksimal (n, m, p) = p, Split B vertikal:
C = A ( B 1 B 2 ) = ( A B 1 A B 2 ) {displaystyle C = A {egin {pmatrix} B_ {1} & B_ {2} end {pmatrix}} = {egin {pmatrix} AB_ {1} & AB_ {2} end {pmatrix}}}
Aks holda, maksimal (n, m, p) = m. Split A vertikal va B gorizontal ravishda:
C = ( A 1 A 2 ) ( B 1 B 2 ) = A 1 B 1 + A 2 B 2 {displaystyle C = {egin {pmatrix} A_ {1} & A_ {2} end {pmatrix}} {egin {pmatrix} B_ {1} B_ {2} end {pmatrix}} = A_ {1} B_ {1} + A_ {2} B_ {2}}
Kesh harakati
Rekrursiv matritsani ko'paytirishning kesh o'tkazib yuborish tezligi a bilan bir xil plitka bilan qoplangan takrorlanadigan versiya, ammo bu algoritmdan farqli o'laroq, rekursiv algoritm keshni unutish:[5] keshning optimal ishlashini ta'minlash uchun sozlash parametri talab qilinmaydi va u o'zini yaxshi tutadi ko'p dasturlash kesh hajmini egallaydigan boshqa jarayonlar tufayli kesh hajmi samarali dinamik bo'lgan muhit.[3](Oddiy iteratsion algoritm keshni ham unutmaydi, ammo matritsa sxemasi algoritmga moslashtirilmagan bo'lsa, amalda juda sekinroq.)
Ushbu algoritm bilan ishlaydigan keshni o'tkazib yuborish soni M har bir o'lchamdagi ideal kesh satrlari b bayt, chegaralangan[5]:13
Θ ( m + n + p + m n + n p + m p b + m n p b M ) {displaystyle Theta chapda (m + n + p + {frac {mn + np + mp} {b}} + {frac {mnp} {b {sqrt {M}}}} ight)}
Sub-kub algoritmlari
Promoted Content


Eng past ω shunday qilib matritsani ko'paytirish ma'lum O(nω), vaqtga qarshi fitna uyushtirdi.
Algoritmlar to'g'ridan-to'g'ri vaqtga qaraganda yaxshiroq ishlash vaqtini ta'minlaydigan mavjud. Birinchi bo'lib topilgan Strassen algoritmitomonidan ishlab chiqilgan Volker Strassen 1969 yilda va ko'pincha "tezkor matritsani ko'paytirish" deb nomlangan. Bu ikkitasini ko'paytirish usuliga asoslangan 2 × 2- qo'shimcha qo'shish va ayirish operatsiyalari hisobiga atigi 7 marta ko'paytirishni talab qiladigan matritsalar (odatdagi 8 o'rniga). Buni rekursiv ravishda qo'llash multiplikatsion narxga ega algoritmni beradi O ( n jurnal 2 ⁡ 7 ) ≈ O ( n 2.807 ) {displaystyle O (n ^ {log _ {2} 7}) taxminan O (n ^ {2.807})} . Strassen algoritmi ancha murakkab va raqamli barqarorlik sodda algoritm bilan taqqoslaganda,[6]ammo bu holatlarda tezroq bo'ladi n > 100 yoki shunday[1] kabi bir nechta kutubxonalarda paydo bo'ladi BLAS.[7] Kabi aniq domenlarga nisbatan katta matritsalar uchun juda foydali cheklangan maydonlar, bu erda raqamli barqarorlik muammo emas.
Joriy O(nk) ma'lum bo'lgan eng past ko'rsatkichga ega algoritm k ning umumlashtirilishi Misgar - Winograd algoritmi ning asimptotik murakkabligiga ega O(n2.3728639), Fransua Le Gall tomonidan.[8] Le Gall algoritmi va unga asoslangan mischi - Winograd algoritmi Strassen algoritmiga o'xshaydi: ikkitasini ko'paytirish usuli o'ylab topilgan k × k-dan kam bo'lgan matritsalar k3 ko'paytmalar va bu usul rekursiv tarzda qo'llaniladi. Biroq, tomonidan yashiringan doimiy koeffitsient Big O notation juda katta, bu algoritmlar faqat hozirgi kompyuterlarda ishlash uchun juda katta bo'lgan matritsalar uchun foydalidir.[9][10]
Ikkisini ko'paytirish uchun har qanday algoritm bo'lgani uchun n × n-matrisalar barchasini qayta ishlashi kerak 2n2 yozuvlari, ning asimptotik pastki chegarasi mavjud Ω (n2) operatsiyalar. Raz ning pastki chegarasini isbotladi Ω (n2 log (n)) haqiqiy yoki murakkab sonlar bo'yicha cheklangan koeffitsientli arifmetik davrlar uchun.[11]
Kon va boshq. Strassen va Misgar-Winograd algoritmlari kabi usullarni butunlay boshqacha qilib qo'ying guruh-nazariy kontekstida, nomutanosiblik xususiyatini qondiradigan cheklangan guruhlarning uchta to'plamidan foydalangan holda uch baravar mahsulot xususiyati (TPP). Ular shuni ko'rsatadiki, agar oilalar gulchambar mahsulotlari ning Abeliya guruhlari nosimmetrik guruhlar bilan TPP ning bir vaqtning o'zida versiyasi bilan kichik uchlik oilalarini amalga oshiradi, so'ngra kvadratik murakkabligi bilan matritsani ko'paytirish algoritmlari mavjud.[12][13] Aksariyat tadqiqotchilar bu haqiqatan ham shunday deb hisoblashadi.[10] Biroq, Alon, Shpilka va Kris Umans yaqinda shuni ko'rsatdiki, tezkor matritsani ko'paytirishni nazarda tutadigan ushbu taxminlarning ba'zilari boshqa mantiqiy gipoteza bilan mos kelmaydi, kungaboqar gumoni.[14]
Freivalds algoritmi oddiy Monte-Karlo algoritmi berilgan matritsalar A, B va C, tekshiradi Θ (n2) vaqt agar AB = C.
Parallel va taqsimlangan algoritmlar
Umumiy xotira parallelligi
The algoritmni ajratish va yutish oldinroq chizilgan bo'lishi mumkin parallel ikki yo'l bilan umumiy xotira multiprotsessorlari. Bu sakkizta rekursiv matritsaning ko'paytmasi
( A 11 B 11 + A 12 B 21 A 11 B 12 + A 12 B 22 A 21 B 11 + A 22 B 21 A 21 B 12 + A 22 B 22 ) {displaystyle {egin {pmatrix} A_ {11} B_ {11} + A_ {12} B_ {21} va A_ {11} B_ {12} + A_ {12} B_ {22} A_ {21} B_ {11} + A_ {22} B_ {21} va A_ {21} B_ {12} + A_ {22} B_ {22} end {pmatrix}}}
to'rtta yig'ilish kabi bir-biridan mustaqil ravishda bajarilishi mumkin (garchi algoritm yig'indilarni bajarishdan oldin ko'paytmalarni "birlashtirish" kerak bo'lsa). Masalaning to'liq parallelligidan foydalanib, ifodalash mumkin bo'lgan algoritm olinadi vilka – qo'shilish uslubi psevdokod:[15]
.
Bu yerda, vilka hisoblash funktsiyasining qolgan qismi bilan parallel ravishda bajarilishi mumkin bo'lgan signal beruvchi kalit so'z qo'shilish ilgari barcha "vilkalar" hisob-kitoblarning bajarilishini kutadi. bo'lim o'z maqsadiga faqat ko'rsatgich manipulyatsiyasi orqali erishadi.
Ushbu algoritm a muhim yo'l uzunligi ning Θ (log.)2 n) qadamlar, ya'ni cheksiz ko'p protsessorga ega bo'lgan ideal mashinada shuncha vaqt talab etiladi; shuning uchun u maksimal darajada mumkin tezlikni oshirmoq ning Θ (n3/ log2 n) har qanday haqiqiy kompyuterda. Algoritm ma'lumotlarning vaqtincha matritsaga ko'chirilishiga xos bo'lgan aloqa xarajatlari tufayli amaliy emas T, ammo amaliyroq variantga erishiladi Θ (n2) vaqtinchalik matritsani ishlatmasdan tezlashtirish.[15]

Matritsani ko'paytirishni blokirovka qilish. 2D algoritmida har bir protsessor bitta submatriks uchun javobgardir C. 3D algoritmida har bir submatrikaning juftligi A va B ko'paytiriladi, bitta protsessorga beriladi.
Muloqotdan qochish va tarqatilgan algoritmlar
Ierarxik xotiraga ega zamonaviy arxitekturalarda kirish matritsasi elementlarini yuklash va saqlash xarajatlari arifmetik xarajatlarga ustunlik qiladi. Bitta mashinada bu RAM va kesh o'rtasida o'tkaziladigan ma'lumotlar miqdori, tarqatilgan xotira ko'p tugunli mashinada esa tugunlar o'rtasida o'tkaziladigan miqdor; har qanday holatda ham u aloqa o'tkazuvchanligi. Uchta ichki ko'chadan foydalanadigan sodda algoritmdan foydalaniladi Ω (n3) aloqa tarmoqli kengligi.
Cannon algoritmi, deb ham tanilgan 2D algoritmi, a muloqotdan qochish algoritmi har bir kirish matritsasini elementlari kattaligi submatritsasi bo'lgan blok matritsasiga ajratadi √M/3 tomonidan √M/3, qayerda M tezkor xotira hajmi.[16] Keyinchalik sodda algoritm blok matritsalarida ishlatiladi, submatrikalarning mahsulotlarini to'liq tezkor xotirada hisoblash. Bu aloqa o'tkazuvchanligini kamaytiradi O(n3/√M), bu asimptotik jihatdan maqbul (algoritmlarni bajarish uchun Ω (n3) hisoblash).[17][18]
Bilan tarqatilgan muhitda p a da joylashgan protsessorlar √p tomonidan √p 2D mash, natijaning bitta submatriksi har bir protsessorga tayinlanishi mumkin va har bir protsessor uzatishda mahsulotni hisoblash mumkin. O(n2/√p) so'zlar, bu har bir tugun minimal saqlanishini nazarda tutgan holda asimptotik jihatdan maqbuldir O(n2/p) elementlar.[18] Bu tomonidan yaxshilanishi mumkin 3D algoritmi, protsessorlarni ikkita kubikli mashga joylashtirib, ikkita kirish submatrisasining har bir mahsulotini bitta protsessorga tayinlaydi. Natijada submatrices har bir satrda qisqartirishni amalga oshirish orqali hosil bo'ladi.[19] Ushbu algoritm uzatadi O(n2/p2/3) asimptotik jihatdan maqbul bo'lgan har bir protsessor uchun so'zlar.[18] Biroq, bu har bir kirish matritsasi elementini takrorlashni talab qiladi p1/3 marta, va shuning uchun omil talab etiladi p1/3 Kirishlarni saqlash uchun zarur bo'lganidan ko'proq xotira. Ushbu algoritmni ish vaqtini yanada qisqartirish uchun Strassen bilan birlashtirish mumkin.[19] "2.5D" algoritmlari xotiradan foydalanish va aloqa o'tkazuvchanligi o'rtasida uzluksiz almashinuvni ta'minlaydi.[20] Kabi zamonaviy taqsimlangan hisoblash muhitlarida MapReduce, ko'paytirishning ixtisoslashgan algoritmlari ishlab chiqilgan.[21]
Meshlar uchun algoritmlar

Matritsani ko'paytirish 2 n-1 bosqichda ikkita n × n matritsa uchun o'zaro faoliyat simli mash ustida yakunlandi.
Ko'paytirish uchun turli xil algoritmlar mavjud meshlar. Ikkisini ko'paytirish uchun n×n 2D yordamida standart ikki o'lchovli mashda Cannon algoritmi, ko'paytmani 3 ga to'ldirish mumkinn-2 qadam, lekin bu takroriy hisoblash uchun bu sonning yarmiga kamayadi.[22] Ikkala matritsadagi ma'lumotlar bir vaqtning o'zida kelmasligi sababli nol bilan to'ldirilishi kerakligi sababli standart massiv samarasiz.
Natija ikki qavatli o'zaro faoliyat simli mashda ham tezroq bo'ladi, bu erda faqatgina 2 tan-1 qadam kerak.[23] 100% samaradorlikka olib keladigan takroriy hisob-kitoblar uchun ishlash yanada yaxshilanadi.[24] O'zaro faoliyat simli tarmoq majmuasi tekis bo'lmagan (ya'ni ko'p qatlamli) ishlov berish strukturasining alohida holati sifatida qaralishi mum

Xulosa
Xulosa qilib aytganda algoritmlar to'g'ridan-to'g'ri vaqtga qaraganda yaxshiroq ishlash vaqtini ta'minlaydigan mavjud. Birinchi bo'lib topilgan Strassen algoritmitomonidan ishlab chiqilgan Volker Strassen 1969 yilda va ko'pincha "tezkor matritsani ko'paytirish" deb nomlangan. Bu ikkitasini ko'paytirish usuliga asoslangan 2 × 2- qo'shimcha qo'shish va ayirish operatsiyalari hisobiga atigi 7 marta ko'paytirishni talab qiladigan matritsalar (odatdagi 8 o'rniga). Buni rekursiv ravishda qo'llash multiplikatsion narxga ega algoritmni beradi.

Foydalanilgan adabiyotlar

1. 
   Skiena, Stiven (2008). "Saralash va qidirish". Algoritmlarni tuzish bo'yicha qo'llanma. Springer. pp.45–46, 401–403. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
   
2. 
   Kormen, Tomas H.; Leyzerson, Charlz E.; Rivest, Ronald L.; Shteyn, Klifford (2009) [1990]. Algoritmlarga kirish (3-nashr). MIT Press va McGraw-Hill. 75-79 betlar. ISBN 0-262-03384-4.
   
3. 
   rasinghe, Saman; Leyzerson, Charlz (2010). "6.172 Dasturiy ta'minot tizimlarining ishlash muhandisligi, 8-ma'ruza".. MIT OpenCourseWare. Massachusets texnologiya instituti. Olingan 27 yanvar 2015.
   
4. 
   Lam, Monika S.; Rotberg, Edvard E.; Bo'ri, Maykl E. (1991). Keshning ishlashi va bloklangan algoritmlarni optimallashtirish. Xalqaro Konf. Dasturlash tillari va operatsion tizimlarini me'moriy qo'llab-quvvatlash (ASPLOS) to'g'risida.
   
5. 
   Prokop, Xarald (1999). Keshni unutadigan algoritmlar (PDF) (Magistr). MIT.
   
6. 
   Miller, Uebb (1975), "Hisoblash murakkabligi va son barqarorligi", SIAM yangiliklari, 4 (2): 97–107, CiteSeerX 10.1.1.148.9947, doi:10.1137/0204009
   
7. 
   Matbuot, Uilyam H.; Flannery, Brian P.; Teukolskiy, Shoul A.; Vetterling, Uilyam T. (2007). Raqamli retseptlar: Ilmiy hisoblash san'ati (3-nashr). Kembrij universiteti matbuoti. p.108. ISBN 978-0-521-88068-8.