\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 4},
            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 4}

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



\begin{document}
\maketitle

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

Please answer the following questions in complete sentences in a clearly
prepared manuscript and submit the solution by the due date on
Gradescope (Due morning of Nov 6.)

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-flop-counts}{%
\subsection{Problem 1: Flop counts}\label{problem-1-flop-counts}}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Let \(\mH = \mI - 2 \frac{\vv \vv^T}{\vv^T \vv}\) be a Householder
  matrix. Starting from the vector \(\vv\) and matrix \(\mA\). Show how
  many addition operations it takes to compute \(\mH \mA\), along with
  subtraction and multiplication operations. Assume that \(\mH\) is
  \(n \times n\) and \(\mA\) is \(n \times c\). You may lose points if
  your count is not \(O(n c)\).
\item
  Consider computing \(\text{trace}(\mA^T \mB)\) where \(\mA\) and
  \(\mB\) are in compressed sparse column format and have the same
  dimensions. Suppose we have access to a fused multiply add operation.
  This is an operation that takes three inputs \(\alpha, \gamma, \beta\)
  and computes\\
  \(\theta \leftarrow \alpha*\gamma + \beta\) in a single operation.
  Explain how to use this operation when computing the trace and compute
  how much such operations you need along with any other floating point
  operations (additions, multiplications, divisions, etc. )
\end{enumerate}

\hypertarget{problem-2-inner-products-are-backwards-stable.}{%
\subsection{Problem 2: Inner-products are backwards
stable.}\label{problem-2-inner-products-are-backwards-stable.}}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Find a proof that computing \(\vx^T \vy\) is backwards stable. Explain
  this proof in enough detail for a classmate to understand it without
  having read the document. This could take up to a page to give enough
  detail.
\item
  Show that computing a matrix-vector product \(\vy = \mA \vx\) is
  backwards stable.
\end{enumerate}

\hypertarget{problem-3-accurate-summation}{%
\subsection{Problem 3: Accurate
summation}\label{problem-3-accurate-summation}}

Consider a list of \(n\) numbers. For simplicity, assume that all
numbers are positive so you don't have to write a lot of absolute
values.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Show that the following algorithm is backwards stable.

\begin{verbatim}
 function mysum(x::Vector{Float64})
   s = zero(Float64)
   for i=1:length(x)
     s += x[i]
   end
   return s
 end
\end{verbatim}

  Which requires showing that \(\text{mysum}(\vx) = \sum \hat{x}_i\)
  where \(\normof{\hat{\vx} - \vx}/\normof{\vx} \le C_n \eps\) where
  \(\eps\) is the unit-roundoff for Float64. (You may want to solve
  problem 2 first.)
\item
  Consider adding three positive numbers together \(a, b, c\). Describe
  how to compute \(s = a+b+c\) with the greatest accuracy.
\item
  Use the results of part 2 to describe a way to permute the input
  \(\vx\) to \texttt{mysum} to attain the greatest accuracy. Find an
  input vector \(\vx\) where this new ordering gives a measurable change
  in the floating point accuracy as determined by the number of correct
  digits in the mantissa. (Hint, this means you should know the true sum
  of your vector so that you can identify it's best floating point
  representation.)
\item
  Lookup the Kahan summation algorithm and implement it to sum a vector.
  Compare the accuracy with what you found in part 3.
\end{enumerate}

\hypertarget{problem-4-quadratic-equations}{%
\subsection{Problem 4: Quadratic
equations}\label{problem-4-quadratic-equations}}

Read through the stack exchange post on solving quadratic equations.
\url{https://math.stackexchange.com/questions/311382/solving-a-quadratic-equation-with-precision-when-using-floating-point-variables}

This suggests a number of approaches to compute the roots of a quadratic
equation through closed form solutions.

An alternative approach is to use an iterative algorithm to estimate
that root of an equation. In this case, we can use a simple bisection
approach, which works quite nicely for finding the root.

Your task for this problem is to implement a bisection algorithm to
return all the solutions of \(ax^2 + bx + c = 0\) when \(c \not= 0\).

\begin{verbatim}
    """ Return all the solutions to ax^2 + bx + c. It is acceptable to return
    NaN instead of a root as well. """
    function roots(a::Float32,b::Float32,c::Float32)
    end
\end{verbatim}

The input to this method is Float32 so you can compare to
higher-accuracy solutions with Float64 and to elucidate some of the
issues that arise with slightly lower-precision.

Compare the accuracy of this procedure to the methods suggested on the
stack exchange page and explain your results. Note that you may need to
look for extremal inputs. In this case, Float32 is handy because there
are only 4 billion inputs for each input value \(a, b, c\). This is
still too many to test all combinations. But there are only two choices
for the roots, which greatly reduces the space.

\hypertarget{problem-5-the-advantages-of-float64}{%
\subsection{Problem 5: The advantages of
Float64}\label{problem-5-the-advantages-of-float64}}

Consider the Chutes and Ladders problem from HW2 where we worked out the
expected length of a game based on an infinite summation. Repeat this
analysis with Float16 arithmetic and also with BigFloat analysis. (This
problem may require julia to use both Float16 and BigFloat.) Make sure
that all intermediate computations use these types. To declare a vector
of Float16 or BigFloats, use \texttt{Vector\{Float16\}} or
\texttt{Matrix\{BigFloat\}} also helpful are
\texttt{zero(Float16),\ one(Float16)}. If there are questions about
using these types, please post to Piazza. Which answer is more accurate?

\hypertarget{problem-6-condition-numbers}{%
\subsection{Problem 6: Condition
numbers}\label{problem-6-condition-numbers}}

Consider the following computations. Discuss if they are
well-conditioned or ill-conditioned. If the answer depends on the types
of input, please provide some rough guidance. (e.g. for subtraction,
it's ill-conditioned if the numbers are close by)

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  The entropy of a probability distribution is
  \(H(\vp) = -\sum_{i=1}^n p_i \log p_i\) where \(0 < p_i < 1\). Compute
  the condition number of the entropy function.
\item
  A matrix vector product \(\vy = \mA^T \vx\).
\item
  Evaluating a neural network layer \(\vy = f(\mW^T \vx)\) where the
  elements are \(y_i = f(w_i^T x)\) and \(f\) the soft-plus function
  \(\log(1+e^x)\).
\end{enumerate}

\hypertarget{problem-7-experience-with-the-svd}{%
\subsection{Problem 7: Experience with the
SVD}\label{problem-7-experience-with-the-svd}}

Produce the analytic SVDs of the following matrices. (That is, no
numerical approximations, but feel free to let Julia give you a good
guess!). It's important to think about these questions because I may
give similar questions on a midterm or final and you'll be expected to
remember these. It's also handy to think about how to construct these,
even though we haven't seen any algorithms yet. You should be able to
work them all out directly from the definition.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  \(\bmat{0 & -3 \\ 0 & 0}\)
\item
  \(\bmat{-5 & 0 \\ 2 & 0}\)
\item
  \(\bmat{1 & -2 \\ 2 & -4 \\ 0 & 0}\)
\item
  \(\bmat{2 & 0 \\ 0 & 5}\)
\end{enumerate}

\hypertarget{problem-8-backwards-stability}{%
\subsection{Problem 8: Backwards
stability}\label{problem-8-backwards-stability}}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Let \(f(x) = \sqrt{x}\). Suppose you have an algorithm where
  \(\texttt{myf}(x) = \sqrt{x+\mu}\) where \(\mu\) is the machine
  precision. Is \(\texttt{myf}(x)\) backwards stable?
\item
  Suppose that you have a fancy implementation of \(\sqrt{x}\) and you
  compute \(\texttt{mysqrt}(0.1 \mu) = -1 \cdot 10^{-16} \mu\). Is this
  a backwards stable implementation?
\end{enumerate}

\hypertarget{problem-9-condition-numbers}{%
\subsection{Problem 9: Condition
numbers}\label{problem-9-condition-numbers}}

Show that \[ \frac{1}{\kappa(\mA)} \] measures the relative distance
from \(\mA\) to the space of singular matrices. That is
\[ \frac{1}{\kappa(\mA)} = \text{ smallest } \frac{\normof{\mD}}{\normof{\mA}} \text{ such that } \mA + \mD  \text{ is singular}. \]
Everything here involves the matrix 2-norm.

\hypertarget{optional-problems}{%
\section{Optional Problems}\label{optional-problems}}

The following problem is optional, but highly recommended.

\hypertarget{problem-x---fun-with-the-svd}{%
\subsection{Problem X - Fun with the
SVD}\label{problem-x---fun-with-the-svd}}

Need to think of a fun problem here.

\end{document}
