Szybki algorytm mnożenia wektora przez macierz diadną

• Autorzy: Tariov A. , Adamski M.
• Języki publikacji: PL

Abstrakty

PL

W referacie zostala przedstawiona procedura optymalizowania liczby operacji arytmetycznych przy wyznaczaniu iloczynu dowolnego wektora przez macierz specjalnego typu - macierz diadną. Przedstawiona zostala specyfika proponowanego podejścia poprzez rozważenie struktury i wlaściwości tej macierzy, która to stanowi kluczowy element omawianego zagadnienia. Zaprezentowane zostały wektorowo - macierzowe procedury obliczeniowe, a także przyklady syntezowania "szybkich" algorytmów mnożenia wektora przez macierz diadną. Wykazano konkretne zyski obliczeniowe wynikające z ich stosowania oraz nakreślono kierunek dalszych prac.

EN

In the paper is presented a "fast" algorithm for calculating a product of any vector by a matrix of a specjal type - dyadic matrix. The specific matrix structure and properties were considered which make the key factor of the problem. Some computational procedures were described, as well as examples of producing "fast" algorithms for calculating the product of a vector and a dyadic matrix and substantial increase of efficiency they offer over straightforward algorithms. The idea for producing an effective algorithm for multiplying vector and a dyadic matrix is based on easiness for factorizing of such matrix due to the fact the eigenvectors of such matrix are columns of a Hadamard matrix. The algorithm requires, in general case, N multiplications and 3N log2 N additions. In most applications, the matrix is known a priori and all its elements are known before constructing the algorithm. In such case elements of the diagonal matrix can be calculated and stored in memory.

Słowa kluczowe

PL

iloczyn wektorowo-macierzowy; notacja macierzowa; macierz diadna

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Informatyka Teoretyczna i Stosowana
• Rocznik: 2005
• Tom: R. 5, nr 8
• Strony: 107--115
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Tariov A.

• IAKiT Zakład Telekomunikacji, Politechnika Szczecińska ul. Żołnierska 49, 71-210 Szczecin, Polska

autor

Adamski M.

• IAKiT Zakład Telekomunikacji, Politechnika Szczecińska ul. Żołnierska 49, 71-210 Szczecin, Polska

Bibliografia

• [1] Winograd S., A new algorithm for inner product. IEEE Trans. Computers, C-17:693-694, 1968.
• [2] Strassen V., Gaussian elimination is not optimal. Numerische Mathematik, 14:354-356, 1969.
• [3] Winograd S., On multiplication of 2x2 matrices, Linear Algebra and Appl. 4, 381-388 (1971).
• [4] Coppersmith D. and Winograd S., Matrix multiplication via arithmetic progressions. In Proc. Nineteenth ACM Symp. Theory of Computing, pages 1-6, 1987.
• [5] Pan V., Strassen’s algorithm is not optimal-trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations, Proc. 19th Ann. Symp. on Foundations of Computer Science, 1 66-l 76 (Oct. 1978).
• [6] Fischer M.J. and Meyer A.R., Boolean matrix multiplication and transitive closure, Proc. IEEE 12th Ann. Symp. Switching and Automata Theory, 129-131 (1971).
• [7] Pan V., Field extension and trilinear aggregating, uniting, and canceling for the acceleration of matrix multiplications, Proc. 20th Ann. Symp. on Foundations of Computer Science (1979).
• [8] Pan V., New fast algorithms for matrix operations, SIAM J. Computing 9, 32 l-342 (1980).
• [9] Bini D., Capovani M., Romani F., Lotti G., O(n2.7799) complexity for nxn approximate matrix multiplication, Inform. Proc. Lett. 8, 234-235 (1979).
• [10] Bini D., Lotti G., and Romani F., Approximate solutions for the bilinear form computational problem, S1M J. Computing 9, 692-697 (1980).
• [11] Schönhage A., Partial and total matrix multiplication, SIAM J. Computing 10, 434-455 (1981).
• [12] Coppersmith D. and Winograd S., On the asymptotic complexity of matrix multiplication, SIAM J. Computing 11,472-492 (1982).
• [13] Pan V., How to Multiply Matrices Faster, Lecture Notes in Computer Science 179, Springer- Verlag, 1984.
• [14] Coppersmith D. and Winograd S., Matrix multiplication via arithmetic progressions, J. Symbolic Computation 9, 251-280, 1990.
• [15] Laderman J., A noncommutative algorithm for multiplying 3x3 matrices using 23 multiplications, Bull. Amer. Math. Soc. 82, 126-128 (1976).
• [16] Johnson R.W. and McLoughlin A.M., Noncommutative bilinear algorithms for 3x3 matrix multiplication, SIAM J. Computing 15 (2), 595-603 (1986).
• [17] Hopcroft J.E. and Kerr L.R., On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. App Math. 20, 30—36 (1971).
• [18] Obotnin A.N., Metody wyprowadzania szybkich algorytmów obliczania widma, rękopis zdeponowany No 5989-84 Dep., Politechnika Uralska 1984, 18 s.
• [19] Ahmed Nasir U., Ramamohan Rao K., Orthogonal Transforms for Digital Signal Processing Springer-Verlag New York, mc, 1975.
• [20] Tolimieri R., An M., Lu C., Algorithms for Discrete Fourier Transform and Convolution, Springer-Verlag New York Inc., 1989.
• [21] Horn Roger A., The Hadamard product, Proc. Sympos. Appl. Math. (Charles R. Johnson,ed.), vol. 40, Amer. Math. Soc., Providence, RI, 1990.