|
||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[222] (В упр. 31.2-2 предлагается рассмотреть случай, в котором га не является точной степенью 2.) Для удобства подматрицы в А идут по алфавиту порядке слева направо, а подматрицы в В - сверху вниз, в соответствии с правилом умножения матриц. Уравнение (31.9) распадается на четыре уравнения
Каждое из четырёх уравнений требует двух умножений (га/2 X га/2)-матриц, после чего произведения складываются. Рассмотрим естественный рекурсивный алгоритм, использующий эти соотношения. Его время работы Т(п) (для матриц размера га X га) удовлетворяет неравенству Г(га) = 8Г(га/2)+ в(га2)(31.14) Отсюда Т(п) = ©(га3), но ничего нового мы не получили, так как стандартный алгоритм умножения матриц имеет (асимптотически) то же время работы. Штрассен придумал, как сэкономить одно умножение и обойтись лишь 7 умножениями (га/2 X га/2)-матриц и 0(га2) операциями сложения и вычитания чисел для умножения (га X га)-матриц. Рекуррентное соотношение тогда принимает вид Г(га) = 7Г(га/2) + 0(га2),(31.15) откуда Г(га) = 0(га1§7) = 0(га2-81). Алгоритм Штрассена умножает две (га X га)-матрицы А и В так: 1.Каждая из матриц А и В разбивается на 4 блока, как в (31.9). 2.Строятся 14 матриц А\, В\, А2, В2, , Аг, В?, размера (га/2 х га/2) (для чего нужно ©(га2) операций сложения/вычитания чисел) 3.Рекурсивно вычисляются 7 произведений матриц меньшего размера Рг- = А{В{ [г = 1,... ,7). 4.Вычисляются части г, s, t, и искомой матрицы С. Они являются линейными комбинациями матриц Рг- с коэффициентами из множества { - 1, 0,1}, и вычисление их требует 0(га2) операций сложения/вычитания чисел. Время работы этого алгоритма, очевидно, удовлетворяет соотношению (31.15). Изложим теперь опущенные детали. Какие же матрицы меньшего размера нужно перемножать? Готоые формулы для Р1-Р7 проверить легко, труднее понять, как до них можно догадаться. Вот один из возможных путей. Будем искать произведения Рг- среди выражений вида = (аца + аг2Ь + аг3с + ai4d) ((Зце + fil2f + (Згз9 + (31.16) где коэффициенты a8j,/38j принимают значения -1,0,1. Конечно, можно искать формулы для Рг- и в более общем виде, но оказывается, что этого уже достаточно. Обратите внимание, что после раскрытия скобок куски матрицы А будут стоять слева в попарных произведениях, а куски матрицы В - справа. Это важно, поскольку умножение матриц не коммутативно. Для удобства мы будем изображать линейную комбинацию попарных произведений кусков матриц при помощи (4 X 4)-матрицы, элементами которой служат соответствующие коэффициенты линейной комбинации. Например, равенство (31.10) запишется в виде Р% - AjBj формула набрана мной не г = ае + bf верно вполне /+10 0 0\ /е\ 0+100 / 00 0 0 g \ 00 0 0/\/г/ а (+ е f g h + Л = ь + с d \ J Для краткости мы заменяем +1 на +, 0 на • и -1 на - и опускаем имена столбцов и строк. В этих терминах три остальные компо- ненты результирующей матрицы С запишутся так: s = ад A- bh •• • + 1 V 7 t = се + df /. . . Л = + ... {+) и = eg -\- dh /. . . А •• + • V• • +/ [Видно, что ни одну из матриц s, t, и, v нельзя вычислить за одно умножение по формуле (31.16) - нужно два. Если делать это независимо для каждой из четырёх матриц, потребуется 8 умножений. Однако, как мы увидим, одно умножение можно сэкономить, используя одни и те же произведения для нескольких матриц.] Начнём со следующего наблюдения: s можно вычислить как s = Pi + Р2, где каждая из матриц Pi и Р2 требует одного умножения: Pi = AiBi = а (д - h) = ад - ah V 7 Р2 = А2В2 = (а + Ъ) -h = ahA-bh ( +\ + V• • 7 Аналогичным образом можно вычислить t. Именно, t = Р3 + Р4, |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||||||||