\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
    \makeatletter % undo the wrong changes made by mathspec
    \let\RequirePackage\original@RequirePackage
    \let\usepackage\RequirePackage
    \makeatother
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage{hyperref}
\hypersetup{unicode=true,
            pdftitle={Homework 3},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi

\title{Homework 3}

\input{preamble.tex}
\title{Homework}



\begin{document}
\maketitle

\hypertarget{homework-3}{%
\section{Homework 3}\label{homework-3}}

Please answer the following questions in complete sentences in a clearly
prepared manuscript and submit the solution by the due date on
Gradescope (before early am on October 2nd, 2023.)

Remember that this is a graduate class. There may be elements of the
problem statements that require you to fill in appropriate assumptions.
You are also responsible for determining what evidence to include. An
answer alone is rarely sufficient, but neither is an overly verbose
description required. Use your judgement to focus your discussion on the
most interesting pieces. The answer to ``should I include `something' in
my solution?'' will almost always be: Yes, if you think it helps support
your answer.

\hypertarget{problem-0-homework-checklist}{%
\subsection{Problem 0: Homework
checklist}\label{problem-0-homework-checklist}}

\begin{itemize}
\item
  Please identify anyone, whether or not they are in the class, with
  whom you discussed your homework. This problem is worth 1 point, but
  on a multiplicative scale.
\item
  Make sure you have included your source-code and prepared your
  solution according to the most recent Piazza note on homework
  submissions.
\end{itemize}

\hypertarget{problem-1-viral-spreading-and-the-power-method.}{%
\subsection{Problem 1: Viral spreading and the power
method.}\label{problem-1-viral-spreading-and-the-power-method.}}

As mentioned in the class video and briefly explored on the last
homework, there is a neat relationship between viral spreading and
matrix eigenvalues. We'll explore that here a bit more.

The two problems we'll use are the 10-node problem

\begin{verbatim}
    Random.seed!(10)
    A,xy = spatial_network(10, 2)
    
\end{verbatim}

and the 1000-node problem

\begin{verbatim}
    Random.seed!(10)
    A,xy = spatial_network(1000, 2)     
\end{verbatim}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Consider using the \texttt{approx\_evolve\_steps} function from
  Homework 1 for 10 steps. If we use the last step as an approximation
  of an eigenvector of \(\rho \mA\), what is the associated eigenvalue?
  (Hint: This is often called the Rayleigh quotient.) Here, we'll use
  \(\rho = 0.2\) or \texttt{p\ =\ 0.2}. Also
  \texttt{x0\ =\ zeros(size(A,1));\ x0{[}1{]}\ =\ 1} for the 10-node
  problem and \texttt{x0\ =\ zeros(size(A,1));\ x0{[}end{]}\ =\ 1} for
  the 1000-node problem. To check your approach with Julia 1.8, for 10
  nodes with 10 steps, I get \texttt{1.1671278134538403}. (This varies
  with the random number generator you use, so I need to double check on
  Julia 1.9, we will do that quickly and update as appropriate.) What
  happens with \(50\) and \(100\) steps? \textbf{For fun, I also tried
  this with the \texttt{evolve\_steps} function too but you don't have
  to do that.}
\item
  Use the power method to estimate the largest eigenvalues for
  \(\rho \mA\) for both the \(10\) and \(1000\) node problems. How does
  it compare with the estimates from the previous step?
\item
  Use the power method to determine how much social distancing is
  required to get the largest eigenvalue of the matrix \(\rho \mA\)
  below \(1\) for the \(1000\)-node graph. (The eigenvalue of \(1\) is
  important because that's where you would expect an epidemic to occur.)
  Does it make sense that an epidemic wouldn't occur if you draw a
  picture of the graph with appropriate social distancing? How does this
  compare with reducing \(\rho\) to achieve the same effect?
\item
  Vaccination behavior and epidemic thresholds. If we have a vaccine
  that is 90\% effective and we have vaccinated 80\% of the population,
  then we can simulate the impact of that by simply removing 72\% of the
  nodes from the graph. Let's assume vaccination is done at random.
  (This is actually a very bad assumption in the United States right
  now, but that's a topic for a different class.) For the 1000 node
  graph, do you need more or less social distancing to get the largest
  eigenvalue of \(\rho \mA\) below one? Please run at least 25 trials of
  which nodes are randomly vaccinated. And report the mean and standard
  deviations of your estimates.
\end{enumerate}

\hypertarget{problem-2-implementing-backsolve}{%
\subsection{Problem 2: Implementing
Backsolve}\label{problem-2-implementing-backsolve}}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Implement backsolve and forward solve as functions in Julia. Show and
  document your code.
\item
  Construct a random upper-triangular linear system via:

\begin{verbatim}
A = triu(randn(n,n));
b = randn(n);
\end{verbatim}

  Compare the performance of your backsolve to Julia's backslash method
  to solve a linear system.
\item
  Use your backsolve and forward solve code, along with Julia's
  \texttt{lu} factorization in order to implement your own linear
  solver. Present a paragraph or two (and a figure or two) comparing
  it's speed and accuracy to using the \texttt{\textbackslash{}} solver.
\end{enumerate}

\hypertarget{problem-3-the-schur-complement}{%
\subsection{Problem 3: The Schur
Complement}\label{problem-3-the-schur-complement}}

Suppose we wish to solve \[ \mM \vx = \vb \] and further suppose that
you \emph{KNOW} some of the values of \(\vx\).

Let us permute and partition \(\mM\) to be a block system:
\[ \mM  \vx = \bmat{ \mA & \mB \\ \mC & \mD } \bmat{\vx_1 \\ \vx_2} = \bmat{ \vb_1 \\ \vb_2 } \]
where \(\vx_1\) is what you know.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Show how to solve for \(\vx_2\) given \(\vx_1\). Under what conditions
  is this possible?
\item
  Now, suppose that you have a very kind, but very confused dog that
  happened to \emph{eat} your flash memory stick holding the piece of
  \(\vx_1\) that you knew. However, you had saved your computed
  \(\vx_2\) on your Purdue account, and so you have a backup. (This
  means you can assume that computing \(\vx_2\) from \(\vx_1\) is
  \emph{possible} for this problem if you determined it wasn't always
  possible above.) Can you get \(\vx_1\) back?
\item
  Combine these two parts to derive a single linear system to compute
  \(\vx_1\) without computing \(\vx_2\). The system you'll derive is
  called the \emph{Schur complement}.
\end{enumerate}

\hypertarget{problem-4-quicker-questions}{%
\subsection{Problem 4: Quicker
questions}\label{problem-4-quicker-questions}}

These questions are not necessarily very hard, but ask you to relate
mathematical details in a computational way.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Let \(\mP\), \(\mL\), \(\mU\) be the output of an LU with partial
  pivoting. Write a software test to check if this is the correct
  output.
\item
  Recall that there is a quadratic function
  \(f(x) = 1/2 \vx^T \mA \vx - \vx^T \vb\) associated with a symmetric
  positive definite linear system \(\mA\) and vector \(\vb\) such that
  the minimizer of \(f\) is the solution to \(\mA \vx = \vb\). Draw a
  picture of the original quadratic and also draw a picture of the
  quadratic after you eliminate the variable \(x_1\) (i.e.~you do one
  variable elimination step as we did in class.) Your answer should have
  two quadratics. Do this for the system \(\mA = \bmat{2 & 1 \\ 1 & 2}\)
  and \(\vb = \bmat{5.5 \\ 0.5}\).
\end{enumerate}

\end{document}
