pset3sol.lyx

#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass article
\begin_preamble

\renewcommand{\vec}[1]{\mathbf{#1}}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}

\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\end_preamble
\use_default_options false
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "times" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry true
\use_package amsmath 2
\use_package amssymb 2
\use_package cancel 1
\use_package esint 0
\use_package mathdots 0
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 0
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\topmargin 1in
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 2
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Section*
18.335 Problem Set 3 Solutions
\end_layout

\begin_layout Subsection*
Problem 2: QR and orthogonal bases (10+(5+5+5) points)
\end_layout

\begin_layout Enumerate
Trefethen, problem 10.4:
\begin_inset Separator latexpar
\end_inset


\end_layout

\begin_deeper
\begin_layout Enumerate
e.g.
 consider 
\begin_inset Formula $\theta=\pi/2$
\end_inset

 (
\begin_inset Formula $c=0$
\end_inset

, 
\begin_inset Formula $s=1$
\end_inset

): 
\begin_inset Formula $Je_{1}=-e_{2}$
\end_inset

 and 
\begin_inset Formula $Je_{2}=e_{1}$
\end_inset

, while 
\begin_inset Formula $Fe_{1}=e_{2}$
\end_inset

 and 
\begin_inset Formula $Fe_{2}=e_{1}$
\end_inset

.
 
\begin_inset Formula $J$
\end_inset

 rotates clockwise in the plane by 
\begin_inset Formula $\theta$
\end_inset

.
 
\begin_inset Formula $F$
\end_inset

 is easier to interpret if we write it as 
\begin_inset Formula $J$
\end_inset

 multiplied on the right by 
\begin_inset Formula $[-1,0;0,1]$
\end_inset

: i.e., 
\begin_inset Formula $F$
\end_inset

 corresponds to a mirror reflection through the 
\begin_inset Formula $y$
\end_inset

 (
\begin_inset Formula $e_{2}$
\end_inset

) axis followed by clockwise rotation by 
\begin_inset Formula $\theta$
\end_inset

.
 More subtly, 
\begin_inset Formula $F$
\end_inset

 corresponds to reflection through a mirror plane corresponding to the 
\begin_inset Formula $y$
\end_inset

 axis rotated clockwise by 
\begin_inset Formula $\theta/2$
\end_inset

.
 That is, let 
\begin_inset Formula $c_{2}=\cos(\theta/2)$
\end_inset

 and 
\begin_inset Formula $s_{2}=\cos(\theta/2)$
\end_inset

, in which case (recalling the identities 
\begin_inset Formula $c_{2}^{2}-s_{2}^{2}=c$
\end_inset

, 
\begin_inset Formula $2s_{2}c_{2}=s$
\end_inset

): 
\begin_inset Formula 
\[
\left(\begin{array}{cc}
c_{2} & s_{2}\\
-s_{2} & c_{2}
\end{array}\right)\left(\begin{array}{cc}
-1 & 0\\
0 & 1
\end{array}\right)\left(\begin{array}{cc}
c_{2} & -s_{2}\\
s_{2} & c_{2}
\end{array}\right)=\left(\begin{array}{cc}
-c_{2} & s_{2}\\
s_{2} & c_{2}
\end{array}\right)\left(\begin{array}{cc}
c_{2} & -s_{2}\\
s_{2} & c_{2}
\end{array}\right)=\left(\begin{array}{cc}
-c & s\\
s & c
\end{array}\right)=F,
\]

\end_inset

which shows that 
\begin_inset Formula $F$
\end_inset

 is reflection through the 
\begin_inset Formula $y$
\end_inset

 axis rotated by 
\begin_inset Formula $\theta/2$
\end_inset

.
\end_layout

\begin_layout Enumerate
The key thing is to focus on how we perform elimination under a single column
 of 
\begin_inset Formula $A$
\end_inset

, which we then repeat for each column.
 For Householder, this is done by a single Householder rotation.
 Here, since we are using 
\begin_inset Formula $2\times2$
\end_inset

 rotations, we have to eliminate under a column one number at a time: given
 2-component vector 
\begin_inset Formula $x=\left(\begin{array}{c}
a\\
b
\end{array}\right)$
\end_inset

 into 
\begin_inset Formula $Jx=\left(\begin{array}{c}
\Vert x\Vert_{2}\\
0
\end{array}\right)$
\end_inset

, where 
\begin_inset Formula $J$
\end_inset

 is clockwise rotation by 
\begin_inset Formula $\theta=\tan^{-1}(b/a)$
\end_inset

 [or, on a computer, 
\begin_inset Formula $\mbox{atan2}(b,a)$
\end_inset

].
 Then we just do this working 
\begin_inset Quotes eld
\end_inset

bottom-up
\begin_inset Quotes erd
\end_inset

 from the column: rotate the bottom two rows to introduce one zero, then
 the next two rows to introduce a second zero, etc.
\end_layout

\begin_layout Enumerate
The flops to compute the 
\begin_inset Formula $J$
\end_inset

 matrix itself are asymptotically irrelevant, because once 
\begin_inset Formula $J$
\end_inset

 is computed it is applied to many columns (all columns from the current
 one to the right).
 To multiply 
\begin_inset Formula $J$
\end_inset

 by a single 
\begin_inset Formula $2$
\end_inset

-component vector requires 4 multiplications and 2 additions, or 6 flops.
 That is, 6 flops per row per column of the matrix.
 In contrast, Householder requires each column 
\begin_inset Formula $x$
\end_inset

 to be rotated via 
\begin_inset Formula $x=x-2v(v^{*}x)$
\end_inset

.
 If 
\begin_inset Formula $x$
\end_inset

 has 
\begin_inset Formula $m$
\end_inset

 components, 
\begin_inset Formula $v^{*}x$
\end_inset

 requires 
\begin_inset Formula $m$
\end_inset

 multiplications and 
\begin_inset Formula $m-1$
\end_inset

 additions, multiplication by 
\begin_inset Formula $2v$
\end_inset

 requires 
\begin_inset Formula $m$
\end_inset

 more multiplications, and then subtraction from 
\begin_inset Formula $x$
\end_inset

 requires 
\begin_inset Formula $m$
\end_inset

 more additions, for 
\begin_inset Formula $4m-1$
\end_inset

 flops overall.
 That is, asymptotically 4 flops per row per column.
 The 6 flops of Givens is 50% more than the 4 of Householder.
\begin_inset Newline newline
\end_inset


\begin_inset Newline newline
\end_inset

The reason that Givens is still considered interesting and useful is that
 (as we shall see in the next problem set), it can be used to exploit 
\emph on
sparsity
\emph default
: because it rotates only two elements at a time in each column, from the
 bottom up, if a column ends in zeros then the zero portion of the column
 can be skipped.
\end_layout

\end_deeper
\begin_layout Enumerate
If 
\begin_inset Formula $A=QR$
\end_inset

, then 
\begin_inset Formula $B=RQ=Q^{*}AQ=Q^{-1}AQ$
\end_inset

 is a similarity transformation, and hence has the same eigenvalues as shown
 in the book.
 Numerically (and as explained in class and in lecture 28), doing this repeatedl
y for a Hermitian 
\begin_inset Formula $A$
\end_inset

 (the unshifted QR algorithm) converges to a diagonal matrix 
\begin_inset Formula $\Lambda$
\end_inset

 of the eigenvalues in descending order.
 To get the eigenvectors, we observe that if the 
\begin_inset Formula $Q$
\end_inset

 matrices from each step are 
\begin_inset Formula $Q_{1}$
\end_inset

, 
\begin_inset Formula $Q_{2}$
\end_inset

, and so on, then we are computing 
\begin_inset Formula $\cdots Q_{2}^{*}Q_{1}^{*}AQ_{1}Q_{2}\cdots=\Lambda$
\end_inset

, or 
\begin_inset Formula $A=Q\Lambda Q^{*}$
\end_inset

 where 
\begin_inset Formula $Q=Q_{1}Q_{2}\cdots$
\end_inset

.
 By comparison to the formula for diagonalizing 
\begin_inset Formula $A$
\end_inset

, the columns of 
\begin_inset Formula $Q$
\end_inset

 are the eigenvectors.
\end_layout

\begin_layout Enumerate
Trefethen, problem 28.2:
\begin_inset Separator latexpar
\end_inset


\end_layout

\begin_deeper
\begin_layout Enumerate
In general, 
\begin_inset Formula $r_{ij}$
\end_inset

 is nonzero (for 
\begin_inset Formula $i<j$
\end_inset

) if column 
\begin_inset Formula $i$
\end_inset

 is non-orthogonal to column 
\begin_inset Formula $j$
\end_inset

.
 For a tridiagonal matrix 
\begin_inset Formula $A$
\end_inset

, only columns within two columns of one another are non-orthogonal (overlapping
 in the nonzero entries), so 
\begin_inset Formula $R$
\end_inset

 should only be nonzero (in general) for the diagonals and for two entries
 above each diagonal; i.e.
 
\begin_inset Formula $r_{ij}$
\end_inset

 is nonzero only for 
\begin_inset Formula $i=j$
\end_inset

, 
\begin_inset Formula $i=j-1$
\end_inset

, and 
\begin_inset Formula $i=j-2$
\end_inset

.
\begin_inset Newline newline
\end_inset


\begin_inset Newline newline
\end_inset

Each column of the 
\begin_inset Formula $Q$
\end_inset

 matrix involves a linear combination of all the previous columns, by induction
 (i.e.
 
\begin_inset Formula $q_{2}$
\end_inset

uses 
\begin_inset Formula $q_{1}$
\end_inset

, 
\begin_inset Formula $q_{3}$
\end_inset

uses 
\begin_inset Formula $q_{2}$
\end_inset

 and 
\begin_inset Formula $q_{1}$
\end_inset

, 
\begin_inset Formula $q_{4}$
\end_inset

 uses 
\begin_inset Formula $q_{3}$
\end_inset

 and 
\begin_inset Formula $q_{2}$
\end_inset

, 
\begin_inset Formula $q_{5}$
\end_inset

 uses 
\begin_inset Formula $q_{4}$
\end_inset

 and 
\begin_inset Formula $q_{3}$
\end_inset

, and so on).
 This means that an entry 
\begin_inset Formula $(i,j)$
\end_inset

 of 
\begin_inset Formula $Q$
\end_inset

 is zero (in general) only if 
\begin_inset Formula $a_{i,1:j}=0$
\end_inset

 (i.e., that entire row of 
\begin_inset Formula $A$
\end_inset

 is zero up to the 
\begin_inset Formula $j$
\end_inset

-th column).
 For the case of tridiagonal 
\begin_inset Formula $A$
\end_inset

, this means that 
\begin_inset Formula $Q$
\end_inset

 will have upper-Hessenberg form.
\end_layout

\begin_layout Enumerate

\series bold
Note:
\series default
 In the problem, you are told that 
\begin_inset Formula $A$
\end_inset

 is symmetric and tridiagonal.
 You must also assume that 
\begin_inset Formula $A$
\end_inset

 is real, or alternatively that 
\begin_inset Formula $A$
\end_inset

 is Hermitian and tridiagonal.
 (The problem clearly intended this, since tridiagonal matrices only arise
 in the QR method if the starting point is Hermitian.) In contrast, if 
\begin_inset Formula $A$
\end_inset

 is complex tridiagonal with 
\begin_inset Formula $A^{T}=A$
\end_inset

, the stated result is not true (
\begin_inset Formula $RQ$
\end_inset

 is not in general tridiagonal, as can easily be verified using a random
 tridiagonal complex 
\begin_inset Formula $A$
\end_inset

 in Julia).
\begin_inset Newline newline
\end_inset


\begin_inset Newline newline
\end_inset

It is sufficient to show that 
\begin_inset Formula $RQ$
\end_inset

 is upper Hessenberg: since 
\begin_inset Formula $RQ=Q^{*}AQ$
\end_inset

 and 
\begin_inset Formula $A$
\end_inset

 is Hermitian, then 
\begin_inset Formula $RQ$
\end_inset

 is Hermitian and upper-Hessenberg implies tridiagonal.
 To show that 
\begin_inset Formula $RQ$
\end_inset

 is upper-Hessenberg, all we need is the fact that 
\begin_inset Formula $R$
\end_inset

 is upper-triangular and 
\begin_inset Formula $Q$
\end_inset

 is upper-Hessenberg.
\begin_inset Newline newline
\end_inset


\begin_inset Newline newline
\end_inset

Consider the 
\begin_inset Formula $(i,j)$
\end_inset

 entry of 
\begin_inset Formula $RQ$
\end_inset

, which is given by 
\begin_inset Formula $\sum_{k}r_{i,k}q_{k,j}$
\end_inset

.
 
\begin_inset Formula $r_{i,k}=0$
\end_inset

 if 
\begin_inset Formula $i>k$
\end_inset

 since 
\begin_inset Formula $R$
\end_inset

 is upper triangular, and 
\begin_inset Formula $q_{k,j}=0$
\end_inset

 if 
\begin_inset Formula $k>j+1$
\end_inset

 since 
\begin_inset Formula $Q$
\end_inset

 is upper-Hessenberg, and hence 
\begin_inset Formula $r_{i,k}q_{k,j}\neq0$
\end_inset

 only when 
\begin_inset Formula $i\leq k\leq j+1$
\end_inset

, which is only true if 
\begin_inset Formula $i\leq j+1$
\end_inset

.
 Thus the 
\begin_inset Formula $(i,j)$
\end_inset

 entry of 
\begin_inset Formula $RQ$
\end_inset

 is zero if 
\begin_inset Formula $i>j+1$
\end_inset

 and thus 
\begin_inset Formula $RQ$
\end_inset

 is upper-Hessenberg.
\end_layout

\begin_layout Enumerate
Obviously, if 
\begin_inset Formula $A$
\end_inset

 is tridiagonal (or even just upper-Hessenberg), most of each column is
 already zero—we only need to introduce one zero into each column below
 the diagonal.
 Hence, for each column 
\begin_inset Formula $k$
\end_inset

 we only need to do one 
\begin_inset Formula $2\times2$
\end_inset

 Givens rotation or 
\begin_inset Formula $2\times2$
\end_inset

 Householder reflection of the 
\begin_inset Formula $k$
\end_inset

-th and 
\begin_inset Formula $(k+1)$
\end_inset

-st rows, rotating 
\begin_inset Formula $\left(\begin{array}{c}
\cdot\\
\cdot
\end{array}\right)\to\left(\begin{array}{c}
\bullet\\
0
\end{array}\right)$
\end_inset

.
 Each 
\begin_inset Formula $2\times2$
\end_inset

 rotation/reflection requires 6 flops (multiping a 2-component vector by
 a 
\begin_inset Formula $2\times2$
\end_inset

 matrix), and we need to do it for all columns starting from the 
\begin_inset Formula $k$
\end_inset

-th.
 However, actually we only need to do it for 3 columns for each 
\begin_inset Formula $k$
\end_inset

, since from above the conversion from 
\begin_inset Formula $A$
\end_inset

 to 
\begin_inset Formula $R$
\end_inset

 only introduces one additional zero above each diagonal, so most of the
 rotations in a given row are zero.
 That is, the process looks like
\begin_inset Formula 
\[
\left(\begin{array}{cccccc}
\cdot & \cdot\\
\cdot & \cdot & \cdot\\
 & \cdot & \cdot & \cdot\\
 &  & \cdot & \cdot & \cdot\\
 &  &  & \cdot & \cdot & \cdot\\
 &  &  &  & \cdot & \cdot
\end{array}\right)\rightarrow\left(\begin{array}{cccccc}
\bullet & \bullet & \bullet\\
0 & \bullet & \bullet\\
 & \cdot & \cdot & \cdot\\
 &  & \cdot & \cdot & \cdot\\
 &  &  & \cdot & \cdot & \cdot\\
 &  &  &  & \cdot & \cdot
\end{array}\right)\rightarrow\left(\begin{array}{cccccc}
\cdot & \cdot & \cdot\\
0 & \bullet & \bullet & \bullet\\
 & 0 & \bullet & \bullet\\
 &  & \cdot & \cdot & \cdot\\
 &  &  & \cdot & \cdot & \cdot\\
 &  &  &  & \cdot & \cdot
\end{array}\right)\rightarrow\left(\begin{array}{cccccc}
\cdot & \cdot & \cdot\\
0 & \cdot & \cdot & \cdot\\
 & 0 & \bullet & \bullet & \bullet\\
 &  & 0 & \bullet & \bullet\\
 &  &  & \cdot & \cdot & \cdot\\
 &  &  &  & \cdot & \cdot
\end{array}\right),
\]

\end_inset

where 
\begin_inset Formula $\bullet$
\end_inset

 indicates the entries that change on each step.
 Notice that it gradually converts 
\begin_inset Formula $A$
\end_inset

 to 
\begin_inset Formula $R$
\end_inset

, with the two nonzero entries above each diagonal as explained above, and
 that each Givens rotation need only operate on three columns.
 Hence, only 
\begin_inset Formula $O(m)$
\end_inset

 flops are required, compared to 
\begin_inset Formula $O(m^{3})$
\end_inset

 for ordinary QR! [Getting the exact number requires more care that I won't
 bother with, since we can no longer sweep under the rug the 
\begin_inset Formula $O(m)$
\end_inset

 operations required to construct the 
\begin_inset Formula $2\times2$
\end_inset

 Givens or Householder matrix, etc.]
\end_layout

\end_deeper
\begin_layout Subsection*
Problem 2: Schur fine (10+15 points)
\end_layout

\begin_layout Enumerate
First, let us show that 
\begin_inset Formula $T$
\end_inset

 is normal: substituting 
\begin_inset Formula $A=QTQ^{*}$
\end_inset

 into 
\begin_inset Formula $AA^{*}=A^{*}A$
\end_inset

 yields 
\begin_inset Formula $QTQ^{*}QT^{*}Q^{*}=QT^{*}Q^{*}QTQ^{*}$
\end_inset

 and hence (cancelling the 
\begin_inset Formula $Q$
\end_inset

s) 
\begin_inset Formula $TT^{*}=T^{*}T$
\end_inset

.
\begin_inset Newline newline
\end_inset


\begin_inset Newline newline
\end_inset

The (1,1) entry of 
\begin_inset Formula $T^{*}T$
\end_inset

 is the squared 
\begin_inset Formula $L_{2}$
\end_inset

 norm (
\begin_inset Formula $\Vert\cdot\Vert_{2}^{2}$
\end_inset

) of the first column of 
\begin_inset Formula $T$
\end_inset

, i.e.
 
\begin_inset Formula $|t_{1,1}|^{2}$
\end_inset

 since 
\begin_inset Formula $T$
\end_inset

 is upper triangular, and the (1,1) entry of 
\begin_inset Formula $TT^{*}$
\end_inset

 is the squared 
\begin_inset Formula $L_{2}$
\end_inset

 norm of the first row of 
\begin_inset Formula $T$
\end_inset

, i.e.
 
\begin_inset Formula $\sum_{i}|t_{1,i}|^{2}$
\end_inset

.
 For these to be equal, we must obviously have 
\begin_inset Formula $t_{1,i}=0$
\end_inset

 for 
\begin_inset Formula $i>1$
\end_inset

, i.e.
 that the first row is diagonal.
\begin_inset Newline newline
\end_inset


\begin_inset Newline newline
\end_inset

We proceed by induction.
 Suppose that the first 
\begin_inset Formula $j-1$
\end_inset

 rows of 
\begin_inset Formula $T$
\end_inset

 are diagonal, and we want to prove this of row 
\begin_inset Formula $j$
\end_inset

.
 The 
\begin_inset Formula $(j,j)$
\end_inset

 entry of 
\begin_inset Formula $T^{*}T$
\end_inset

 is the squared norm of the 
\begin_inset Formula $j$
\end_inset

-th column, i.e.
 
\begin_inset Formula $\sum_{i\leq j}|t_{i,j}|^{2}$
\end_inset

, but this is just 
\begin_inset Formula $|t_{j,j}|^{2}$
\end_inset

 since 
\begin_inset Formula $t_{i,j}=0$
\end_inset

 for 
\begin_inset Formula $i<j$
\end_inset

 by induction.
 The 
\begin_inset Formula $(j,j)$
\end_inset

 entry of 
\begin_inset Formula $TT^{*}$
\end_inset

 is the squared norm of the 
\begin_inset Formula $j$
\end_inset

-th row, i.e.
 
\begin_inset Formula $\sum_{i\geq j}|t_{j,i}|^{2}$
\end_inset

.
 For this to equal 
\begin_inset Formula $|t_{j,j}|^{2}$
\end_inset

, we must have 
\begin_inset Formula $t_{j,i}=0$
\end_inset

 for 
\begin_inset Formula $i>j$
\end_inset

, and hence the 
\begin_inset Formula $j$
\end_inset

-th row is diagonal.
 Q.E.D.
 
\end_layout

\begin_layout Enumerate
The eigenvalues are the roots of 
\begin_inset Formula $\det(T-\lambda I)=\prod_{i}(t_{i,i}-\lambda)=0$
\end_inset

—since 
\begin_inset Formula $T$
\end_inset

 is upper-triangular, the roots are obviously therefore 
\begin_inset Formula $\lambda=t_{i,i}$
\end_inset

 for 
\begin_inset Formula $i=1,\ldots,m$
\end_inset

.
 To get the eigenvector for a given 
\begin_inset Formula $\lambda=t_{i,i}$
\end_inset

, it suffices to compute the eigenvector 
\begin_inset Formula $x$
\end_inset

 of 
\begin_inset Formula $T$
\end_inset

, since the corresponding eigenvector of 
\begin_inset Formula $A$
\end_inset

 is 
\begin_inset Formula $Qx$
\end_inset

.
\begin_inset Newline newline
\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Formula $x$
\end_inset

 satisfies
\begin_inset Formula 
\[
0=(T-t_{i,i}I)x=\left(\begin{array}{ccc}
T_{1} & u & B\\
 & 0 & v^{*}\\
 &  & T_{2}
\end{array}\right)\left(\begin{array}{c}
x_{1}\\
\alpha\\
x_{2}
\end{array}\right),
\]

\end_inset

where we have broken up 
\begin_inset Formula $T-t_{i,i}I$
\end_inset

 into the first 
\begin_inset Formula $i-1$
\end_inset

 rows 
\begin_inset Formula $(T_{1}\,u\,B)$
\end_inset

, the 
\begin_inset Formula $i$
\end_inset

-th row (which has a zero on the diagonal), and the last 
\begin_inset Formula $m-i$
\end_inset

 rows 
\begin_inset Formula $T_{2}$
\end_inset

; similarly, we have broken up 
\begin_inset Formula $x$
\end_inset

 into the first 
\begin_inset Formula $i-1$
\end_inset

 rows 
\begin_inset Formula $x_{1}$
\end_inset

, the 
\begin_inset Formula $i$
\end_inset

-th row 
\begin_inset Formula $\alpha$
\end_inset

, and the last 
\begin_inset Formula $m-i$
\end_inset

 rows 
\begin_inset Formula $x_{2}$
\end_inset

.
 Here, 
\begin_inset Formula $T_{1}\in\mathbb{C}^{(i-1)\times(i-1)}$
\end_inset

 and 
\begin_inset Formula $T_{2}\in\mathbb{C}^{(m-i)\times(m-i)}$
\end_inset

 are upper-triangular, and are non-singular because by assumption there
 are no repeated eigenvalues and hence no other 
\begin_inset Formula $t_{j,j}$
\end_inset

 equals 
\begin_inset Formula $t_{i,i}$
\end_inset

.
 
\begin_inset Formula $u\in\mathbb{C}^{i-1}$
\end_inset

, 
\begin_inset Formula $v\in\mathbb{C}^{m-i}$
\end_inset

, and 
\begin_inset Formula $B\in\mathbb{C}^{(i-1)\times(m-i)}$
\end_inset

 come from the upper triangle of 
\begin_inset Formula $T$
\end_inset

 and can be anything.
 Taking the last 
\begin_inset Formula $m-i$
\end_inset

 rows of the above equation, we have 
\begin_inset Formula $T_{2}x_{2}=0$
\end_inset

, and hence 
\begin_inset Formula $x_{2}=0$
\end_inset

 since 
\begin_inset Formula $T_{2}$
\end_inset

 is invertible.
 Furthermore, we can scale 
\begin_inset Formula $x$
\end_inset

 arbitrarily, so we set 
\begin_inset Formula $\alpha=1$
\end_inset

.
 The first 
\begin_inset Formula $i-1$
\end_inset

 rows then give us the equation 
\begin_inset Formula $T_{1}x_{1}+u=0$
\end_inset

, which leads to an upper-triangular system 
\begin_inset Formula $T_{1}x_{1}=-u$
\end_inset

 that we can solve for 
\begin_inset Formula $x_{1}$
\end_inset

.
\begin_inset Newline newline
\end_inset


\begin_inset Newline newline
\end_inset

Now, let us count the number of operations.
 For the 
\begin_inset Formula $i$
\end_inset

-th eigenvalue 
\begin_inset Formula $t_{i,i}$
\end_inset

, to solve for 
\begin_inset Formula $x_{1}$
\end_inset

 requires 
\begin_inset Formula $\sim(i-1)^{2}\sim i^{2}$
\end_inset

 flops to do backsubstitution on an 
\begin_inset Formula $(i-1)\times(i-1)$
\end_inset

 system 
\begin_inset Formula $T_{1}x_{1}=-u$
\end_inset

.
 Then to compute the eigenvector 
\begin_inset Formula $Qx$
\end_inset

 of 
\begin_inset Formula $A$
\end_inset

 (exploiting the 
\begin_inset Formula $m-i$
\end_inset

 zeros in 
\begin_inset Formula $x$
\end_inset

) requires 
\begin_inset Formula $\sim2mi$
\end_inset

 flops.
 Adding these up for 
\begin_inset Formula $i=1\ldots m$
\end_inset

, we obtain 
\begin_inset Formula $\sum_{i=1}^{m}i^{2}\sim m^{3}/3$
\end_inset

, and 
\begin_inset Formula $2m\sum_{i=0}^{m-1}i\sim m^{3}$
\end_inset

, and hence the overall cost is 
\begin_inset Formula $\sim\frac{4}{3}m^{3}$
\end_inset

 flops (
\begin_inset Formula $K=4/3$
\end_inset

).
\end_layout

\begin_layout Subsection*
Problem 3: Caches and backsubstitution (5+15 points)
\end_layout

\begin_layout Enumerate
For each column of 
\begin_inset Formula $X$
\end_inset

 we get a cache miss to read each entry 
\begin_inset Formula $r_{ij}$
\end_inset

 of the matrix 
\begin_inset Formula $R$
\end_inset

, an there are roughly 
\begin_inset Formula $m^{2}/2$
\end_inset

 of these.
 For large enough 
\begin_inset Formula $m$
\end_inset

, where 
\begin_inset Formula $m^{2}\gg Z$
\end_inset

, these are no-longer in-cache when the next column is processed (because
 the entire matrix 
\begin_inset Formula $R$
\end_inset

 is read in for each column before re-using any 
\begin_inset Formula $r_{ij}$
\end_inset

 for the next column) and hence incur new misses on each of the 
\begin_inset Formula $n$
\end_inset

 columns.
 Hence there are at least 
\begin_inset Formula $m^{2}n/2$
\end_inset

, or 
\begin_inset Formula $\Theta(m^{2}n)$
\end_inset

 misses.
 There are also 
\begin_inset Formula $\Theta(m^{2}n)$
\end_inset

 misses in reading 
\begin_inset Formula $X$
\end_inset

, but this only change the constant factor.
 The 
\begin_inset Formula $\Theta(mn)$
\end_inset

 misses in reading 
\begin_inset Formula $B$
\end_inset

 (each entry is used exactly once) are asymptotically negligible.
 [Since 
\begin_inset Formula $\Theta(m^{2}n)$
\end_inset

 does not depend on 
\begin_inset Formula $Z$
\end_inset

 there is no asymptotic benefit from the cache: we have a 
\emph on
pessimal
\emph default
 cache-oblivious algorithm that achieves the worst case independent of 
\begin_inset Formula $Z$
\end_inset

.]
\end_layout

\begin_layout Enumerate
We can solve this problem in a cache-oblivious or cache-aware fashion.
 I find the cache-oblivious algorithm to be more beautiful, so let's do
 that.
 We'll divide 
\begin_inset Formula $R$
\end_inset

, 
\begin_inset Formula $X$
\end_inset

, and 
\begin_inset Formula $B$
\end_inset

 into 
\begin_inset Formula $\frac{m}{2}\times\frac{m}{2}$
\end_inset

 blocks for sufficiently large 
\begin_inset Formula $m$
\end_inset

:
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
If 
\begin_inset Formula $m$
\end_inset

 is not even, then we round as needed: 
\begin_inset Formula $R_{11}$
\end_inset

 is 
\begin_inset Formula $\left\lceil \frac{m}{2}\right\rceil \times\left\lceil \frac{m}{2}\right\rceil $
\end_inset

, 
\begin_inset Formula $R_{12}$
\end_inset

 is 
\begin_inset Formula $\left\lceil \frac{m}{2}\right\rceil \times\left\lfloor \frac{m}{2}\right\rfloor $
\end_inset

, 
\begin_inset Formula $R_{21}$
\end_inset

 is 
\begin_inset Formula $\left\lfloor \frac{m}{2}\right\rfloor \times\left\lceil \frac{m}{2}\right\rceil $
\end_inset

, and 
\begin_inset Formula $R_{22}$
\end_inset

is 
\begin_inset Formula $\left\lfloor \frac{m}{2}\right\rfloor \times\left\lfloor \frac{m}{2}\right\rfloor $
\end_inset

; similarly for 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $B$
\end_inset

.
 These bookkeeping details don't change anything, though, so it is fine
 to just assume that 
\begin_inset Formula $m$
\end_inset

 is a power of 2 for simplicity.
\end_layout

\end_inset

 
\begin_inset Formula 
\[
\left(\begin{array}{cc}
R_{11} & R_{12}\\
0 & R_{22}
\end{array}\right)\left(\begin{array}{cc}
X_{11} & X_{12}\\
X_{21} & X_{22}
\end{array}\right)=\left(\begin{array}{cc}
B_{11} & B_{12}\\
B_{21} & B_{22}
\end{array}\right),
\]

\end_inset

where 
\begin_inset Formula $R_{11}$
\end_inset

 and 
\begin_inset Formula $R_{22}$
\end_inset

 are upper-triangular.
 Now we solve this, analogous to backsubstitution, from bottom to top.
 First, for 
\begin_inset Formula $k=1,2$
\end_inset

, we solve 
\begin_inset Formula 
\[
R_{22}X_{2k}=B_{2k}
\]

\end_inset

recursively for 
\begin_inset Formula $X_{2k}$
\end_inset

.
 Then, for 
\begin_inset Formula $k=1,2$
\end_inset

 we solve 
\begin_inset Formula 
\[
R_{11}X_{1k}=B_{1k}-R_{12}X_{2k}
\]

\end_inset

recursively for 
\begin_inset Formula $X_{1k}$
\end_inset

.
 We use a cache-optimal algorithm (from class) for the dense matrix multiplies
 
\begin_inset Formula $R_{12}X_{2k}$
\end_inset

, which requires 
\begin_inset Formula $f(m)\in\Theta(m^{3}/\sqrt{Z})$
\end_inset

 misses for each 
\begin_inset Formula $\frac{m}{2}\times\frac{m}{2}$
\end_inset

 multiply.
 The number 
\begin_inset Formula $Q(m)$
\end_inset

 of cache misses then satisfies the recurrence: 
\begin_inset Formula 
\[
Q(m)=4Q(m/2)+2f(m)+4m^{2},
\]

\end_inset

where the 
\begin_inset Formula $4Q(m/2)$
\end_inset

 is for the four recursive backsubsitutions and the 
\begin_inset Formula $4m^{2}$
\end_inset

 is for the two matrix subtractions 
\begin_inset Formula $B_{1k}-R_{12}X_{2k}$
\end_inset

.
 This recurrence terminates when the problem fits in cache, i.e.
 when 
\begin_inset Formula $2m^{2}+m^{2}/2\leq Z$
\end_inset

, at which point only 
\begin_inset Formula $\sim3m^{2}/2$
\end_inset

 misses are required.
 (Since we are only interested in the asymptotic 
\begin_inset Formula $\Theta$
\end_inset

 results, these little factors of 3 and 4 don't matter much, and I'll be
 dropping them soon.) Noting that 
\begin_inset Formula $f(m/2)\approx f(m)/8$
\end_inset

 , we can solve this recurrence as in class by just plugging it in a few
 times and seeing the pattern: 
\begin_inset Formula 
\begin{eqnarray*}
Q(m) & \approx & 4[4Q(m/4)+2f(m)/8+4m^{2}/4]+2f(m)+4m^{2}\\
 & = & 4^{2}Q(m/4)+2f(m)\,\left[1+\frac{1}{2}\right]+4m^{2}\,\left[1+1\right]\\
 & \approx & 4^{3}Q(m/8)+2f(m)\,\left[1+\frac{1}{2}+\frac{1}{2^{2}}\right]+4m^{2}\,\left[1+1+1\right]\\
 & \approx & \cdots\\
 & \approx & 4^{k}\Theta[(m/2^{k})^{2}]+2f(m)\,\left[1+\frac{1}{2}+\cdots+\frac{1}{2^{k-1}}\right]+4m^{2}\,\left[k\right]\\
 & \approx & \Theta(m^{2})+\Theta(m^{3}/\sqrt{Z})+\Theta(m^{2})k
\end{eqnarray*}

\end_inset

where 
\begin_inset Formula $\left[1+\frac{1}{2}+\cdots+\frac{1}{2^{k-1}}\right]\leq2$
\end_inset

 and 
\begin_inset Formula $k$
\end_inset

 is the number of times we have to divide the problem to fit in cache, i.e.
 
\begin_inset Formula $3(m/2^{k})^{2}/2\approx Z$
\end_inset

 so 
\begin_inset Formula $k$
\end_inset

 is 
\begin_inset Formula $\Theta[\log(m^{2}/Z)]$
\end_inset

.
 Hence, for large 
\begin_inset Formula $m$
\end_inset

 where the 
\begin_inset Formula $m^{3}$
\end_inset

term dominates over the 
\begin_inset Formula $m^{2}$
\end_inset

 and 
\begin_inset Formula $m^{2}\log m$
\end_inset

 terms, we obtain 
\begin_inset Formula 
\[
Q(m;Z)=\Theta(m^{3}/\sqrt{Z})
\]

\end_inset

and hence we can, indeed, achieve the same asymptotic cache complexity as
 for matrix multiplication.
\begin_inset Newline newline
\end_inset


\begin_inset Newline newline
\end_inset

We could also get the same cache complexity in a cache-aware fashion by
 blocking the problem into 
\begin_inset Formula $m/b$
\end_inset

 blocks of size 
\begin_inset Formula $b\times b$
\end_inset

, where 
\begin_inset Formula $b$
\end_inset

 is some 
\begin_inset Formula $\Theta(\sqrt{Z})$
\end_inset

 size chosen so that pairwise operations on the individual blocks fit in
 cache.
 Again, one would work on rows of blocks from bottom to top, and the algorithm
 would look much like the ordinary backsubstitution algorithm except that
 the numbers 
\begin_inset Formula $b_{ij}$
\end_inset

 etcetera are replaced by blocks.
 The number of misses is 
\begin_inset Formula $\Theta(b^{2})=\Theta(Z)$
\end_inset

 per block, and there are 
\begin_inset Formula $\Theta(\frac{m}{b}\times\frac{m}{b}\times\frac{n}{b})$
\end_inset

 block operations, hence 
\begin_inset Formula $\Theta(\frac{m^{2}n}{b^{3}}\times b^{2})=\Theta(m^{2}n/\sqrt{Z})$
\end_inset

 misses.
 This is a perfectly acceptable answer, too.
\end_layout

\end_body
\end_document