Week 5 - Matrix- Matrix Multiplication

1. Composing Rotations

  • Rotate vector χ\chi through angle θ\theta then ρ\rho
  • Rθ((χ0χ1))=(cos(θ)sin(θ)sin(θ)cos(θ))(χ0χ1)R_{\theta}(\left(\begin{array}{c} \chi_{0} \\ \chi_1\end{array}\right)) =\left( \begin{array}{c|c} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{array} \right)\left(\begin{array}{c} \chi_{0} \\ \chi_1\end{array}\right)
  • Rρ(Rθ((χ0χ1)))=(cos(ρ)sin(ρ)sin(ρ)cos(ρ))((cos(θ)sin(θ)sin(θ)cos(θ))(χ0χ1))R_{\rho}(R_{\theta}(\left(\begin{array}{c} \chi_{0} \\ \chi_1\end{array}\right))) = \left( \begin{array}{c|c} \cos(\rho) & -\sin(\rho) \\ \sin(\rho) & \cos(\rho) \end{array} \right) \left( \left( \begin{array}{c|c} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{array} \right) \left(\begin{array}{c} \chi_{0} \\ \chi_1\end{array}\right) \right)
  • Rρ(Rθ((χ0χ1)))=(cos(ρ)sin(ρ)sin(ρ)cos(ρ))(cos(θ)sin(θ)sin(θ)cos(θ))(χ0χ1)R_{\rho}(R_{\theta}(\left(\begin{array}{c} \chi_{0} \\\chi_1\end{array}\right))) = \left( \begin{array}{c|c} \cos(\rho) & -\sin(\rho) \\ \sin(\rho) & \cos(\rho) \end{array} \right) \left( \begin{array}{c|c} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{array} \right) \left(\begin{array}{c} \chi_{0} \\ \chi_1\end{array}\right)
    • =(cos(ρ)cos(θ)sin(ρ)sin(θ)cos(ρ)sin(θ)sin(ρ)cos(θ)cos(ρ)sin(θ)+sin(ρ)cos(θ)cos(ρ)cos(θ)sin(ρ)sin(θ))(χ0χ1) = \left( \begin{array}{c|c} \cos(\rho)\cos(\theta) -\sin(\rho)\sin(\theta) & -\cos(\rho)\sin(\theta) - \sin(\rho)\cos(\theta)\\ \cos(\rho)\sin(\theta) + \sin(\rho)\cos(\theta) & \cos(\rho)\cos(\theta) - \sin(\rho)\sin(\theta) \end{array} \right) \left(\begin{array}{c|c} \chi_{0} \\ \chi_1\end{array}\right)
  • Rρ(Rθ((χ0χ1)))=Rθ+ρ((χ0χ1))=(cos(θ+ρ)sin(θ+ρ)sin(θ+ρ)cos(θ+ρ))(χ0χ1)R_{\rho}(R_{\theta}(\left(\begin{array}{c} \chi_{0} \\ \chi_1\end{array}\right))) = R_{\theta + \rho}(\left(\begin{array}{c|c} \chi_{0} \\ \chi_1\end{array}\right)) = \left( \begin{array}{c|c} \cos(\theta + \rho) & -\sin(\theta + \rho) \\ \sin(\theta + \rho) & \cos(\theta + \rho) \end{array} \right) \left(\begin{array}{c} \chi_{0} \\ \chi_1\end{array}\right)
    • cos(θ+ρ)=cos(ρ)cos(θ)sin(ρ)sin(θ)\cos(\theta + \rho) =\cos(\rho)\cos(\theta) -\sin(\rho)\sin(\theta)
    • sin(θ+ρ)=cos(ρ)sin(θ)+sin(ρ)cos(θ)\sin(\theta + \rho) = \cos(\rho)\sin(\theta) + \sin(\rho)\cos(\theta)

2. Observations

2.1. Transposing a Product of Matrices

  • Let ARm×k and BRk×n.(AB)T=BTAT.A \in \mathbb{R}^{m \times k} \text{ and }B \in \mathbb{R}^{k \times n}. (AB)^T = B^T A^T.
  • Let A,B and CA,B \text{ and } C be conformal matrices so that ABCABC is well-defined. Then (ABC)T=CTBTAT(ABC)^T = C^T B^T A^T.

2.2. Matrix-Matrix Multiplication with Special Matrices

  • Let ARm×nA \in \mathbb{R}^{m \times n} and let II denote the identity matrix of appropriate size.
    • AI=IA=AA I = I A = A
  • Let ARm×nA \in \mathbb R^{m \times n} and let DD denote the diagonal matrix with diagonal elements δ0,δ1,,δn1\delta_0, \delta_1, \cdots, \delta_{n-1}. Partition AA by columns : A=(a0a1an1).AD=(δ0a0δ1a1δn1an1).A= \left( \begin{array}{r|r|r|r} a_0 & a_1 & \dots & a_{n-1} \end{array} \right). AD= \left ( \begin{array}{r|r|r|r} \delta_0 a_0 & \delta_1 a_1 & \dots & \delta_{n-1}a_{n-1} \end{array} \right).
  • Let ARm×nA \in \mathbb R^{m \times n} and let DD denote the diagonal matrix with diagonal elements δ0,δ1,,δm1\delta_0, \delta_1, \cdots, \delta_{m-1}. Partition AA by rows : A=(a~0Ta~1Ta~m1T).DA=(δ0a~0Tδ1a~1Tδm1a~m1T).A= \left( \begin{array}{c} \widetilde a_0^{T} \\ \widetilde a_1^{T} \\ \vdots \\ \widetilde a_{m-1}^{T} \end{array} \right). DA= \left ( \begin{array}{c} \delta_0 \widetilde a_0^{T} \\ \delta_1 \widetilde a_1^{T} \\ \vdots \\ \delta_{m-1} \widetilde a_{m-1}^{T} \end{array} \right).
  • Let U,RRn×nU, R \in \mathbb{R}^{n \times n} be upper triangular matrices.
    • The product URUR is still an upper triangular matrix.
    • same as lower triangular.
  • Let ARm×nA \in \mathbb R^{m \times n}. ATAA^TA is symmetric.
    • (ATA)T=AT(AT)T=ATA(A^TA)^T = A^T(A^T)^T = A^TA
  • Let A,BRn×nA,B \in \mathbb R^{n \times n} be symmetric matrices. ABAB may be symmetric.
    1. B=AB = A
    2. A=I or B=IA = I \text{ or } B = I
    3. An example when this is false: A=(0110)B=(1112)AB=(1211)A= \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} B=\begin{pmatrix} 1 & -1 \\ -1 & 2 \end{pmatrix} AB=\begin{pmatrix} -1 & 2 \\ 1 & -1 \end{pmatrix}

3. Algorithms for Computing Matrix-Matrix Multiplication

  • Loops for computing C := AB
    • The easiest way is three loops via dot product:
  • Three other different ways: by Columns, by Rows and with Rank-1 Updates.
  • Computing C := AB by columns
    • Inner loop: c1T=a1TB+c1Tc_1^T = a_1^T B + c_1^T
  • Computing C := AB by rows
    • Inner loop: c1=Ab1+c1c_1 = A b_1 + c_1
  • Computing C := AB via rank-1 updates
    • Inner loop: C=a1b1t+CC = a_1b_1^t + C
    • Start with first column of A and first row of B. Notice that after calculating a0b~0Ta_0 \widetilde b_0^{T}, all of the elements in C are set to a new value. Like layer by layer to rewrite C.

4. Optimize Matrix Matrix Multiplication

5. Words

  • favorable ['feivərəbl] adj. 有利的;良好的;赞成的,赞许的;讨人喜欢的

results matching ""

    No results matching ""