Алгоритъм на Strassen

Въведение и постановка на проблема

Матрично умножение по дефиниция, вградена функция

матмул и оптимизация

1 Въведение и формулиране на проблема

Една от основните задачи на тази работа е прилагането на алгоритъма на Strassen. Това е рекурсивен алгоритъм за умножение на матрици, който ви позволява значително да ускорите процеса на умножение. Трябва да се отбележи, че този алгоритъм е ефективен само за достатъчно големи матрици. Възможно е експериментално да се определи размерът на матриците, от които има смисъл да се започне умножаване с помощта на алгоритъма на Strassen. Освен това вече споменах, че алгоритъмът е рекурсивен. Нерекурсивният клон на алгоритъма използва "просто" матрично умножение, т.е. умножение по дефиниция. Да направя нерекурсивния клон най-ефективен и да организирам изхода от рекурсията в точното време е друга задача от моята работа.

И така, нека очертаем целите на работата:

Приложете алгоритъма на Strassen;

Експериментално намерете размера на матрицата, за която е необходимо да преминете към умножение по алгоритъма;

Организирайте изхода от рекурсията в точното време;

Направете нерекурсивния клон най-ефективен.

2 алгоритъм на Strassen

Най-отнемащата време операция е умножението. Тези. за да ускорите процеса, трябва да намалите броя им. Strassen излезе с алгоритъм [1, 2, 3], който избягва едно умножение. Забележително е, че формулите не изискват комутативност на събирането, т.е. те са приложими и за матрици, което прави възможно прилагането на алгоритъма рекурсивно.

Алгоритъмът работи с квадратни матрици с размер 2 n . Имайте предвид, че умножаването на матрици с този размер изисква 2 3n умножения. Ако матриците не са квадратни, тогава можете да ги разширите до желания размер, като попълните липсващите редове и колони с нули. Да кажем, че са две2 n матрици A и B за умножение: C = AB. Нека разделим всяка матрица на четири подматрици:

---