% rpb002a: Abstract only, AMS-Latex format, last revised 20000406
\newcommand{\lbrk}{{\linebreak[0]}}	% Useful in URLs
\documentstyle[11pt,amsa4]{amsart}
\bibliographystyle{plain}
\begin{document}

\title{Algorithms for Matrix Multiplication}

\author{R.\ P.\ Brent}
\address{Department of Computer Science\\
	Stanford University\\
	Stanford\\
	CA~94305\\
	USA}

\thanks{{\em{CR Categories}}. 5.11, 5.14, 5.19, 5.39.}

\thanks{Reproduction in whole or in part is permitted for any
purpose of the United States Government.}

\thanks{The preparation of this manuscript was supported in part by
the Office of Naval Research (NR~044~211),
the National Science Foundation (GJ~798),
and the Atomic Energy Commission (Stanford PA~\#18).}

\thanks{The author thanks R.\ Floyd and J.\ Herriot for their helpful advice,
and CSIRO (Australia) for its generous financial support.}

\thanks{Copyright \copyright\ 1970, R.~P.~Brent.}
\thanks{Comments \copyright\ 1993, 2000, R.~P.~Brent.}
\thanks{\hfill rpb002a typeset using \AmS-\LaTeX}

\keywords{Matrix multiplication, inner-product, error analysis,
scaling, Winograd, Strassen, computational complexity}

\subjclass{Primary 68Q25; Secondary 65F05, 65F35, 65F30, 65G99}

\maketitle
\thispagestyle{empty}

\vfil
\section*{Abstract} 
% This is expanded compared to original abstract
Strassen's and Winograd's algorithms for 
$n \times n$ matrix multiplication are
investigated and compared with the normal algorithm. 

The normal algorithm requires 
$n^3 + O(n^2)$
multiplications and about the same number of additions.
Winograd's algorithm almost halves the number of multiplications
at the expense of more additions. 
Strassen's algorithm reduces the total number of operations to
$O(n^{2.82})$
by recursively multiplying 
$2n \times 2n$ matrices using seven $n \times n$
matrix multiplications.

Floating-point
error bounds are obtained for both Strassen's and Winograd's methods.
It is shown that Strassen's method satisfies a certain numerical
stability property (albeit weaker than that satisfied by the normal method); 
and that scaling is essential
for numerical accuracy using Winograd's method. 

In practical cases, for moderate $n$,
Winograd's method appears to be slightly faster than the other two
methods, but the gain is, at most, about 20~percent. 
Strassen's method should be faster for sufficiently large $n$,
and this will be important in the future as memory sizes increase.

An attempt
to generalize Strassen's method is described.

\vfil
\section*{Comments}
This report describes a project undertaken as one of the requirements for
the degree of Master of Science, and hence may be regarded as the author's
master's thesis.
Only the Abstract is given here.
The full report appeared as~\cite{rpb002}.
For related work, see~\cite{rpb004,str69,win68}.

The error analysis of Strassen's algorithm shows that, although it is not
as stable component\-wise as the normal algorithm, it is sufficiently stable
to be usable in implementations of Level 3 Basic Linear Algebra Subroutines
(BLAS). (This was not pointed out in the report since Level 3 BLAS had not
been invented at the time.)

\vfil
\begin{thebibliography}{9}

\bibitem{rpb002}
R.\ P.\ Brent,
{\em Algorithms for Matrix Multiplication},
Report TR-CS-70-157, Computer Science Department,
Stanford University (March 1970), 52~pp.
Available from NTIS, \#AD705509.
Page images available from
{\tt ftp://elib.stanford.edu/{\lbrk}pub/{\lbrk}reports/{\lbrk}cs/{\lbrk}tr%
/{\lbrk}70/{\lbrk}157/{\lbrk}GIF-PAGE-IMAGES/} and from
{\tt ftp://ftp.comlab.ox.ac.uk/{\lbrk}pub/{\lbrk}Documents/{\lbrk}techpapers/%
{\lbrk}Richard.Brent/{\lbrk}rpb002/}
%rpb002.

\bibitem{rpb004}	% [12]
R.\ P.\ Brent,
``Error analysis of algorithms for matrix multiplication and
triangular decomposition using Winograd's identity'',
{\em Numerische Mathematik} 16 (1970), 145--156.
MR~43\#5702, CR~12\#21408.
rpb004.

\bibitem{str69}		% [5]
V.\ Strassen,
``Gaussian elimination is not optimal'',
{\em Numerische Mathematik} 13 (1969), 354--356.

\bibitem{win68}		% [7]
S.\ Winograd,
``A new algorithm for inner product'',
{\em IEEE Transactions on Computers} C-17 (1968), 693--694.

\end{thebibliography}
\end{document}
