АППАРАТУРНО-ОРИЕНТИРОВАННЫЙ АЛГОРИТМ ДЛЯ БЫСТРОГО УМНОЖЕНИЯ КРОНЕКЕРОВА ПРОИЗВЕДЕНИЯ МАТРИЦ НА ВЕКТОР

Аннотация

В статье на основе использования свойств произведения Кронекера (КП) матриц предлагается новый алгоритм для повышения эффективности выполнения операции ум- ножения КП на вектор. Указанная операция широко применяется при решении задач обра- ботки сигналов, изображений, криптографии и т.п., где выполняется формирование мат- риц большого размера с заданными свойствами с помощью КП матриц малого размера. При этом используются матрицы со следующими свойствами: ортогональные (унитар- ные), обращаемые, инволютивные. Умножение квадратной матрицы размера на вектор имеет вычислительную сложность O(n2). Поэтому при росте количества элемен- тарных матриц-сомножителей размер результирующей матрицы КП и сложность умно- жения ее на вектор растут экспоненциально. Это обстоятельство существенно повыша- ет время решения прикладных задач. Целью предлагаемой работы является построение алгоритма, ориентированного на аппаратную реализацию и ускоряющего процессы фор- мирования КП и умножения вектора на него. Предлагается совместить во времени эти процедуры. Таким образом матрица КП в явном виде фактически не рассчитывается. Вме- сто этого матрицы-сомножители КП итеративно умножаются на компоненты вектора за время O(nlog2n) и требуют линейной сложности памяти. Приведена схема вычислений с топологией гиперкуба для возможной аппаратной реализации предлагаемого алгоритма, которая легко поддается конвейеризации. В разделе 1 приведены определения и свойства КП, используемые при синтезе предлагаемого алгоритма. В разделе 2 рассмотрен иллюст- рирующий предлагаемый алгоритм пример с , на основе которого в разделе 3 пред- ложена аппаратурно-ориентированная структура его реализации для произвольного n.