Matrix black box algorithms - a survey

• Autorzy: Respondek Jerzy

Identyfikatory

DOI

10.24425/bpasts.2022.140535

• Języki publikacji: EN

Abstrakty

EN

The implementations of matrix multiplication on contemporary, vector-oriented, and multicore-oriented computer hardware are very carefully designed and optimized with respect to their efficiency, due to the essential significance of that operation in other science and engineering domains. Consequently, the available implementations are very fast and it is a natural desire to take advantage of the efficiency of those implementations in other problems, both matrix and nonmatrix. Such an approach is often called a black box matrix computation paradigm in the literature on the subject. In this article, we gathered a broad series of algorithms taking advantage of the efficiency of fast matrix multiplication algorithms in other mathematical and computer science operations.

Słowa kluczowe

EN

matrix algebra; matrix multiplication algorithm; numerical recipes; recursion

PL

algebra macierzowa; algorytm mnożenia macierzy; receptury numeryczne; rekurencja

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2022
• Tom: Vol. 70, nr 2
• Strony: art. no. e140535
• Opis fizyczny: Bibliogr. 35 poz., rys.

Twórcy

autor

Respondek Jerzy

• The Silesian University of Technology, Faculty of Automatic Control, Electronics and Computer Science, ul. Akademicka 16, 44-100 Gliwice, Poland

Bibliografia

• [1] V. Strassen, “Gaussian elimination is not optimal”, Numer. Math., vol. 13, pp. 354–356, 1969.
• [2] V. Pan, “Strassen’s algorithm is not optimal”, in 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), 1978, pp. 166–176, doi: 10.1109/SFCS. 1978.34.
• [3] D. Bini, M. Capovani, G. Lotti., and F. Romani, “O(n^2.7799) complexity for approximate matrix multiplication”, Inf. Proc. Lett., vol. 8, no. 5, pp. 234–235, 1979.
• [4] A. Schonhage, “Partial and Total Matrix Multiplication”, SIAM J. Comput., vol. 10, no. 3, pp. 434–455, 1981.
• [5] F. Romani, “Some properties of disjoint sums of tensors related to matrix multiplication”, SIAM J. Comput., vol. 11, pp. 263–267, 1982.
• [6] D. Coppersmith and S. Winograd, “On the Asymptotic Complexity of Matrix Multiplication”, SIAM J. Comput., vol. 11, no. 3, pp. 472–492, 1982.
• [7] V. Strassen, “The Asymptotic Spectrum of Tensors and the Exponent of Matrix Multiplication”, in 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), 1986, pp. 49–54, doi: 10.1109/SFCS.1986.52.
• [8] D. Coppersmit and S. Winograd, “Matrix multiplication via arithmetic progressions”, J. Symb. Comput., vol. 9, no. 3, pp. 251–280, 1990.
• [9] A. Davie and A. Stothers, “Improved bound for complexity of matrix multiplication”, Proc. Royal Society of Edinburgh: Section A Mathematics, vol. 143, no. 2, pp. 351–369, 2013.
• [10] V. Vassilevska-Williams, “Multiplying matrices in O(n^2.373) time”, Tech. Rep., Stanford University, 2014.
• [11] F. Le Gall, “Powers of tensors and fast matrix multiplication”, in ISSAC ’14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, 2014.
• [12] S. Winograd, “Some remarks on fast multiplication of polynomials”, Complexity of Sequential and Parallel Numerical Algorithms, J.F. Traub, Ed., Academic Press, New York, 1973, pp. 189–208.
• [13] T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to algorithms, The MIT Press, Cambridge, 2009.
• [14] P.C. Fischer, “Further Schemes for Combining Matrix Algorithms”, Automata, Languages and Programming. ICALP 1974. Lecture Notes in Computer Science, Loeck J., Ed., vol 14, pp. 428–436, 1974, doi: 10.1007/978-3-662-21545-6_32.
• [15] J.R. Hopcroft and L.R. Kerr, “On Minimizing the Number of Multiplications Necessary for Matrix Multiplication”, SIAM J. Appl. Math., vol. 20, no. 1, pp. 30–36, 1971.
• [16] R. Probert, “On the Complexity of Matrix Multiplication”, University of Waterloo, Comp. Sci. Tech. Report CS-73-27.
• [17] T. Kaczorek, Wektory i macierze w automatyce i elektrotechnice, 2nd ed. WNT, Warszawa, 1998, [in Polish].
• [18] J. Bunch and J. Hopcroft, “Triangular factorization and inversion by fast matrix multiplication”, Math. Comput., vol. 28, no. 125, pp. 231–236, 1974.
• [19] A. Schonhage, “Fast Schmidt Orthogonalization and Unitary Transformations of Large Matrices”, Complexity of Sequential and Parallel Numerical Algorithms, J.F. Traub, Ed., Academic Press, New York, 1973, pp. 283–291.
• [20] W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 1989, [in Polish].
• [21] A. Borodin and I. Munro, The Computational Complexity of Algebraic and Numeric Problems, Am. Elsevier Publ. Comp., New York, 1975.
• [22] O.H. Ibarra, S. Moran, and R. Hui, “A generalization of the fast LUP matrix decomposition algorithm and applications”, J. Alg., vol. 3, pp. 45–56, 1982.
• [23] W. Keller-Gehrig, “Fast algorithms for the characteristic polynomial”, Theor. Comput. Sci., vol. 36, pp. 309–317, 1985.
• [24] R. Seidel, “On the All-Pairs-Shortest-Path Problem”, in STOC ’92: Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing, ACM Press, New York, 1992, pp. 745–749.
• [25] N. Alon, Z. Galil, and O. Margalit, “On the exponent of the all pairs shortest path problem”, in Proc. 32nd Ann. IEEE Symp. on Found. Comp. Sci., 1991, pp. 569–575.
• [26] L.G. Valiant, “General context-free recognition in less than cubic time”, J. Comput. Syst. Sci., vol. 10, pp. 308–315, 1975.
• [27] I. Munro, “Efficient determination of the transitive closure of a directed graph”, Inform. Process. Lett., vol. 2, pp. 56–58, 1971.
• [28] M.J. Fisher and A.R. Meyer, “Boolean matrix multiplication and transitive closure”, in 12th IEEE Ann. Symp. on Switching and Automata Theory, 1971, pp. 129–131.
• [29] T. Kaczorek, “Structure decomposition of normal 2D transfer matrices”, Bull. Pol. Acad. Sci. Tech. Sci., vol. 52, no. 4, pp. 353-357, 2004.
• [30] X. Yang, D. Liu, D. Zhou, and R. Yang, “Moving cast shadow detection using block nonnegative matrix factorization”, Bull. Pol. Acad. Sci. Tech. Sci., vol. 66, no. 2, pp. 229–234, 2018, doi: 10.24425/122103.
• [31] J. Huang, T.M. Smith, G.M. Henry, and R.A. Geijn, “Strassen’s Algorithm Reloaded”, in SC’16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2016, pp. 690–701, doi: 10.1109/SC.2016.58.
• [32] M. Blaser, “On the complexity of the multiplication of matrices of small formats”, J. Complexity, vol. 19, no. 1, pp. 43-60, 2003, doi: 10.1016/S0885-064X(02)00007-9.
• [33] J.D. Laderman, “A noncommutative algorithm for multiplying 3 × 3 matrices using 23 multiplications”, Bull. Am. Math. Soc., vol. 82, no. 1, pp. 126–128, 1976.
• [34] A. Sedoglavic, “A noncommutative algorithm for multiplying 5 × 5 matrices using 99 multiplications”, hal-01562131v5, 2017.
• [35] T. Kaczorek, “Drazin inverse matrix method for fractional descriptor discrete-time linear systems”, Bull. Pol. Acad. Sci. Tech. Sci., vol. 64, no. 4, pp. 395–399, 2016. doi: 10.24425/bpas.2016.98076