Пәннің ОҚУ-Әдістемелік кешені «Матрицалар теориясы»
жүктеу/скачать 2,25 Mb.
|
7d448e60-8cb2-11e3-bf6e-f6d299da70eeказ умм теория матриц
1.9 Штрассен әдісі1965 жылы Штрассен - өлшемді матрицаны тек қана 7 көбейтіндінің көмегімен көбейтуді анықтады (классикалық әдісте – 8 көбейтінді қолданылады). Штрассеннің ойлап тапқаны «көп өлшемді матрицалардың» тензорлық рангын есептеу көмегімен алынады. 1.10 - өлшемді матрицалар үшін рекурсия 7 көбейтіндінің көмегімен есептелетін - өлшемді матрицаларды көбейтуден аспайтын амлады қажет ететін - өлшемді матрицаларды көбейту әдісіне көшу оңай. ұмтылғанда ұмтылғандықтан, Штрассен әдісі классикалық әдістен асимптотикалық жақсырақ болып табылады. Айталық болсын және матрицаларын - өлшемді блокты матрица түрінде қарастырайық: Штрассен әдісінде - өлшемді матрицаларды көбейткенде коммутативтілік қолданылмайды. Сондықтан да бұл әдіс - өлшемді блокты матрицаларды көбейту үшін де қолданылады. Сонымен, өлшемді есеп дәл осындай жеті өлшемді есепке келтіріледі. Бұл 7 есепті құру үшін және осы 7 есепті шешкеннен кейін қорытынды нәтижені алу үшін ретті блоктарды 18 рет қосу қажет. Көрсетілген рекурсияны аяғына дейін «бұрмаласақ», соңғы кезеңде көбейтуді аламыз. Барлық кезеңдегі қосудың жалпы саны құрайды. (мұнда екендігін ескеру қажет). Қазіргі кезде Штрассен әдісінен де аса жылдам әдістер ойлап табылған. жүктеу/скачать 2,25 Mb. Достарыңызбен бөлісу:
|