Frontmatter

If you are publishing this notebook on the web, you can set the parameters below to provide HTML metadata. This is useful for search engines and social media.

HW 1 for CS 4220

You may (and probably should) talk about problems with the each other, with the TAs, and with me, providing attribution for any good ideas you might get. Your final write-up should be your own.
md"""
# HW 1 for CS 4220

You may (and probably should) talk about problems with the each other, with the TAs, and with me, providing attribution for any good ideas you might get. Your final write-up should be your own.
"""
166 μs
using LinearAlgebra
264 μs
using BenchmarkTools
64.3 ms

1: Placing Parens

Suppose $A, B \in \mathbb{R}^{n \times n}$ and $d, u, v, w \in \mathbb{R}^n$. Rewrite each of the following Julia functions to compute the same result but with the indicated asymptotic complexity.
md"""
#### 1: Placing Parens

Suppose $A, B \in \mathbb{R}^{n \times n}$ and $d, u, v, w \in \mathbb{R}^n$. Rewrite each of the following Julia functions to compute the same result but with the indicated asymptotic complexity.
"""
182 μs
hw1p1a (generic function with 1 method)
# Rewrite to run in O(n)
function hw1p1a(A, d)
D = diagm(d)
tr(D*A*D)
end
379 μs
"P1a code passes correctness test"
begin
function test_hw1p1a()
A = [1.0 2.0; 3.0 4.0]
d = [9.0; 11.0]
hw1p1a(A, d) == 565.0
end
if test_hw1p1a()
"P1a code passes correctness test"
else
"P1a code fails correctness test"
end
end
378 ms
hw1p1b (generic function with 1 method)
# Rewrite to run in O(n^2)
function hw1p1b(A, B, u, v)
C = u*v'
A*C*B
end
340 μs
"P1b code passes correctness test"
begin
function test_hw1p1b()
A = [9.0 15.0; 11.0 16.0]
B = [8.0 17.0; 12.0 18.0]
u = [7.0; 11.0]
v = [4.0; 5.0]
hw1p1b(A, B, u, v) == [20976.0 36024.0; 23276.0 39974.0]
end
if test_hw1p1b()
"P1b code passes correctness test"
else
"P1b code fails correctness test"
end
end
58.2 ms
hw1p1c (generic function with 1 method)
# Rewrite to run in O(n^2)
function hw1p1c(A, B, d, w)
(diagm(d) + A*B)*w
end
324 μs
"P1c code passes correctness test"
begin
function test_hw1p1c()
A = [1.0 2.0; 3.0 4.0]
B = [5.0 6.0; 7.0 8.0]
d = [8.0; 12.0]
w = [4.0; 5.0]
hw1p1c(A, B, d, w) == [218.0, 482.0]
end
if test_hw1p1c()
"P1c code passes correctness test"
else
"P1c code fails correctness test"
end
end
90.0 ms

2: Making matrices

Recall the first kind Chebyshev polynomials, which satisfy

$$\begin{align*} T_0(x) &= 1 \\ T_1(x) &= x \\ T_{n+1}(x) &= 2x T_n(x) - T_{n-1}(x), \quad n \geq 1. \end{align*}$$

  1. Write the matrix $A \in \mathbb{R}^{5 \times 5}$ representing the linear map from the coefficients of $p \in \mathcal{P}_4$ in the Chebyshev basis to the coefficients of the same $p \in \mathcal{P}_4$ in the power basis.

  2. Write the matrix $B \in \mathbb{R}^{5 \times 4}$ representing the linear map $p(x) \mapsto x p(x)$ from $\mathcal{P}_3$ to $\mathcal{P}_4$ with respect to the Chebyshev basis for both spaces.

Hint for 2: Observe that the Chebyshev recurrence can also be written as

$$x T_n(x) = \frac{1}{2} T_{n-1}(x) + \frac{1}{2} T_{n+1}(x)$$
md"""
#### 2: Making matrices

Recall the [first kind Chebyshev polynomials](https://en.wikipedia.org/wiki/Chebyshev_polynomials), which satisfy

$$\begin{align*}
T_0(x) &= 1 \\
T_1(x) &= x \\
T_{n+1}(x) &= 2x T_n(x) - T_{n-1}(x), \quad n \geq 1.
\end{align*}$$

1. Write the matrix $A \in \mathbb{R}^{5 \times 5}$ representing the linear map from the coefficients of $p \in \mathcal{P}_4$ in the Chebyshev basis to the coefficients of the same $p \in \mathcal{P}_4$ in the power basis.

2. Write the matrix $B \in \mathbb{R}^{5 \times 4}$ representing the linear map $p(x) \mapsto x p(x)$ from $\mathcal{P}_3$ to $\mathcal{P}_4$ with respect to the Chebyshev basis for both spaces.

*Hint for 2*: Observe that the Chebyshev recurrence can also be written as

$$x T_n(x) = \frac{1}{2} T_{n-1}(x) + \frac{1}{2} T_{n+1}(x)$$
2.7 ms

3: Crafty cosines

Suppose $\| \cdot \|$ is a inner product norm in some real vector space and you are given

$$a = \|u\|, \quad b = \|v\|, \quad c = \|u-v\|$$

Express $\langle u, v \rangle$ in terms of $a$, $b$, and $c$. Be sure to explain where your formula comes from.
md"""
#### 3: Crafty cosines

Suppose $\| \cdot \|$ is a inner product norm in some real vector space and you are given

$$a = \|u\|, \quad b = \|v\|, \quad c = \|u-v\|$$

Express $\langle u, v \rangle$ in terms of $a$, $b$, and $c$. Be sure to explain where your formula comes from.
"""
224 μs
compute_dot (generic function with 1 method)
function compute_dot(a, b, c)
return 0.0
end
247 μs
"Fails sanity check"
begin
function test_dot_abc()
u = rand(10)
v = rand(10)
a = norm(u)
b = norm(v)
c = norm(u-v)
d1 = compute_dot(a, b, c)
d2 = v'*u
(d2-d1)/d2
end
if abs(test_dot_abc()) < 1e-8
"Passes sanity check"
else
"Fails sanity check"
end
end
185 ms