Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

R[i,j]=0 for k=l to b do

R[i,j>Rti.J]+G[i.k]*H[k,j] end for k end for j end for i

Биринчи қарашда бу минимал ҳажмдаги иш, икки матрицани қайта кўпайтириш зарур. Аммо олимлар буни минимал иш эканлигини исботлаша олмади ва натижада улар бошқа алгоритмларни топишди ва улар жуда қулай бўлган кўпайтириш матрицаларидир.

Матрицаларни Виноград усулида кўпайтириш
Агар икки матрица кўпайтмаларининг натижасига қарасак, ҳар бир элемент унга аҳамиятли бўлган скаляр кўпайтмага муносиб қатор ва устун матрицаларга асос қилиб олинади. Биз ишнинг олдиндан бажарилишига имкон берувчи дастлабки қайта ишлаш кўпайтмасини сезишимиз мумкин.
Икки векторни қараймиз:
V = (v₁,v₂,v₃,v₄) и W=(w₁,w₂,w₃,w₄)
Уларниг скаляр кўпайтмаси
V • W = v₁w₁ + v₂w₂ + v₃w₃ + v₄w₄ га тенг.
Бу тенгликни қуйидаги кўринишда ёзишимиз мумкин:
V • W = (v₁ + w₂)(v₂ + w₁) + (v₃ + w₄)(v₄ + w₄)
— v₁v₂ — v₃v₄ — w₁w₂ — w₃w₄.
Китобхон охирги икки ифоданинг эквивалентлигига осонгина ишонади. Балки иккинчи ифода биринчи ифодага қараганда кўпроқ ишни талаб қилади: тўртта кўпайтириш ўрнига биз олтита эканлигини, 3та қўшилувчи ўрнига эса 10 тасини кўрамиз. Бу ифоданинг ўнг қисми охиридаги тенглик дастлабки қайта ишлаш имконини бергани аниқ эмас: унинг қисмларини ҳар бир матрица қаторининг ва иккинчи матрицанинг ҳар бир устунини олдиндан ҳисоблаш ва эслаб қолиш мумкин. G матрицанинг а х b ҳажмдаги Н матрицанинг b x с ҳажмига кўпайтириш учун Винограднинг тўлиқ алгоритми шундай кўринишга эга. Натижа а х с ҳажмдаги R матрицага ёзилади.
d=b/2
// ҳисоблаш rowFactors для G
for i=l to a do
rowFactor[i]=G[i,1]*G[i,2]
for j=2 to d do
rowFactor[i]=rowFactor[i]+G[i,2j-1]*G[i,2j]
end for j end for i
// ҳисоблаш columnFactors для Н for i=l to с do
columnFactor[i]=H[1,i]*H[2,i]
for j=2 to d do
columnFactor[i]=columnFactor[i]+H[2j-1,i] *H[2j,i]
end for j end for i
// матрицаларни ҳисоблаш R for i=l to a do for j=l to с do
R[i,j]=-rowFactor[i]-columnFactor[j J for k=l to d do
R[i,j>RCi»JJ ⁺ (Gti,2k-l]+H[2k,j])*(G[i,2k]+H[2k-l,j]) end for к ena^udry ~ end for i
// умумий ҳажмдаги тоқ кўпҳадларни қўшиш if (2*(Ъ/2) /= Ъ)
then for i=l to a do for j=l to с do
R[i,j]-RCi,j]+G[i,b]*H[b,j]
end for j end for i end if