\documentclass[11pt,onecolumn]{article}
\usepackage{amssymb, amsmath, amsthm,graphicx, paralist,algpseudocode,algorithm,cancel,url,color}
\usepackage{sectsty}
\usepackage{fancyvrb}
\usepackage{mathrsfs}
\usepackage{multirow}
\usepackage{hhline}
\usepackage{booktabs}
\usepackage[table]{xcolor}
\usepackage{tikz}
% \usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usepackage{listings}
\usepackage{enumitem}
\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\tx}{\tilde{x}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Rn}{\R^{n\times n}}
\newcommand{\Rmn}{\R^{m\times n}}
\newcommand{\Cn}{\C^{n\times n}}
\newcommand{\Cmn}{\C^{m\times n}}
\newcommand{\cO}{\mathcal{O}}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\trace}{trace}
\DeclareMathOperator{\diag}{diag}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 6210: Homework 3}\\
Instructor: Anil Damle\\
Due: March 8, 2022\\
\subsection*{Policies}
You may discuss the homework problems freely with other students, but please
refrain from looking at their code or writeups (or sharing your own).
Ultimately, you must implement your own code and write up your own solution to
be turned in. Your solution, including plots and requested output from your code
should be typeset and submitted via the Gradescope as a pdf file. Additionally, please
submit any code written for the assignment. This can be done
by either including it in your solution as an appendix, or uploading it as a zip
file to the separate Gradescope assignment.\\
\hrule
\vspace{1cm}
\noindent
\subsection*{Question 1:}
For square non-singular $A$ implement the computation of a QR factorization via Householder triangularization. This now gives a means for solving linear systems $Ax=b.$ For the following you may use your existing code for computing LU decompositions with partial pivoting. (If you did not complete the previous homework or did not end up with working code you can use a built-in implementation.)
\begin{enumerate}[label=(\alph*)]
\item Compare and contrast the runtimes of your QR factorization and your LU factorization with partial pivoting. As part of this, show your implementation of Householder QR is $\cO(n^3).$
\item Build a set of problems that are increasingly ill-conditioned. (These should be general dense matrices and not something explicitly structured, i.e., do not use diagonal matrices.) Using this set of matrices explore the relationship between the condition number of the problem and your ability to accurately solve $Ax=b$ using your QR factorization routine. How does this compare to what you observe when using LU with partial pivoting? What about for some of the ``worst case'' problems we considered on the last homework?
\end{enumerate}
\subsection*{Question 2 (ungraded but fun, and maybe a good conceptual warm up for later in the semester):}
Say we would like to compute a QR factorization of $A^k$ for some real, square $A$ and (potentially large) integer $k.$
\begin{enumerate}[label=(\alph*)]
\item Even if it is feasible to simply construct $A^k,$ is it be good idea numerically to compute its QR factorization directly? Justify your response.
\item Develop a scheme to compute a QR factorization of $A^k$ via a sequence of $k$ QR factorizations of matrices whose condition number is never larger than that of $A$ itself. As long as you adhere to this constraint, for the purposes of this problem you may assume that computing matrix matrix products with the resulting $Q$ and/or $R$ matrices is fine numerically.
\end{enumerate}
\end{document}