АППАРАТУРНО-ОРИЕНТИРОВАННЫЙ АЛГОРИТМ ДЛЯ БЫСТРОГО УМНОЖЕНИЯ КРОНЕКЕРОВА ПРОИЗВЕДЕНИЯ МАТРИЦ НА ВЕКТОР
Аннотация
В статье на основе использования свойств произведения Кронекера (КП) матриц
предлагается новый алгоритм для повышения эффективности выполнения операции ум-
ножения КП на вектор. Указанная операция широко применяется при решении задач обра-
ботки сигналов, изображений, криптографии и т.п., где выполняется формирование мат-
риц большого размера с заданными свойствами с помощью КП матриц малого размера.
При этом используются матрицы со следующими свойствами: ортогональные (унитар-
ные), обращаемые, инволютивные. Умножение квадратной матрицы размера на
вектор имеет вычислительную сложность O(n2). Поэтому при росте количества элемен-
тарных матриц-сомножителей размер результирующей матрицы КП и сложность умно-
жения ее на вектор растут экспоненциально. Это обстоятельство существенно повыша-
ет время решения прикладных задач. Целью предлагаемой работы является построение
алгоритма, ориентированного на аппаратную реализацию и ускоряющего процессы фор-
мирования КП и умножения вектора на него. Предлагается совместить во времени эти
процедуры. Таким образом матрица КП в явном виде фактически не рассчитывается. Вме-
сто этого матрицы-сомножители КП итеративно умножаются на компоненты вектора
за время O(nlog2n) и требуют линейной сложности памяти. Приведена схема вычислений с
топологией гиперкуба для возможной аппаратной реализации предлагаемого алгоритма,
которая легко поддается конвейеризации. В разделе 1 приведены определения и свойства
КП, используемые при синтезе предлагаемого алгоритма. В разделе 2 рассмотрен иллюст-
рирующий предлагаемый алгоритм пример с , на основе которого в разделе 3 пред-
ложена аппаратурно-ориентированная структура его реализации для произвольного n.
Литература
Mathematics, 2000, No. 123, pp. 85-100.
2. Jemderson H.V., Pukelsheim F., and Searle S.R. On the history of the Kronecker product, Linear
and Multilinear Algebra, 1983, Vol. 14, No. 2, pp. 113-120.
3. Graham A. Kronecker Products and Matrix Calculus with Applications (Dover Books on
Mathematics), Dover Publications, 2018.
4. Buchholz P., Ciardo G., Donatelli S., Kemper P. Complexity of memory-efficient Kronecker
operations with applications to the solution of Markov models, INFORMS J. Comput., 2000,
pp. 203-222.
5. Tadonki C., Philippe B. Parallel multiplication of a vector by a Kronecker product of matrices,
Journal of Parallel and Distributed Computing and Practices, 2000, No. 3 (3), pp. 1-11.
6. Tadonki C. Large-scale Kronecker product on supercomputers, 2011 Second Workshop on
Architecture and Multi-Core Applications (WAMCA 2011). 26-27 Oct. 2011. Victoria, Brazil.
IEEE, pp. 1-4.
7. Doukhnitch E., Strelnikov O., Andreev A., Application of Kronecker Matrix Product for the
Synthesis of Hardware-oriented DSP Algorithms, in Proc. of Intern. Conf. on Signal Proc.
“DSPA-99”, Moscow, Sept. 1999, pp. 78-83.
8. Doukhnitch E., Salamah M., Andreev A. Effective Processor for Matrix Decomposition, Arabian
Journal for Science and Engineering, March 2014, Vol. 39, Issue 3, pp. 1797-1804.
9. Dayar T., Orhan M.C. On vector-Kronecker product multiplication with rectangular factors,
SIAM J. Sci. Comput., 2015, Vol. 37 (5), p. S526-S543.
10. Koukouvinos C., Lappas E., Simos D.E. Encryption schemes using orthogonal arrays, Journal
of Discrete Mathematical Sciences and Cryptography, 2009, No. 12 (5), pp. 615-628.
11. Chefranov A., Dukhnich E. One-time Kronecker product-based Hill cipher modification, International
Journal of Information Assurance and Security, 2017, No. 12 (3), pp. 94-103.
12. Lancaster Р. and Tismenetsky М., The Theory of Matrices. 2nd ed. Orlando, Florida:
AcademicPress, 1985.
13. Chefranov A., Dukhnich E., Shapel A. One-Time Involutory Matrix-Based Hill Cipher Modification,
International Journal of Information Assurance and Security (JIAS), 2020, Vol. 15,
No. 4, pp. 165-174.
14. Dzhambruno M. Trekhmernaya (3D) grafika i animatsiya [3D Graphics &Animation]. Moscow:
Vil'yams, 2002, 640 p.
15. Dzwonkowski M., Rykaczewski R. Secure quaternion Feistel cipher (S-QFC) for DICOM
images, IEEE Transactions on Image Processing, 2019, Vol. 28, No. 1, pp. 371-380.
16. Dzwonkowski M., Papaj M., Rykac R. A new quaternion-based encryption method for DICOM
Images, IEEE Transactions on Image Processing, 2015, Vol. 24, No. 11, pp. 4614-4522.
17. Gantmakher F.R. Teoriya matrits [The theory of matrices]. Moscow: Glavnaya redaktsiya
fiziko-matematicheskoy literatury izdatel'stva "Nauka", 1966.
18. Blair Jeffrey S. The Biomedical Engineering handbook. CRC Press Taylor & Francis Group,
New York, 2006, pp. 42-4–42-5.
19. Deng Y., Guo M., Ramos A.F., et al. Optimal low-latency network topologies for cluster performance
enhancement, J. Supercomput. Published online 02 March 2020. Available at:
https://doi.org/10.1007/s11227-020-03216-y.
20. Hayes J.P., Mudge T. Hypercube supercomputers, Proceedings of the IEEE, 1989, Vol. 77
(12), pp. 1829-1841.
