An Efficient Method of Matrix Multiplication for Heaps of Pieces
| Autor: | Simon Ware, FaJun Yang, Liyong Lin, Yuting Zhu, Rong Su |
|---|---|
| Přispěvatelé: | School of Electrical and Electronic Engineering |
| Rok vydání: | 2018 |
| Předmět: |
0209 industrial biotechnology
04 agricultural and veterinary sciences 02 engineering and technology Supervisory Control 040401 food science Matrix multiplication Combinatorics Matrix (mathematics) 020901 industrial engineering & automation 0404 agricultural biotechnology Control and Systems Engineering Engineering::Electrical and electronic engineering [DRNTU] Heaps of Pieces Time complexity Mathematics R-matrix |
| Zdroj: | IFAC-PapersOnLine. 51:206-211 |
| ISSN: | 2405-8963 |
| DOI: | 10.1016/j.ifacol.2018.06.302 |
| Popis: | In this paper, we outline a method for carrying out efficient (max, +) matrix multiplication when using the heaps of pieces framework. We present an algorithm for multiplying an arbitrary m by r matrix X by a r by r heaps of pieces matrix M, making it possible to calculate the resulting matrix in worst case time complexity O(mr), rather than O(mr2) which is required when using the matrix multiplication definition. We also give an algorithm for multiplying M by an arbitrary r by n matrix X with worst case time complexity O(nr). Finally, we consider a variant of the standard heaps of pieces model, and present an improved matrix multiplication algorithm for this variant as well. Published version |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|