pset3.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})}
\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 1
\use_package amssymb 1
\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
\end_layout

\begin_layout Standard
Due Friday, 15 March 2019.
\end_layout

\begin_layout Subsection*
Problem 1: QR and orthogonal bases
\end_layout

\begin_layout Enumerate
Trefethen, problem 10.4.
\end_layout

\begin_layout Enumerate
Prove that 
\begin_inset Formula $A=QR$
\end_inset

 and 
\begin_inset Formula $B=RQ$
\end_inset

 have the same eigenvalues, assuming 
\begin_inset Formula $A$
\end_inset

 is a square matrix.
 Then do a little experiment: Construct a random 
\begin_inset Formula $5\times5$
\end_inset

 real-symmetric matrix in Julia via 
\family typewriter
X=rand(5,5); A = X' + X
\family default
.
 Use 
\family typewriter
QR = qr(A)
\family default
 (do 
\family typewriter
using LinearAlgebra
\family default
 first) to compute the QR factorization of 
\begin_inset Formula $A$
\end_inset

, and then compute 
\family typewriter
B = QR.R * QR.Q
\family default
.
 Then find the QR factorization 
\begin_inset Formula $B=Q'R'$
\end_inset

, and compute 
\begin_inset Formula $R'Q'$
\end_inset

...repeat this process until the matrix converges (maybe writing a loop and/or
 a function).
 From what it converges to, suggest a procedure to compute the eigenvalues
 and eigenvectors of a real-symmetric matrix (no need to prove that it converges
 in general—we will discuss this in class).
\end_layout

\begin_layout Enumerate
Trefethen, problem 28.2,
\end_layout

\begin_layout Subsection*
Problem 2: Schur fine 
\end_layout

\begin_layout Standard
In class, we will show that any square 
\begin_inset Formula $m\times m$
\end_inset

 matrix 
\begin_inset Formula $A$
\end_inset

 can be factorized as 
\begin_inset Formula $A=QTQ^{*}$
\end_inset

 (the 
\emph on
Schur factorization
\emph default
), where 
\begin_inset Formula $Q$
\end_inset

 is unitary and 
\begin_inset Formula $T$
\end_inset

 is an upper-triangular matrix (with the same eigenvalues as 
\begin_inset Formula $A$
\end_inset

, since the two matrices are similar).
 
\end_layout

\begin_layout Enumerate
\begin_inset Formula $A$
\end_inset

 is called ``normal'' if 
\begin_inset Formula $AA^{*}=A^{*}A$
\end_inset

.
 Show that this implies 
\begin_inset Formula $TT^{*}=T^{*}T$
\end_inset

.
 From this, show that 
\begin_inset Formula $T$
\end_inset

 must be diagonal.
 Hence, any normal matrix (e.g.
 unitary or Hermitian matrices) must be unitarily diagonalizable.
 Hint: consider the diagonal entries of 
\begin_inset Formula $TT^{*}$
\end_inset

 and 
\begin_inset Formula $T^{*}T$
\end_inset

, starting from the (1,1) entries and proceeding diagonally downwards by
 induction.
\end_layout

\begin_layout Enumerate
Given the Schur factorization of an arbitary 
\begin_inset Formula $A$
\end_inset

 (not necessarily normal), describe an algorithm to find the eigenvalues
 and eigenvectors of 
\begin_inset Formula $A$
\end_inset

, assuming for simplicity that all the eigenvalues are distinct.
 The flop count should be asymptotically 
\begin_inset Formula $Km^{3}+O(m^{2})$
\end_inset

; give the constant 
\begin_inset Formula $K$
\end_inset

.
 
\end_layout

\begin_layout Subsection*
Problem 3: Caches and backsubstitution
\end_layout

\begin_layout Standard
In this problem, you will consider the impact of caches (again in the ideal-cach
e model from class) on the problem of 
\emph on
backsubstitution
\emph default
: solving 
\begin_inset Formula $Rx=b$
\end_inset

 for 
\begin_inset Formula $x$
\end_inset

, where 
\begin_inset Formula $R$
\end_inset

 is an 
\begin_inset Formula $m\times m$
\end_inset

 upper-triangular matrix (such as might be obtained by Gaussian elimination).
 The simple algorithm you probably learned in previous linear-algebra classes
 (and reviewed in the book, lecture 17) is (processing the rows from bottom
 to top): 
\end_layout

\begin_layout LyX-Code
\begin_inset Formula $x_{m}=b_{m}/r_{mm}$
\end_inset


\end_layout

\begin_layout LyX-Code

\series bold
for
\series default
 
\begin_inset Formula $j=m-1$
\end_inset

 down to 
\begin_inset Formula $1$
\end_inset


\end_layout

\begin_layout LyX-Code
   
\begin_inset Formula $x_{j}=(b_{j}-\sum_{k=j+1}^{m}r_{jk}x_{k})/r_{jj}$
\end_inset


\end_layout

\begin_layout Standard
Suppose that 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $B$
\end_inset

 are 
\begin_inset Formula $m\times n$
\end_inset

 matrices, and we want to solve 
\begin_inset Formula $RX=B$
\end_inset

 for 
\begin_inset Formula $X$
\end_inset

—this is equivalent to solving 
\begin_inset Formula $Rx=b$
\end_inset

 for 
\begin_inset Formula $n$
\end_inset

 different right-hand sides 
\begin_inset Formula $b$
\end_inset

 (the 
\begin_inset Formula $n$
\end_inset

 columns of 
\begin_inset Formula $B$
\end_inset

).
 One way to solve the 
\begin_inset Formula $RX=B$
\end_inset

 for 
\begin_inset Formula $X$
\end_inset

 is to apply the standard backsubstitution algorithm, above, to each of
 the 
\begin_inset Formula $n$
\end_inset

 columns in sequence.
\end_layout

\begin_layout Enumerate
Give the asymptotic cache complexity 
\begin_inset Formula $Q(m,n;Z)$
\end_inset

 (in asymptotic 
\begin_inset Formula $\Theta$
\end_inset

 notation, ignoring constant factors) of this algorithm for solving 
\begin_inset Formula $RX=B$
\end_inset

.
\end_layout

\begin_layout Enumerate
Suppose 
\begin_inset Formula $m=n$
\end_inset

.
 Propose an algorithm for solving 
\begin_inset Formula $RX=B$
\end_inset

 that achieves a better asymptotic cache complexity (by cache-aware/blocking
 or cache-oblivious algorithms, your choice).
 Can you gain the factor of 
\begin_inset Formula $1/\sqrt{Z}$
\end_inset

 savings that we showed is possible for square-matrix multiplication? 
\end_layout

\end_body
\end_document