Search

The Strassen algorithm for multiplying 22 matrices requires seven multiplications and 18 additions. The recursive use of this algorithm for matrices of dimension n yields a total arithmetic complexity of (7n2.816n2) for n=2k. Winograd showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying 22 matrices with seven multiplications is called a Strassen-like algorithm. Winograd also discovered an additively optimal Strassen-like algorithm with 15 additions. This algorithm is called the Winograd's variant, whose arithmetic complexity is (6n2.815n2) for n=2k and (3.73n2.815n2) for n=82k, which is the best-known bound for Strassen-like multiplications. This paper proposes a method that reduces the complexity of Winograd's variant to (5n2.81+0.5n2.59+2n2.326.5n2) for n=2k. It is also shown that the total arithmetic complexity can be improved to (3.55n2.81+0.148n2.59+1.02n2.326.5n2) for n=82k, which, to the best of our knowledge, improves the best-known bound for a Strassen-like matrix multiplication algorithm.

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.

Consider the multiplication of two n×n matrices. A straight-forward sequential algorithm for computing the product takes Θ(n3) time. Strassen [20] presented an algorithm that takes Θ(n1g 7) time; lg denotes logarithm to the base 2; lg 7 is about 2.81.Now, consider the implementation of these two algorithms (straight-forward and Strassen) in the mapReduce framework. Several papers have studied mapReduce implementations of the straight-forward algorithm; this algorithm can be implemented using a constant number (typically, one or two) of mapReduce passes. In this paper, we study the mapReduce implementation of Strassen's algorithm.If we unwind the recursion, Strassen's algorithm consists of three parts, Parts I-III. Direct mapReduce implementations of the three parts take lg n, 1 and lg n passes, respectively; total number of passes is 2 lg n+1. We show that Part I can be implemented in 2 passes, with total work Θ(n1g 7), and reducer size and reducer workload o(n). We believe that Part III can also be implemented, with small reducer size and workload, in a constant number of passes; this is future work.

In this work an efficient algorithm to perform a block decomposition for large dense rectangular matrices with entries in F"2 is presented. Matrices are stored as column blocks of row major matrices in order to facilitate rows operation and matrix multiplications with blocks of columns. One of the major bottlenecks of matrix decomposition is the pivoting involving both rows and column exchanges. Since row swaps are cheap and column swaps are order of magnitude slower, the number of column swaps should be reduced as much as possible. Here an algorithm that completely avoids the column permutations is presented. An asymptotically fast algorithm is obtained by combining the four Russian algorithm and the recursion with the Strassen algorithm for matrix-matrix multiplication. Moreover optimal parameters for the tuning of the algorithm are theoretically estimated and then experimentally verified. A comparison with the state of the art public domain software SAGE shows that the proposed algorithm is generally faster.

Algorithms have historically been evaluated in terms of the number of arithmetic operations they performed. This analysis is no longer sufficient for predicting running times on today's machines. Moving data through memory hierarchies and among processors requires much more time (and energy) than performing computations. Hardware trends suggest that the relative costs of this communication will only increase. Proving lower bounds on the communication of algorithms and finding algorithms that attain these bounds are therefore fundamental goals. We show that the communication cost of an algorithm is closely related to the graph expansion properties of its corresponding computation graph. Matrix multiplication is one of the most fundamental problems in scientific computing and in parallel computing. Applying expansion analysis to Strassen's and other fast matrix multiplication algorithms, we obtain the first lower bounds on their communication costs. These bounds show that the current sequential algorithms are optimal but that previous parallel algorithms communicate more than necessary. Our new parallelization of Strassen's algorithm is communication-optimal and outperforms all previous matrix multiplication algorithms.

Bini-Capovani-Lotti-Romani approximate formula (or border rank) for matrix multiplication achieves a better complexity than Strassen’s matrix multiplication formula. In this article, we show a novel way to use the approximate formula in the special case where the ring is Z / p Z . In addition, we show an implementation à la FFLAS--FFPACK, where p is a word-size modulo, that improves on state-of-the-art Z / p Z matrix multiplication implementations.

In 1968, Volker Strassen, a young German mathematician, announced a clever algorithm to reduce the asymptotic complexity of n×n matrix multiplication from the order of n 3 to n 2.81. It soon became one of the most famous scientific discoveries in the 20th century and provoked numerous studies by other mathematicians to improve upon it. Although a number of improvements have been made, Strassen's algorithm is still optimal in his original framework, the bilinear systems of 2 × 2 matrix multiplication, and people are still curious how Strassen developed his algorithm. We examined it to see if we could automatically reproduce Strassen's discovery using a search algorithm and find other algorithms of the same quality. In total, we found 608 algorithms that have the same quality as Strassen's, including Strassen's original algorithm. We partitioned the algorithms into nine different groups based on the way they are constructed. This paper was made possible by the combination of genetic search and linear-algebraic techniques. To the best of our knowledge, this is the first work that automatically reproduced Strassen's algorithm, and furthermore, discovered new algorithms with equivalent asymptotic complexity using a search algorithm.

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.

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O(n2.3755). Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le~Gall has led to an improved algorithm running in time O(n2.3729). These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time O(n2.3725), and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078}); in particular, this approach cannot prove the conjecture that for every e > 0, two n x n matrices can be multiplied in time O(n2+e).We describe a new framework extending the original laser method, which is the method underlying the previously mentioned algorithms. Our framework accommodates the algorithms by Coppersmith and Winograd, Stothers, Vassilevska-Williams and Le~Gall. We obtain our main result by analyzing this framework. The framework also explains why taking tensor powers of the Coppersmith--Winograd identity results in faster algorithms.

Gaussian elimination is a key algorithm in linear algebra. It has many usages, for instance solving systems of linear equations and determining whether a set of vectors is linearly independent. This algorithm transforms an input matrix into a matrix in row (column) echelon form. The matrix entries and the transformations are defined over algebraic fields either infinite (e.g. the real numbers) or finite (e.g. GF (2)). This work discusses a vector implementation of this algorithm over GF (2). The evaluation develops a case study that searches exhaustively for algorithms over GF (2) similar to Strassen's algorithm (a matrix-multiply algorithm with sub cubic complexity) because the search engine requires solving a huge number of Gaussian eliminations over GF (2). Our vector implementation allows the search engine to complete the exploration in less than nine hours on a commodity processor supporting AVX2, outperforming by 1.92X a scalar-SWAR implementation specialized for the case study and by 7.43X a generic scalar-SWAR implementation. Our results show that, over GF (2), there are 20 algorithms similar to Strassen's.

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.

International audience; In a seminal work at EUROCRYPT '96, Coppersmith showed how to find all small roots of a univariate polynomial congruence in polynomial time: this has found many applications in public-key cryptanalysis and in a few security proofs. However, the running time of the algorithm is a high-degree polynomial, which limits experiments: the bottleneck is an LLL reduction of a high-dimensional matrix with extra-large coefficients. We present in this paper the first significant speedups over Coppersmith's algorithm. The first speedup is based on a special property of the matrices used by Coppersmith's algorithm, which allows us to provably speed up the LLL reduction by rounding, and which can also be used to improve the complexity analysis of Coppersmith's original algorithm. The exact speedup depends on the LLL algorithm used: for instance, the speedup is asymptotically quadratic in the bit-size of the small-root bound if one uses the Nguyen-Stehlé L2 algorithm. The second speedup is heuristic and applies whenever one wants to enlarge the root size of Coppersmith's algorithm by exhaustive search. Instead of performing several LLL reductions independently, we exploit hidden relationships between these matrices so that the LLL reductions can be somewhat chained to decrease the global running time. When both speedups are combined, the new algorithm is in practice hundreds of times faster for typical parameters.

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.

Fast matrix multiplication algorithms of Strassen and Winograd are known to have weaker numerical accuracy than usual (inner product) multiplication. In this paper, we show that scaling usually improves accuracy when operands have elements of widely varying magnitude. We also propose estimators for numerical errors, based on samples of the result. All these estimators can be computed in \(O(n^2)\) operations. Experiments prove the effectiveness of the scaling idea and of the absolute error estimator.

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.

We present an algorithm for matrix inversion that combines the practical requirement of an optimal number of arithmetic operations and the theoretical goal of a polylogarithmic critical path length. The algorithm reduces inversion to matrix multiplication. It uses Strassen's recursion scheme but on the critical path, it breaks the recursion early switching to an asymptotically inefficient yet fast use of Newton's method. We also show that the algorithm is numerically stable. Overall, we get a candidate for a massively parallel algorithm that scales to exascale systems even on relatively small inputs. Preliminary experiments on multicore machines give the surprising result that even on such moderately parallel machines the algorithm outperforms Intel's Math Kernel Library and that Strassen's algorithm seems to be numerically more stable than one might expect.

In this paper, we give what we believe to be the first high performance parallel implementation of Strassen''s algorithm for matrix multiplication. We show how under restricted conditions, this algorithm can be implemented plug compatible with standard parallel matrix multiplication algorithms. Results obtained on a large Intel Paragon system show a 10-20% reduction in execution time compared to what we believe to be the fastest standard parallel matrix multiplication implementation available at this time.

Strassen's algorithm multiplies two numerical matrices fast, but when applied to interval matrices, leads to excess width. We use Rump's interval arithmetic to propose an interval version of Strassen's algorithm whose only excess width is in second order terms.

Algorithms of matrix multiplication are widely used in software engineering field. Application of Strassen algorithm makes a significant contribution to optimize the algorithm . Therefore, thorough study based on time complexity of matrix multiplication algorithm is very important. This paper talks about the time complexity of Strassen algorithm and general algorithm for matrix multiplication, and makes a comparison between the two algorithm routines so as to discuss the advantages and disadvantages of Strassen algorithm. The rational utilization plan of matrix multiplication algorithms is also discussed. Keywords-algorithms for matrix multiplication; time complexity; Strassen algorithm I. A GENERAL ALGORITHM FOR MATRIX MULTIPLICATION Let A=(aij)m × n be an m × n matrix, and let B=(bij)n × p be an n × p matrix. Given an (m×p) matrix A with r row partitions and s column partitions and a (p×n) matrix with s row partitions and t column partitions that are compatible with the partitions of A, the matrix product C=A×B. generally we can explain the matrix multiplication through the following expression, i.e.

A parallel algorithm has perfect strong scaling if its running time on $P$ processors is linear in $1/P$, including all communication costs. Distributed-memory parallel algorithms for matrix multiplication with perfect strong scaling have only recently been found. One is based on classical matrix multiplication (Solomonik and Demmel, 2011), and one is based on Strassen's fast matrix multiplication (Ballard, Demmel, Holtz, Lipshitz, and Schwartz, 2012). Both algorithms scale perfectly, but only up to some number of processors where the inter-processor communication no longer scales. We obtain a memory-independent communication cost lower bound on classical and Strassen-based distributed-memory matrix multiplication algorithms. These bounds imply that no classical or Strassen-based parallel matrix multiplication algorithm can strongly scale perfectly beyond the ranges already attained by the two parallel algorithms mentioned above. The memory-independent bounds and the strong scaling bounds generalize to other algorithms.

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-matrix multiplication is normally computed using one of the BLAS or a reinvention of part of the BLAS. Unfortunately, the BLAS were designed with small matrices in mind. When huge, well-conditioned matrices are multiplied together, the BLAS perform like the blahs, even on vector machines. For matrices where the coefficients are well conditioned. Winograd's variant of Strassen's algorithm offers some relief, but is rarely available in a quality form on most computers. We reconsider this method and offer a highly portable solution based on the Level 3 BLAS interface.

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.

Strassen's method is not the asymptotically fastest known matrix multiplication algorithm, but it is the most widely used for large matrices. Since his manuscript was published, a number of variants have been proposed with different addition complexities. Here we describe a new one. The new variant is at least as good as those already known for simple matrix multiplication, but can save operations either for chain products or for squaring. Moreover it can be proved optimal for these tasks. The largest saving is shown for nth-power computation, in this scenario the additive complexity can be halved, with respect to original Strassen's.

Coppersmith described at Eurocrypt 96 an algorithm for finding small roots of bivariate integer polynomial equations, based on lattice reduction. A simpler algorithm was later proposed in [9], but it was asymptotically less efficient than Coppersmith's algorithm. In this paper, we describe an analogous simplification but with the same asymptotic complexity as Coppersmith. We illustrate our new algorithm with the problem of factoring RSA moduli with high-order bits known; in practical experiments our method is several orders of magnitude faster than [9].

Strassen's matrix multiplication (MM) has benefits with respect to any (highly tuned) implementations of MM because Strassen's reduces the total number of operations. Strassen achieved this operation reduction by replacing computationally expensive MMs with matrix additions (MAs). For architectures with simple memory hierarchies, having fewer operations directly translates into an efficient utilization of the CPU and, thus, faster execution. However, for modern architectures with complex memory hierarchies, the operations introduced by the MAs have a limited in-cache data reuse and thus poor memory-hierarchy utilization, thereby overshadowing the (improved) CPU utilization, and making Strassen's algorithm (largely) useless on its own.In this paper, we investigate the interaction between Strassen's effective performance and the memory-hierarchy organization. We show how to exploit Strassen's full potential across different architectures. We present an easy-to-use adaptive algorithm that combines a novel implementation of Strassen's idea with the MM from automatically tuned linear algebra software (ATLAS) or GotoBLAS. An additional advantage of our algorithm is that it applies to any size and shape matrices and works equally well with row or column major layout. Our implementation consists of introducing a final step in the ATLAS/GotoBLAS-installation process that estimates whether or not we can achieve any additional speedup using our Strassen's adaptation algorithm. Then we install our codes, validate our estimates, and determine the specific performance.We show that, by the right combination of Strassen's with ATLAS/GotoBLAS, our approach achieves up to 30%/22% speed-up versus ATLAS/GotoBLAS alone on modern high-performance single processors. We consider and present the complexity and the numerical analysis of our algorithm, and, finally, we show performance for 17 (uniprocessor) systems.

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.

In this paper we study the impact of the simultaneous exploitation of data- and task-parallelism, so called mixed-parallelism, on the Strassen and Winograd matrix multiplication algorithms. This work takes place in the context of Grid computing and, in particular, in the Client-Agent(s)-Server(s) model, where data can already be distributed on the platform. For each of those algorithms, we propose two mixed-parallel implementations. The former follows the phases of the original algorithms while the latter has been designed as the result of a list scheduling algorithm. We give a theoretical comparison, in terms of memory usage and execution time, between our algorithms and classical data-parallel implementations. This analysis is corroborated by experiments. Finally, we give some hints about heterogeneous and recursive versions of our algorithms

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.

The Fortran-90 standard requires an intrinsic function matmul which multiplies two matrices together to produce a third as the result. However, the standard does not specify which algorithm to use. We consider an extension to the matmul syntax which allows a Winograd variant of Strassen's algorithm to be added. We discuss an implementation that is in a commercial Fortran-90 offering.

In SIAM J. Comput., vol.5, p.187-203 (1976), R.L. Probert proved that 15 additive operations are necessary and sufficient to multiply two 2*2 matrices over the binary field by a bilinear algorithm using seven non-scalar multiplications. The author proves this result for arbitrary field. The algorithm of Winograd is used to classify all such algorithms (S. Winograd, 1971). >

A detailed analysis of Strassen's multiplication algorithm is presented; the analysis consists in deriving a symbolic formula, called time-formula, expressing the time taken to perform matrix multiplications using a combination of Strassen's and the regular method. The variables in the formula represent the time taken to perform the basic operations that can be executed in present day computers; these include arithmetic operations; subscripting, iteration overhead, etc. By binding actual numerical values, corresponding to a given compiler-machine configuration, to the variables one can determine the execution time for that configuration. The derived time-formula corresponds to an optimized and non-recursive version of Strassen's algorithm. This version uses a special scheme for positioning the elements of the matrices, the scheme being particularly suitable for usage in a paging environment. It has been found that Strassen's method can be used in multiplying 40 × 40 matrices (on an Algol-PDP-10 configuration) in a slightly better time than the standard method. Curves expressing the speed-up achieved by Strassen's method are presented. This information is substantiated by benchmarks.

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

The two main results of this note are: (i) The minimum number of multiplications required to multiply two 2 X 2 matrices is seven. (ii) The minimum number of multiplications/divisions required to multiply two complex numbers is three.

Strassen''s and Winograd''s algorithms for matrix multiplication are investigated and compared with the normal algorithm. Floating-point error bounds are obtained, and it is shown that scaling is essential for numerical accuracy using Winograd''s method. In practical cases Winograd''s method appears to be slightly faster than the other two methods, but the gain is, at most, about 20%. Finally, an attempt to generalize Strassen''s method is described.