A computation algorithm for Strassen's matrix multiplication

• Autorzy: Tariov A. , Gliszczyński M.

Warianty tytułu

PL

Algorytm obliczania iloczynu macierzowego Strassena

• Języki publikacji: EN

Abstrakty

EN

In the work the vectorized algorithm for Strassen's matrix product calculating is presented. Unlike the proposed in other works "some recommendations" relating to the Strassen's matrix multiplication implementation, we offer specific computational procedures that allow correctly describe the entire sequence of transformations needed to obtain the final result. The proposed algorithm can be successfully applied to accelerate calculations in the FPGA-based platforms.

PL

W pracy został przedstawiony wektoryzowany algorytm wyznaczenia iloczynu macierzowego Strassena. W odróżnieniu od poruszanych w innych publikacjach wybranych uwag dotyczących realizacji metody Strassena w niniejszej pracy zaproponowane są konkretne procedury, opisujące cały proces obliczeniowy i pozwalające na podstawie wykonania skończonej liczby etapów przetwarzania danych wejściowych otrzymać wynik końcowy. Została roztrząśnięta synteza proponowanego algorytmu oraz pokazana postać stosownego grafu przepływowego dla przykładu mnożenia macierzy drugiego rzędu. Zaproponowany algorytm może być sukcesywnie zastosowany do przyspieszonej realizacji obliczeń w platformach FPGA oraz zaimplementowany w wybranym środowisku sprzętowym. Niewątpliwym atutem odróżniającym przedstawione rozwiązanie od tradycyjnego algorytmu jest również brak rekurencji obliczeń, co daje dodatkowy zysk przy zrównolegleniu procesu wyznaczenia iloczynu.

Słowa kluczowe

EN

Strassen's matrix multiplication; fast algorithms

PL

iloczyn macierzowy Strassena; szybkie algorytmy

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 7
• Strony: 691--693
• Opis fizyczny: Bibliogr. 24 poz., rys., wzory

Twórcy

autor

Tariov A.

autor

Gliszczyński M.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, ul. Żołnierska 49, 71-210 Szczecin,

Bibliografia

• [1] Strassen V.: Gaussian elimination is not optimal. Numerische Mathematik, 13(4), pp. 354-356, 1969.
• [2] Cohen J. and Roth M.: On the implementation of Strassen’s fast multiplication algorithm, Acta Informatica, 1976, pp. 341-355.
• [3] Hopcroft J. E. and Kerr L. R.: On minimizing the number of multiplications necessary for matrix multiplications, SIAM J. Appl. Math., 1971, vol. 20, no 1, pp. 35-36.
• [4] Dumitrescu B., Roch J. L., Trystram D.: Fast matrix multiplication algorithms on MIMD architectures, Int. Journal of Parallel, Emergent and Distributed Systems, Vol. 4, Issue 1 & 2, 1994, pp. 53-70.
• [5] Bailey David H.: Extra high speed matrix multiplication on the Cray-2. SIAM Journal on Scientific and Statistical Computing, 1988, v. 9 no 3, pp. 603-607.
• [6] Kakaradov Boyko: Ultra-fast Matrix Multiplication: An Empirical Analysis of Highly Optimized Vector Algorithm. Stanford Undergraduate Research Journal (SURJ), 2004, vol. 3, pp. 33-36.
• [7] Grayson Brian, Shah Ajay and van de Geijn Robert: A High Performance Parallel Strassen Implementation. Parallel Processing Letters, 1996, vol. 6, No 1, pp. 3-12.
• [8] Huang C. -H., Johnson J. R. and Johnson R. W.: A tensor product formulation of Strassen’s matrix multiplication algorithm. Appl. Math Letters, 3 (3): 67-71, 1990.
• [9] Kumar B., Huang C. -H., Sadayappan P., Johnson R. W.: A Tensor Product Formulation of Strassen’s Matrix Multiplication Algorithm with Memory Reduction, Scientific Programming, Vol. 4, No 4, 1995, pp. 275-289.
• [10] Desprez Frédéric and Suter Frédéric : Impact of Mixed-Parallelism on Parallel Implementations of Strassen and Winograd Matrix Multiplication Algorithms. Concurrency and Computation: Practice and Experience, July 2004, 16 (8), pp. 771-797.
• [11] Chou C. C., Deng Y. F., Li G. and Wang Y.: Parallelizing Strassen’s method for matrix multiplication on distributed-memory MIMD architectures. Computers & Mathematics with Applications, 1995, Vol. 30, Issue 2, , pp. 49-69.
• [12] Alqadi Ziad A. A., Aqel Musbah and El Emary Ibrahiem M. M.: Performance Analysis and Evaluation of Parallel Matrix Multiplication Algorithms. World Applied Sciences Journal, 5 (2), pp. 211-214, 2008.
• [13] Cormen Thomas H., Leiserson Charles E., Rivest Ronald L. and Stein Clifford: Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 28: Section 28.2: Strassens algorithm for matrix multiplication, pp. 735-741.
• [14] Douglas C., Heroux M., Slishman G. and Smith R.: 1994. GEMMW: A portable level 3 BLAS Winograd variant of Strassen’s matrix-matrix multiply algorithm. J. Comp. Phys. 110, 1-10.
• [15] Li Keqin, Pan Yi, Zheng Si Qing: Fast and Processor Efficient Parallel Matrix Multiplication Algorithms on a Linear Array With a Reconfigurable Pipelined Bus System, IEEE Trans. on Parallel and Distributed Systems, vol. 9, no 8, pp. 705-720, Aug. 1998.
• [16] Laderman Julian, Pan Victor and Sha Xuan-He: On practical algorithms for accelerated matrix multiplication. Linear Algebra and its Applications, 1992, vol. 162-164, pp. 557-588.
• [17] Francomano E, Lodato C, Tortorici A.: A recurrence-free variant of Strassen’s algorithm on hypercube. Int. Journal of Parallel, Emergent and Distributed Systems, Vol. 5, Issue 3 & 4 1995, pp. 241-249.
• [18] D’Alberto P. and Nicolau A.: Adaptive Strassen's matrix multiplication. In Proc. of the 21st Annual Int. Conference on Supercomputing. ACM, New York, NY, 2007, 284-292.
• [19] Huss-Lederman S., Jacobson E., Johnson J., Tsao A. and Turnbull T.: 1996a. Strassen’s algorithm for matrix multiplication: Modeling, analysis, and implementation. Tech. rep. CCS-TR-96-14. Center for Computing Sciences, University of Wisconsin-Madison, Madison, WI.
• [20] Goto, K. and van de Geijn, R.: Anatomy of high-performance matrix multiplication. ACM Trans. Math. Softw. 2008, 34, 3, 1-25.
• [21] Fischer P. C. and Probert R. L.: Efficient procedures for using matrix algorithms. In Automata, Languages and Programming, number 14 in Lecture Notes in Computer Science, pages 413-427. Springer-Verlag, 1974.
• [22] Pauca V. P., Sun Xiaobai, Chatterjee Siddhardha, Lebeck Alvin: Architecture-efficient Strassen’s matrix multiplication: A case study of divide-and-conquer algorithms, Technical report CS-1998-06, Department of Computer Science, Duke University, Durham, NC27708, 1998, pp. 1-16.
• [23] Loan C. F. V.: The ubiquitous Kronecker product. Journal of Computational and Applied Mathematics, 123:85-100, 2000.
• [24] Tsariov A.: Algoritmiczeskije modeli i struktury wysoko proizwoditelnych processorow CRS. Szczecin, Informa, 2001.