
maatrika gunakaaram yokka ganana sanklishtata

saiddhaantika computer saastramlo, maatrika gunakaaram yokka ganana sanklishtata maatrika gunakaaram yokka operation entha twaragaa nirvahinchavachho nirdesistundi. sankhya sarala beejaganitam mariyu optimisation kosam saiddhaantika mariyu sankhya algorithamlalo maatrika gunakaara algorithamlu kendra upasuutram, kabatti saraina samayanni kanugonadam anedi pradhana aacharanaatmaka auchityam kaligi untundi.
maatrika gunakaaram yokka ganita nirvachananni neerugaa vartimpajeyadam anedi aaa kshetrampai rendu maatrikalanu guninchadaaniki kshetra karyakalapalu avasaramayye oka algorithamnu istundi (pedda sangnaamaanamlo). aascharyakaramgaa, eee suutigaa "school book algorithm" kante merugaina nadustunna samayaalanu andinche algorithamlu unnaayi. mottamodata kanugonabadinadi strassen yokka algorithm, dheenini 1969loe volkar strassen roopondinchaaru mariyu tarachugaa dheenini "vegavantamaina maatrika gunakaaram" anie pilustaaru. sthiramaina kaarakaala varaku rendu chadarapu maatrikalanu guninchadaaniki avasaramaina kshetra karyakalapala yokka saraina sankhya ippatikee teliyadu. saiddhaantika computer sainslo idhi oka pradhana bahiranga prasna.
, oka maatrika gunakaaram algorithm yokka lakshanarahita sanklishtatapai uttamamgaa prakatinchabadina kattubadi samayam, villiams, xu, xu mariyu zhou dwara ivvabadindi, idhi preprintlo prakatinchabadindi. idhi duan, vu mariyu jhou yokka preprint dwara icchina parimitipai merugupadutundi. ayithe, idhi mariyu straysenku saaruupya merugudalalu aacharanalo upayoginchabadavu, endukante avi galaxy algorithamlu pedda sangnaamaanam dwara daachina sthiramaina gunakam chaalaa peddadi, avi prastuta computerlalo nirvahinchadaaniki chaalaa pedda maatrikalaku matrame viluvainavi.
peer review dwara dhruveekarinchabadina uttama kaalaparimiti.
saralamaina algorithamlu.
a", "b" oka kshetrampai maatrikalu ayithe, appudu vaati utpatti "ab" kooda aaa kshetrampai oka maatrika, pravesam vaareegaa ilaa nirvachinchabadindih
paatasaala pustaka algorithm.
a" mariyu "b" anae rendu maatrikala yokka gunakaranni ganinchadaaniki saralamaina vidhanam, maatrika gunakaaram yokka nirvachanam nundi vachhe ankaganita vyakteekaranalanu ganinchadam. sudocode loeh
 input "a" mariyu "b", rendoo "n" dwara "n" maatrikalu
 anni sunnaala yokka "n" maatruka dwara "c" nuu "n" gaa praarambhinchandi
 i" kosam 1 nundi "n" varakuh
 zhe" kosam 1 nundi "enn" varakuh
 k" kosam 1 nundi "n" varakuh
 "c" "[" "i" "] [" "j" "] =" "c" "[" "i" "] [" "j" "] +" "a" "[" "i" "] [" "k" "] *" "b" "[" "k" "] [" "j" ""]
 avtput "c" (a * b gaa)
eee algorithanku, chettha sandarbhamlo, rendu chadarapu maatrikala utpattini ganinchadaaniki scalarla gunakaalu mariyu cherpulu avasaram. anduvalla, daani ganana sanklishtata anedi ganana namoonaalo, ikkada kshetra karyakalapalu (adanamgaa mariyu gunakaaram) sthiramaina samayanni teesukuntaayi (aacharanalo, idhi floating point sankhyala vishayamlo, conny puurnaamkaalaku tappanisarigaa kaadu).
strassen yokka algorithm.
strassen yokka algorithm oka vibhajana-mariyu-vijayam vidhanam dwara amayaka maatrika gunanampai merugupadutundi. pradhana pariseelana emitante, rendu maatrikalanu guninchadam anedi saadhaarana 8kii badulugaa (11 adanapu adanamgaa mariyu vyavakalanam karyakalapala vyayamtho) 7 gunakaalato matrame cheyavachu. dheeni ardham, input maatrikalanu block maatrikalagaa pariganinchadam, maatrikalanu guninche panini maatrikalanu guninche 7 upa samasyalaku tagginchavachhu. dheenini punaraavrutamgaa vartimpajeyadam suutram _ 2 kshetra kaaryakalaapaalaku avasaramaina algorithamnu istundi.
vegavantamaina asymptotic sanklishtatatoe kuudina algorithamla maadirigaa kakunda, straysen yokka algorithm aacharanalo upayoginchabadutundi. amayaka algorithamtho poliste sankhya sthirathvam taggutundi, conny idhi blass vanti aneka grandhalayalalo kanipinche sandarbhaallo vaegamgaa untundi. vegavantamaina maatrika gunana algorithamlu "bhagala vaareegaa sthirathvam" saadhinchalevu, conny konni "pramaanaala vaareegaa sthirathvam" pradarsinchavacchani chuupavachchu. sankhya sthirathvam samasya kaani parimita kshetraalu vanti khachitamaina domainlapai pedda maatrikalaku idhi chaalaa upayogakaramgaa untundi.
maatrika gunakaaram ghaataankam.
maatrika gunakaaram ghaataankam", saadhaaranamgaa suuchimchabadutumdi, idhi atichinna vaastava sankhya, dheeni kosam oka kshetrampai edainaa rendu suutraalu _ 3 maatrikalanu suutram _ 4 kshetra karyakalapalanu upayoginchi kalisi guninchavacchu. eee sangnaamaanam saadhaaranamgaa algorithamla parisoedhanaloo upayoginchabadutundi, tadwara matricks gunakaranni sub rutainga upayoginche algorithamlu nadustunna samayaniki sarihaddulanu kaligi untaayi, idhi meruguparachadaaniki sarihaddulugaa naveekarinchavacchu.
eguva sarihaddu kosam amayaka diguva sarihaddu mariyu paatasaala pustaka maatruka gunakaaram upayoginchi, okaru suutigaa muginchavacchu. saiddhaantika computer sainslo idhi oka pradhana bahiranga prasna kaadaa, mariyu merugaina sarihaddulanu pondadaaniki matricks gunakaaram algorithamlanu abhivruddhi chese parisoedhana line undhi.
eee parisoedhana shreniloni anni iteevali algorithamlu "lazer paddhati" nii upayogistaayi, idhi kaparsmith-vinograd algorithm yokka saadhaaraneekarana, idhi 1990loe daan kaparsmith mariyu schmuel vinograd icchinadi mariyu 2010 varaku uttama maatrika gunakaara algorithm. eee algorithamla sambhaavita aalochana strassen yokka algorithm maadirigaane untundih rendu-maatrikalanu guninchadam kosam oka maargam roopondinchabadindi, mariyu eee saanketikata punaraavrutamgaa vartinchabadutundi. lazer paddhati daani saktiki parimitulanu kaligi undhi, mariyu daanini choopinchadaaniki upayoginchalemu. duan, vu mariyu jhou lazer paddhatiloo sambhaavya optimisation yokka muulaanni "kalayika nashtam" anie pilustaaru. vaaru choopinchadaaniki upayoginche lazer paddhati yokka vaividhyaanni roopondinchadaaniki dheenini upayoginchukovadaaniki vaaru oka marganni kanugontaaru, edainaa sampradaaya lazer paddhati algorithm kosam addankini vichchinnam chestaaru. eee kotta vidhaanamtho maroka bandham duan, vu mariyu jou prakaram vartistundi mariyu lazer paddhatiloo kalayika nashtanni matrame parishkarinchadam saadhyam kaadu.
samuuha siddhaantam maatruka gunana algorithamla samskarana.
henry kohn, robbert clainberg, balas sejedi mariyu criss umans, triple product property (tii. pii. pii) anie piluvabade oka asambaddhamaina aastini santrupti parache parimita samuuhaala upasamitula moodu bhaagaalanu upayoginchadam dwara, strassen mariyu kaparsmith-vinograd algorithamla vanti paddhatulanu puurtigaa bhinnamaina samuuha-siddhaanta sandarbhamlo unchaaru. avi nijamaithe, tappanisarigaa chaturasra sanklishtatatoe kuudina maatrika gunana algorithamlu unnayani suuchistaayi. idhi maatrika gunakaaram yokka saraina ghaataankam 2 anie suuchistumdi, idhi chaalaa mandhi parisoedhakulu nijamgaa kesu anie nammutaaru. atuvanti oka ooha emitante, samaroopa samuuhaalatoe abelian samuuhaala pushpaguchchaala utpattula kutumbaalu tii. pii. pii yokka ekakaala samskaranatho upasamiti triples kutumbaalanu grahistaayi. vaari aneka oohagaanaalu blassiac, kohn, charchi, grocho, nassland, savin mariyu umans slies rank paddhatini upayoginchi niroopinchabaddaayi. inca, alon, shpilka mariyu criss umans iteevala chuupimchaaru, vegavantamaina maatrika gunanaanni soochinche eee oohallo konni maroka aamodayogyamaina ooha, suuryakaanti oohaku anugunamgaa levani, idhi cap sett samasyaku sambandhinchinadi.
ω kosam diguva sarihaddulu.
oka chinna diguva sarihaddu undhi. rendu-maatrikalanu guninchadaaniki edainaa algorithm anni entreelanu proses cheyalsi untundi kabatti, edainaa maatrika gunakaaram algorithm kosam chinna chinna lakshanarahita takkuva parimitiloo operations untaayi. eee vidhamgaa. anedi teliyadu. matricks-gunakaara sanklishtataku baga telisina diguva sarihaddu, vaastava ledhaa sanklishta sankhyalapai parimita gunakam ankaganita circuitla kosam, mariyu runn raze kaaranamgaa untundi.
ghaataankam ω anedi oka parimiti binduvugaa nirvachinchabadindi, dheenilo idhi anni maatrika gunana algorithm meeda ghaataankam yokka anantam. eee parimiti point saadhinchabadaledani telusu. maroe maatalo cheppalante, saadhaaranamgaa adhyayanam cheyabadina ganana namuunaa kinda, khachitamaina karyakalapalanu upayoginche maatrika gunakaaram algorithm ledhu; oka adanapu karakam undaali.
deerghachaturasraakaara maatrika gunakaaram.
idhe vidhamaina paddhatulu deerghachaturasraakaara maatrika gunanaaniki kooda vartistaayi. adhyayanam yokka kendra lakshyam suutram _ 5, idhi atichinna suutram _ 6, antey suutram _ 9 ankaganita kaaryakalaapaalato parimaana suutram _ 8 yokka maatrukato parimaana suutram _ 7 yokka maatrukanu guninchavacchu. beejaganita sanklishtatalo phalitam, parimaana suutram _ 7 mariyu suutram _ 8 yokka maatrikalanu guninchadaaniki parimaana suutram _ 7 mariyu suutram _ 13 mariyu parimaana suutram _ 13 mariyu suutram _ 7 yokka maatrikalanu guninchadam vale adhe sankhyalo ankaganita karyakalapalu avasaramavutaayani chebutundi, kabatti idhi deerghachaturasraakaara maatrika gunakaaram yokka sanklishtatanu kaligi untundi. idhi suutram _ 16 nundi chadarapu maatrika gunakaaram ghaataankaanni saadhaaraneekaristundi.
maatrika gunana samasya yokka avtput parimaana suutram _ 17 kabatti, suutram _ 19 yokka anni viluvalaku suutram _ 18 undhi. suutram _ 19 yokka konni viluvalaku 0 mariyu 1 madhya suutram _ 21 anie niroopinchagaligithe, appudu atuvanti phalitam aaa suutram _ 19kii suutram _ 22nii chooputundi. aaa suutram _ 22nii "dwandwa maatrika gunakam ghaataankam" anie pilustaaru, saadhaaranamgaa "α" anie suuchistaaru. "α" nuu "dual" gaa suuchistaaru endukante aaa suutram _ 25 choopinchadam aaa suutram _ 26 choopinchadaaniki samanam. maatrika gunakaaram ghaataankam vale, dwandwa maatrika gunakaaram ghaataankam konnisaarlu sankhya sarala beejaganitam mariyu optimisationloni algorithamla sanklishtatalo kanipistundi.
α" paie modati bandham 1982loe kaparsmith dwara choopabadindi, athanu aaa suutraanni _ 27 anie choopinchaadu. "α" paie prastuta uttama bandham suutram _ 28, idhi leey gall mariyu urutia dwara ivvabadindi. eee kaagitam suutram _ 5 paie sarihaddulanu kooda kaligi untundi.
sambandhita samasyalu.
maatrika gunakaaram vale adhe lakshanarahita sanklishtata kaligina samasyalalo nirnayakam, maatrika vilomam, gassian tolagimpu (tadupari vibhaganni chudandi) unnaayi. suutram _ 30 paramgaa vyakteekarinchadagina sanklishtatatoe unna samasyalalo lakshana bahupadi, aigen viluvalu (conny aigen vektarlu kaadu), hermite saadhaarana roopam mariyu smith saadhaarana roopam unnaayi.
matricks inversion, determinant mariyu gassian elemination.
1969loe thana kaagitamlo, athanu maatrika ganana kosam sanklishtata suutram _ 31nii niroopinchaadu, oka gunaka sthiraamkam varaku, maatrika gunakaaram vale adhe ganana sanklishtata maatrika vilomam, nirnayakam mariyu gassian tolagimpu kaligi unnayani kooda straysen niroopinchaadu. konni suutraala kosam daani sanklishtata suutram _ 32 ayithe tappa, upayoginchina maatrika gunanampai rujuvu etuvanti anchanaalu cheyadu.
straysen rujuvu yokka prarambha sthaanam block matricks gunakaranni upayoginchadam. pratyaekamgaa, sarri parimaanam yokka maatrukanu naalugu blaculuga vibhajinchavachhu.
eee roopamlo, daani vilomam 
adhi mariyu suutram _ 36 invertible gaa unte.
anduvalla, oka maatrika yokka vilomaanni rendu vilomaalu, aaru gunakaalu mariyu naalugu cherpulu ledhaa maatrikala sankalana vilomaalato lekkinchavacchu. idhi varusaga suuchistumdi, mariyu inverting, guninchadam mariyu maatrikalanu jodinchadaaniki avasaramaina karyakalapala sankhya, okati kaligi undhi 
suutram _ 38 ayithe eee suutraanni punaraavrutamgaa vartimpajeyavachuhu
suutram _ 40 mariyu suutram _ 41 chivariki labhiste 
kontha sthiramgaa.
rendu yokka shakti laeni parimaanam kaligina maatrikala kosam, rendu yokka saktiki maatrika yokka parimaanaanni penchadam dwara adhe sanklishtatanu cherukuntaaru, varusalatho mariyu niluvu varusalatho maatrikanu padding cheyadam dwara, dheeni namodulu vikarnampai 1 mariyu marekkadaina 0.
idhi maatrikalaku nokkicheppabadina sanklishtatanu rujuvu chestundi, antey vilomam cheyalsina anni upamanalu nijamgaa vilomam avtayi. eee sanklishtata daadaapu anni maatrikalaku niroopinchabadindi, endukante yaadrucchikamgaa enchukunna entreelatho kuudina maatruka sambhaavyatatoo vilomam avutundi.
adhe vaadana luu kullipovadaniki vartistundi, endukante, maatrika vilomamgaa unte, samaanatvam
oka block luu kullipovadaanni nirvachistundi, idhi suutram _ 44 mariyu suutram _ 45kii punaraavrutamgaa vartimpajeyavachu, chivariki asalu maatrika yokka nijamaina luu kullipovadaanni pondadaaniki.
eee vaadana nirnayakudiki kooda vartistundi, endukante idhi block luu kullipovadam valla vastundi 
gunakaala sankhyanu tagginchadam.
ankaganita karyakalapala sankhyanu tagginche samasyaku sambandhinchinadi gunakaala sankhyanu tagginchadam, idhi saadhaaranamgaa adanamgaa kante khareedaina operation. maatrika gunakaaram kosam suutram _ 32 algorithm tappanisarigaa suutram _ 32 gunakaaram karyakalapalanu matrame upayoginchaali, conny eee algorithamlu aacharana saadhyam kaadu. paatasaala pustaka gunakaaram kosam nishkapata suutram 49 gunakaalu nundi meruguparachadam, suutram 51 looni suutram 50 maatrikalanu 47 gunakaalato cheyavachu, commutative ring meeda suutram 52 maatrika gunakaaram 21 gunakaalalo cheyavachu (23 naan-commutative ayithe). avasaramaina gunakaala diguva parimiti 2 "mn" + 2 "n" − "m" −2 (pratyaamnaaya paddhatini upayoginchi "m" × "n"-maatrikalatoe "n" × "m"-maatrala gunakaaram, "m" "n" ′3), antey n = 3 kesuku kaneesam 19 gunakaalu mariyu n = 4 kaneesam 34 avasaram. n = 2 saraina 7 gunakaalaku 15 cherpulu kaneesamainavi, 8 gunakaalaku kevalam 4 cherpulatho poliste.

