Тема: полиномла матрицалар устинде әмеллер. Матрицаларды көп ағымлы көбейтиў

if n == 1

с₁₁ = а₁₁b₁₁

else Т пп өлшемли матрицаларын cәўлелендиреди

Бөлиў А, В, С ҳәм Т ның п/2п/2 ҳ.т.б. матрицаларға сәйкес турде бөлиниўи

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

6. 
   spawn 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³)


Polinomlar
Uliwmaliqko’pag’zalilardin’ ko’rinisi
р(х) = а_nхⁿ + a_n-1 x^n-1 + a_n-2x^n-2 + … + а₂х² + a₁х + a₀
a_n, ……., a₀koeffitsenleribelgiliha’mmassivgejazilg’andepboljaymiz. Bulsonian’latadiko’beymeniesaplawsuhintekbirg’anama’nis x tin’ ma’nisbolipprogrammana’tiyjesi x noqattako’beymenin’ ma’nisiboliwkerek. Esaplawdin’ standartalgoritmnin’ a’piwayi:
Polinom (x)
x; ko’pag’zalilardin’ ko’beymesinesaplapshig’atinnoqat
result = a [0] + a [l] * x
xPower = x
for(inti = 2; i xPower = xPower * x;
result = result + a [i] * xPower
return result;

For cikilda n-1 ma’rteorinlang’anekiko’beyme bar. Bunnanbasqacikldanaldinbirko’beymea’melgeasiriladi, sonin’ ushunko’beymenin’ uluwmasani 2n-1. Cikldabirqosimshaha’mbirqosimshacikldanaldina’melgeasiriladi, sonliqdanqosimshalardin’ uluwmasani n ma’rteboladi.

Qandaydabirbelgilima’niskeiyebolg’anmonomiyalarjiyindisietipjazilg’anko’beytirilgensanlardin’ sheshimitu’rliusillar bar. Joqarida’rejedegiten’lemelerdiesaplawlardaqolaylibolmaydi. BiraqbuljerdeGornersxemasi bar bolip, bundaan’latpanin’ korenina’piwayitu’rdeaniqlawg’aboladi.
Gornersxemasinto’mendegisheanalizlengen.

Gornerta’repinenusung’analgoritmnegizindeitaliyaliqmatematikha’mmeditsinashipakeri Paola Ruffinita’repinenaldinoylaptabilg’an. Olbirinshibolipbesinshida’rejedegian’latpadaradikalditabiwmu’mkinemesekeninaniqladi. Biraqonin’ bulga’pineko’plepqarama-qarsinaraziliqlar bar bolip, bulalimlardin’ matematikdu’nyasita’repinenqabiletiwgeimkaniyatbermedi. 1819 jildainglizUilyamJorjGornero’zjaziwlaritiykarindapolinomiyakorenlerdishamalaptabiwusilinko’rsetti. Bulmaqalaja’miyetta’repinenbaspadanshiqtiha’mRuffini-Gornerusilidepataldi. U’shinshida’rejeliten’lemenisheshiwushin
x3 + 6x - x - 30 = 0 misaletipko’remiz. Bunnanbasqaten’lemenin’ koreniekige ten’ ekenligibelgili. Endibasqakorenlerintabiwkerek. Bulto’mendegisheaniqlanadi. Eger ko’beymeni p(x) tin’ koreni x0 bolsin, onda p(x) x minus x no’lha’mbasqako’psanli h(x) pariqlaresabinapaydalaniwmu’mkin.,olardin’ da’rejesibirkishiboladi. Kerekliko’beytiwa’dettebo’liniwusilija’rdemindea’melgeasiriladi. Ko’ripshig’ilg’an missal to’mendegisheboladi: (x3 + 6x - x - 30) / (x - x2).Bo’liw en’ jaqsimu’yeshpenena’melgeasiriladi. Na’tiyje: x2 + 8x + 15.Sondayetipqa’legenan’latpa(x - 2) * (x2 + 8x + 15) = 0qaytajaziwmu’mkin. Keyinlewten’lemenin’ sheshimintabiwushinto’mendegisheorinlawkerekboladi: ten’lemenin’ birinshima’nisinno’lgeten’lestiripkorenditabiw: x-2=0. Sondayetip x=2bul da sha’rttenkelipshig’adi. Kvadratten’lemenin’ ekinshida’wirinno’lgeten’lestiripsheshiwgeboladi: x2 + 8x + 15 = 0.KorendidiskriminatyamasaVetnamformulasija’rdemindetabiwg’a da boladi. Endibizde (x + 3) * (x + 5) = 0, yag’niybir x u’shke, eki x minus beske ten’ depjazamiz.
Gornerdisxemako’rinisinbasqamisaldako’rsetipbersem: