\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{\yk}{y^{(k)}}
\newcommand{\zk}{z^{(k)}}
\newcommand{\xk}{x^{(k)}}
\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 4}\\
Instructor: Anil Damle\\
Due: November 6, 2024\\

\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
\noindent

\subsection*{Question 1:}
We are going to consider some details about how Krylov methods behave in specific situations.
\begin{enumerate}[label=(\alph*)]
\item Given a symmetric positive definite matrix $A$ and vector $b,$ prove that if the Lanczos process breaks down at some point (\emph{i.e.} $\beta_k = 0$ using the notation from class and Trefethen and Bau) then the subspace $\mathcal{K}_k(A,b)$ contains a solution to the linear system $Ax=b.$ In principle we might be worried that if $\beta_k = 0$ things have gone horribly wrong since we cannot construct the next vector in our orthonormal basis. However, this result shows that in this context everything has actually gone remarkably well.
\item Still assuming that $A$ is symmetric positive definite, consider using CG to solve the linear system $Ax=b$ and let $y$ satisfy $T_ky = \|b\|e_1$ (i.e., $y$ is the solution to the CG subproblem that defines our iterate in $\mathcal{K}_k(A,b)$). Prove that the CG iterate $x^{(k)} = V_ky$ satisfies 
\[
\|b-Ax^{(k)}\|_2 = \beta_k(e_k^Ty).
\]
In addition, prove that $b-Ax^{(k)} \perp \mathcal{K}_k(A,b)$ (i.e., that the residual is orthogonal to the current Krylov subspace).
\end{enumerate}
\newpage
\subsection*{Question 2:}
Here, we will consider the applicability of Krylov methods to solving a set of closely related linear systems. Specifically, we are given a real symmetric $n\times n$ matrix $A$ and a set of $M$ real numbers $\left\{\sigma_i\right\}_{i=1}^{M}$ (you may assume none of the $\sigma_i$ are eigenvalues of $A$), and we want to solve the set of $M$ linear systems
\[
\left(A-\sigma_i I\right)x_i = b
\]
for $\left\{x_i\right\}_{i=1}^M$. You may assume we do not have any reason to use an initial guess besides $\vec{0}$ for all of the given linear systems.\\

\noindent
Devise a Krylov subspace based iterative method to ``simultaneously'' solve this collection of linear systems in the sense that you construct $M$ sequences of iterates each with the property that $x_i^{(k)}\rightarrow \left(A-\sigma_i\right)^{-1}b$ as $k\rightarrow \infty.$ In addition, your algorithm must satisfy the following properties:
\begin{itemize}
\item Use no more than one matrix vector product with $A$ at each iteration. A single iteration constitutes computing $x_i^{(k)}$ for $i = 1,\ldots,M.$ 
\item Converge (in exact arithmetic) for any $\sigma_i$ that is not an eigenvalue of $A$ and converge in at most $\ell$ iterations for every $i$ if $A$ has $\ell$ distinct eigenvalues.
\item Have a storage cost that is na\"ively $\cO(Mnk)$ and computational complexity per iteration that is na\"ively $T_{mult}(A) + \cO(Mnk) + \cO(Mk^3),$ but can be improved to $\cO(Mn)+\cO(Mk)$ and $T_{mult}(A) + \cO(Mn)$ respectively. You do not have to work out all the details on the improvement, but you do have to make a convincing argument that such an improvement is possible.
\end{itemize}

Given this problem and set of requirements address the following:
\begin{enumerate}[label=(\alph*)]
\item State your algorithm for addressing the above problem and prove why it satisfies the desired criteria. Be sure to both clearly articulate your final algorithm and provide the desired proofs.
\item Let's say we are given a set of non-singular real symmetric preconditioners $M_i^{-1}\approx \left(A-\sigma_i\right)^{-1}$ and their Cholesky factorizations $M_i^{-1} = L_iL_i^T.$ Do you think that these preconditioners can be incorporated into your algorithm without adversely impacting its computational benefits (i.e., could you devise an algorithm that is faster than solving the $M$ problems independently)? Why or why not?
\end{enumerate}
\end{document}