Новые быстрые гибридные алгоритмы умножения матриц

Abstract

Запропоновано новi гiбриднi алгоритми множення (n x n)-матриць, при побудові яких використано алгоритм Лейдермана для множення (3 x 3)-матриць. Порівняно з відомими гібридними алгоритмами множення матриць нові алгоритми характеризуються мінімізованою обчислюваною складністю. Наведено оцінки мультиплікативної, адитивної та загальної складності в представлених алгоритмах.

New hybrid algorithms are proposed for multiplying (n x n)-matrices. They are based on Laderman’s algorithm for multiplying (3 x 3)-matrices. As compared with the well-known hybrid matrix multiplication algorithms, the new algorithms are characterized by the minimum computational complexity. The multiplicative, additive, and overall complexities of the algorithms are estimated.