Subsection 2.6 Question 6
Question 6.
Let \(A \in \mathbb R^{m \times n} \) and \(x \in \mathbb R^n \text{.}\) How many floating point operations (flops) are required to compute the matrix-vector multiplication \(A x \text{?}\)
Answer
Solution
Answer
Approximately \(m n \) multiplies and \(m (n-1) \) adds, for a total of \(2 m n - m \) flops.
Solution
Let
\begin{equation*}
A =
\left( \begin{array}{ c c c c}
\alpha_{0,0} \amp \alpha_{0,1} \amp \cdots \amp
\alpha_{0,n-1} \\
\alpha_{1,0} \amp \alpha_{1,1} \amp \cdots \amp
\alpha_{1,n-1} \\
\vdots \amp \vdots \amp \amp \vdots \\
\alpha_{m-1,0} \amp \alpha_{m-1,1} \amp \cdots \amp
\alpha_{m-1,n-1} \\
\end{array} \right)
\mbox{ and }
x = \left( \begin{array}{c}
\chi_0 \\
\chi_1 \\
\vdots \\
\chi_{n-1}
\end{array} \right).
\end{equation*}
Then
\begin{equation*}
\begin{array}{rcl}
A x \amp = \amp
\left( \begin{array}{ c c c c}
\alpha_{0,0} \amp \alpha_{0,1} \amp \cdots \amp
\alpha_{0,n-1} \\
\alpha_{1,0} \amp \alpha_{1,1} \amp \cdots \amp
\alpha_{1,n-1} \\
\vdots \amp \vdots \amp \amp \vdots \\
\alpha_{m-1,0} \amp \alpha_{m-1,1} \amp \cdots \amp
\alpha_{m-1,n-1} \\
\end{array} \right)
\left( \begin{array}{c}
\chi_0 \\
\chi_1 \\
\vdots \\
\chi_{n-1}
\end{array} \right)\\
\amp = \amp
\left( \begin{array}{r r r r r}
\alpha_{0,0} \chi_0 + \amp \alpha_{0,1} \chi_1 + \amp
\cdots + \amp
\alpha_{0,n-1} \chi_{n-1} \\
\alpha_{1,0} \chi_0 + \amp \alpha_{1,1} \chi_1 + \amp
\cdots + \amp
\alpha_{1,n-1} \chi_{n-1} \\
\vdots ~~~~ \amp \vdots ~~~~ \amp \amp \vdots ~~~~ \\
\alpha_{m-1,0} \chi_0 + \amp \alpha_{m-1,1} \chi_1 +
\amp \cdots + \amp
\alpha_{m-1,n-1} \chi_{n-1}
\end{array} \right).
\end{array}
\end{equation*}
This exposes \(m n \) muiltiplications and \(m (n-1) \) additions, for a total of \(2 m n - m \) flops. We usually would state this as "approximately \(2 m n\) flops."