%% This LaTeX-file was created by <glmiller> Tue Jan 27 13:42:24 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

Lecture \#1, day 1, 1/12/98


\section{Matrix Multiplication}


\subsection{Naive method}

The naive method for doing matrix multiplication is the method typically taught
in math class. Multipy 2 matrices \( A*B=C \) by setting \( C_{ij}=\sum _{k=1}^{n}A_{ik}B_{kj} \). The number of multiplications
and additions is \( O(n^{3}) \) 


\subsection{Slightly less Naive method}

Divide the matrices into submatrices, multiply the submatrices, then recombine
the resulting matrices.

\( \left[ \begin{array}{cc}
A & B\\
C & D
\end{array}\right] *\left[ \begin{array}{cc}
E & F\\
G & H
\end{array}\right] =\left[ \begin{array}{cc}
AE+BG & AF+BH\\
CE+DG & CF+DH
\end{array}\right]  \)

\begin{itemize}
\item avoids thrashing the cache, but otherwise has the same time complexity
\end{itemize}

\subsection{Strassen's algorithm}

Strassen's algorithm starts by subdividing the matrices in the same manner as
the slightly less naive method, but then uses a different series of manipulations
to construct the result matrix with only 7 recursive calls, instead of the 8
used in the slightly less naive method. Complexities:

\begin{itemize}
\item Addition: \( A(n)=18\frac{n^{2}}{4}+7A(\frac{n}{2}) \) with \( A(1)=0 \). Solution: \( A(n)=6n^{\log _{2}7} \)
\item Multiplication: \( M(n)=7M(\frac{n}{2}) \) with \( M(1)=1 \). Solution: \( M(n)=n^{\log _{2}7} \)
\end{itemize}
One important note is that the constant \( 6 \) in \( A(n) \) for Strassen's algorithm is much
larger than the constant \( 1 \) in \( A(n) \) for the naive algorithms. This means there is
some size of matrix s.t. forall larger matrix multiplications strassen should
be used and for all smaller matrices, one of the naive methods should be used.

\end{document}