Full Description
The ambition of this monograph is to show the methods of constructing fast matrix multiplication algorithms, and their applications, in an intelligible way, accessible not only to mathematicians. The scope and coverage of the book are comprehensive and constructive, and the analyses and algorithms can be readily applied by readers from various disciplines of science and technology who need modern tools and techniques related to fast matrix multiplication and related problems and techniques. Authors start from commutative algorithms, through exact non-commutative algorithms, partial algorithms to disjoint and arbitrary precision algorithms. Authors explain how to adapt disjoint algorithms to a single matrix multiplication and prove the famous tau-theorem in the (not so) special case. In an appendix, authors show how to work with confluent Vandermonde matrices, since they are used as an auxiliary tool in problems arising in fast matrix multiplication. Importantly, each algorithm is demonstrated by a concrete example of a decent dimensionality to ensure that all the mechanisms of the algorithms are illustrated. Finally, authors give a series of applications of fast matrix multiplication algorithms in linear algebra and other types of problems, including artificial intelligence.
Contents
Introduction.- Commutative matrix multiplication algorithms.- The exact non-commutative algorithms.- Triple disjoint algorithms with application to feasible matrix multiplication.- Arbitrary Precision Approximating Algorithms.- From disjoint to single matrix multiplication.- From partial to total matrix multiplication.- Summary of fast matrix multiplication algorithms.- Applications of the Fast Matrix Multiplication Algorithms.- Efficient Algorithms for Logical Matrices.- Appendix - Algorithms for (confluent) Vandermonde matrices.
