Search

This paper studies Strassen’s algorithms for fast multiplication of two finite dimensional matrices. However, one pertinent issue that has deterred Strassen’s scheme from been considered for practical usage is determining the cross-over point. In this light, large matrices with different sizes were randomly generated on which Strassen and conventional matrix multiplication algorithms were implemented in MATLAB R2008b. Two MATLAB built-in functions nextpow2 and pow2 were used for implementing padding techniques to ensure that the matrices are to the power of two. Three different experiments were carried out using five, four and three levels of recursion (divide and conquer algorithm) respectively to determine the suitable cut-off point which were used to evaluate the optimal running time for Strassen’s algorithm. For each experiment, eight finite dimensional square matrices of real numbers were generated and iteratively multiplied. The experiment reveals that the cut-off point with five level of recursion optimized the Strassens time.

Strassen’s algorithm (1969) was the first sub-cubic matrix multiplication algorithm. Winograd (1971) improved the leading coefficient of its complexity from 6 to 7. There have been many subsequent asymptotic improvements. Unfortunately, most of these have the disadvantage of very large, often gigantic, hidden constants. Consequently, Strassen-Winograd’s O ( n log 2 7 ) algorithm often outperforms other fast matrix multiplication algorithms for all feasible matrix dimensions. The leading coefficient of Strassen-Winograd’s algorithm has been generally believed to be optimal for matrix multiplication algorithms with a 2 × 2 base case, due to the lower bounds by Probert (1976) and Bshouty (1995). Surprisingly, we obtain a faster matrix multiplication algorithm, with the same base case size and asymptotic complexity as Strassen-Winograd’s algorithm, but with the leading coefficient reduced from 6 to 5. To this end, we extend Bodrato’s (2010) method for matrix squaring, and transform matrices to an alternative basis. We also prove a generalization of Probert’s and Bshouty’s lower bounds that holds under change of basis, showing that for matrix multiplication algorithms with a 2 × 2 base case, the leading coefficient of our algorithm cannot be further reduced, and is therefore optimal. We apply our method to other fast matrix multiplication algorithms, improving their arithmetic and communication costs by significant constant factors.

In this paper we show that nxn matrices with entries from a semiring R which is generated additively by q generators can be multiplied in time O(q^2n^@w), where n^@w is the complexity for matrix multiplication over a ring (Strassen: @w

© 2016 Sandia Corporation, operator of Sandia National Laboratories for the U.S. Department of Energy. Fast algorithms for matrix multiplication, namely those that perform asymptotically fewer scalar operations than the classical algorithm, have been considered primarily of theoretical interest. Apart from Strassen's original algorithm, few fast algorithms have been efficiently implemented or used in practical applications. However, there exist many practical alternatives to Strassen's algorithm with varying performance and numerical properties. Fast algorithms are known to be numerically stable, but because their error bounds are slightly weaker than the classical algorithm, they are not used even in cases where they provide a performance benefit. We argue in this paper that the numerical sacrifice of fast algorithms, particularly for the typical use cases of practical algorithms, is not prohibitive, and we explore ways to improve the accuracy both theoretically and empirically. The numerical accuracy of fast matrix multiplication depends on properties of the algorithm and of the input matrices, and we consider both contributions independently. We generalize and tighten previous error analyses of fast algorithms and compare their properties. We discuss algorithmic techniques for improving the error guarantees from two perspectives: manipulating the algorithms, and reducing input anomalies by various forms of diagonal scaling. Finally, we benchmark performance and demonstrate our improved numerical accuracy.

The main purpose of this paper is to present a fast matrix multiplication algorithm taken from the paper of Laderman et al. (Linear Algebra Appl. 162-164 (1992) 557) in a refined compact "analytical" form and to demonstrate that it can be implemented as quite efficient computer code. Our improved presentation enables us to simplify substantially the analysis of the computational complexity and numerical stability of the algorithm as well as its computer implementation. The algorithm multiplies two N × N matrices using O(N2.7760) arithmetic operations. In the case where N = 18 ċ 48k, for a positive integer k, the total number of flops required by the algorithm is 4.894N2.7760 - 16.165N2, which may be compared to a similar estimate for the Winograd algorithm, 3.732N2.8074 - 5N2 flops, N = 8 ċ 2k, the latter being current record bound among all known practical algorithms. Moreover, we present a pseudo-code of the algorithm which demonstrates its very moderate working memory requirements, much smaller than that of the best available implementations of Strassen and Winograd algorithms. For matrices of medium-large size (say, 2000 ≤ N < 10,000) we consider one-level algorithms and compare them with the (multilevel) Strassen and Winograd algorithms. The results of numerical tests clearly indicate that our accelerated matrix multiplication routines implementing two or three disjoint product-based algorithm are comparable in computational time with an implementation of Winograd algorithm and clearly outperform it with respect to working space and (especially) numerical stability. The tests were performed for the matrices of the order of up to 7000, both in double and single precision.

The purpose of this paper is to present an algorithm for matrix multiplication based on a formula discovered by Pan [7]. For matrices of order up to 10 000, the nearly optimum tuning of the algorithm results in a rather clear non-recursive one- or two-level structure with the operation count comparable to that of the Strassen algorithm [9]. The algorithm takes less workspace and has better numerical stability as compared to the Strassen algorithm, especially in Winograd's modification [2]. Moreover, its clearer and more flexible structure is potentially more suitable for efficient implementation on modern supercomputers. Copyright © 1999 John Wiley & Sons, Ltd.

Matrix multiplication is one of the basic operations in linear algebra that mostly used in computer science. For ages, applying naive algorithm to complete it has done it, and it has a standard complexity O(n3). Many researches are concluded to find more efficient and effective algorithm to process this operation, and one day Strassen has one that overcome the naive algorithm complexity with only O(n2.8074). The basic concept of this algorithm is divide and conquer (DnC) but with adjustment, to break the limitation of memory in a GPU computation. An idea to overcome this limit is to combine CPU and GPU processing, which implement Strassen algorithm. This paper shows the result of breaking through GPU memory limitation, checking the accuracy of the algorithm, compare the running time result and the most important thing is to make sure this algorithm can process bigger matrix than the naive one. Through the created charts and tables based on each performances, it showed that the maximum size of data samples that are processed by Strassen Algorithm reach 32.768 for (2n×2n) matrix size, which is bigger than the naive algorithm 8.192 could process. Also for all attempt to matrices with larger than 2048, the running times are way faster, about 0.04 seconds to 0.2 seconds for worst case scenario, and overcome the one with naive algorithm.

Parallel matrix multiplication is one of the most studied fundamental problems in distributed and high performance computing. We obtain a new parallel algorithm that is based on Strassen's fast matrix multiplication and minimizes communication. The algorithm outperforms all known parallel matrix multiplication algorithms, classical and Strassen-based, both asymptotically and in practice. A critical bottleneck in parallelizing Strassen's algorithm is the communication between the processors. Ballard, Demmel, Holtz, and Schwartz (SPAA'11) prove lower bounds on these communication costs, using expansion properties of the underlying computation graph. Our algorithm matches these lower bounds, and so is communication-optimal. It exhibits perfect strong scaling within the maximum possible range. Benchmarking our implementation on a Cray XT4, we obtain speedups over classical and Strassen-based algorithms ranging from 24% to 184% for a fixed matrix dimension n=94080, where the number of nodes ranges from 49 to 7203. Our parallelization approach generalizes to other fast matrix multiplication algorithms., 13 pages, 3 figures

Matrix multiplication is a very common operation performed in many real world applications. So much of research has been done in reducing the time complexity of multiplying two matrices by researchers like Strassen, Don Coppersmith, Shmuel Winograd etc. All mathematical software also rely upon the common matrix multiplication algorithm. But, if the matrices that has to be applied has some special properties in some applications, then their multiplication complexity can be reduced. So, in this paper a new algorithm for multiplying a special kind of n x n matrices which are used in analyzing electrical circuits is devised. This algorithm outperforms the previous fast recursive algorithm for matrix multiplication.

Since Volker Strassen proposed a recursive matrix multiplication algorithm reducing the time complexity to n2.81 in 1968, many scholars have done a lot of research on this basis. In recent years, researchers have proposed using computer algorithms to solve fast matrix multiplication problem. They have found Strassen's algorithm or other algorithms that have the same time complexity as Strassen algorithm by using genetic algorithm. In this paper, we used random search algorithm to find the matrix multiplication algorithms that require fewer multiplications. And we used combining Gaussian elimination for the first time to improve calculation speed; meanwhile we improved the local search technology to enhance the local search capability of the algorithm. In the numerical experiments of 2×2 matrices, the results verified the effectiveness of the algorithm. Compared with the existing genetic algorithm, the new method has obvious advantage of quick search, and found some of new matrix multiplication algorithms.

International audience; We propose several new schedules for Strassen-Winograd's matrix multiplication algorithm, they reduce the extra memory allocation requirements by three different means: by introducing a few pre-additions, by overwriting the input matrices, or by using a first recursive level of classical multiplication. In particular, we show two fully in-place schedules: one having the same number of operations, if the input matrices can be overwritten; the other one, slightly increasing the constant of the leading term of the complexity, if the input matrices are read-only. Many of these schedules have been found by an implementation of an exhaustive search algorithm based on a pebble game.

We propose a new algorithm for fast multiplication of large integers having a precision of 1k computer words, where k is an integer. The algorithm is derived from the Karatsuba-Ofman Algorithm and has the same asymptotic complexity. However, the running time of the new algorithm is slightly better, and it makes one third as many recursive calls.

IT IS shown that Karatsubi's algorithm, applied to the problem of calculating the product of matrices, is transformed into Strassen's algorithm.