Матрицаларды кбейтуді есептеуіш аспектісі

Айталы - лшемді матрицалары берілсін жне оларды кбейтіндісін есептеу керек болсын. Бны есептеуді классикалы алгоритмі мынадай (программа алгоритмдік Фортран тіліне сас):

Алайда алдымен элементтерін нлге айналдырып алу керек.

«Бл бадарламаны жасы жаы неде?»,- деген сра туындайды. Бл сраа жауап беру оай емес. Алдымен бізге андай да бір критерий ажет – айталы осы бадарламаны орындау уаыты болсын. Алайда уаыт тек компьютерді тріне ана туелді емес.

Бл жерде бірдене тсіну шін кптеген блшектерді алып тастап, е негізгісін алтыру керек. Егер де барлы амалдар тізбектей орындалса, онда жмысты орындалу уаытын амалдар санына пропорционал деп есептеуімізге болады. біз арай жрейік жне тек арифметикалы амалдарды есептейміз. Оларды жалпы санын алгоритмні арифметикалы крделілігі деп атаймыз.

Алгоритм –бл элементар амалдарды соы бекітілген жиынтыынан алынан элементар амалдарды тізбегі деп есептейік. Аныты шін, айталы бл трт арифметикалы амал болсын.

Сонымен, математикалы есеп ойылды. Брындары классикалы алгоритм е жасы деп есептелген. азір байайтынымыздай ол блай емес.

1.8 Виноград дісі

Классикалы алгоритмді олданбай матрицаларды кбейткен алашыларды бірі (60 жылдарды басында) Виноград болды. Ол келесі тепе – тедікті олдануа болатынын крсетті:

Айталы болсын. Барлы шін екінші жне шінші осындыны кбейту жне осу амалы арылы табуа болады. Бірінші осынды шін кбейту жне осу амалы ажет.

Нтижесінде – брыныдай, амал орындалады, біра мнда енді кбейту жне осу амалы болады. кбейту амалы осуа араанда крделі амал боландытан Виноград дісіні практикалы маызы бар.

Штрассен дісі

1965 жылы Штрассен - лшемді матрицаны тек ана 7 кбейтіндіні кмегімен кбейтуді анытады (классикалы дісте – 8 кбейтінді олданылады). Штрассенні ойлап тапаны «кп лшемді матрицаларды» тензорлы рангын есептеу кмегімен алынады.

1.10 - лшемді матрицалар шін рекурсия

7 кбейтіндіні кмегімен есептелетін - лшемді матрицаларды кбейтуден аспайтын амлады ажет ететін - лшемді матрицаларды кбейту дісіне кшу оай. мтыланда мтыландытан, Штрассен дісі классикалы дістен асимптотикалы жасыра болып табылады.

Айталы болсын жне матрицаларын - лшемді блокты матрица трінде арастырайы:

Штрассен дісінде - лшемді матрицаларды кбейткенде коммутативтілік олданылмайды. Сондытан да бл діс - лшемді блокты матрицаларды кбейту шін де олданылады.

Сонымен, лшемді есеп дл осындай жеті лшемді есепке келтіріледі. Бл 7 есепті ру шін жне осы 7 есепті шешкеннен кейін орытынды нтижені алу шін ретті блоктарды 18 рет осу ажет.

Крсетілген рекурсияны аяына дейін «брмаласа», соы кезеде кбейтуді аламыз. Барлы кезедегі осуды жалпы саны

 

райды. (мнда екендігін ескеру ажет).

азіргі кезде Штрассен дісінен де аса жылдам дістер ойлап табылан.

 

ДРІС 3,4