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.

"""

202 μs

using LinearAlgebra

339 μs

using BenchmarkTools

28.6 ms

1: Placing Parens

Suppose $A, B \in R^{n \times n}$ and $d, u, v, w \in 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

373 μ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

453 ms

"Estimated complexity: O(n^2.876225695250725)"

begin

function time_hw1p1a(n)

A = rand(n, n)

d = rand(n)

hw1p1a(A, d)

@belapsed hw1p1a($A, $d) seconds=0.5

end

"Estimated complexity: O(n^$(log2(time_hw1p1a(1000)/time_hw1p1a(500))))"

end

3.0 s

hw1p1b (generic function with 1 method)

# Rewrite to run in O(n)

function hw1p1b(d, u, v, w)

A = diagm(d) + u*v'

A*w

end

416 μs

"P1b code passes correctness test"

begin

function test_hw1p1b()

d = [9.0; 11.0]

u = [8.0; 12.0]

v = [7.0; 11.0]

w = [4.0; 5.0]

hw1p1b(d, u, v, w) == [700.0; 1051.0]

end

if test_hw1p1b()

"P1b code passes correctness test"

else

"P1b code fails correctness test"

end

154 ms

"Estimated complexity: O(n^2.2188158938444063)"

begin

function time_hw1p1b(n)

d = rand(n)

u = rand(n)

v = rand(n)

w = rand(n)

hw1p1b(d, u, v, w)

@belapsed hw1p1b($d, $u, $v, $w) seconds=0.5

end

"Estimated complexity: O(n^$(log2(time_hw1p1b(4000)/time_hw1p1b(2000))))"

end

3.3 s

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

322 μ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

12.8 ms

"Estimated complexity: O(n^3.006758543014128)"

begin

function time_hw1p1c(n)

A = rand(n, n)

B = rand(n, n)

d = rand(n)

w = rand(n)

hw1p1c(A, B, d, w)

@belapsed hw1p1c($A, $B, $d, $w) seconds=0.5

end

"Estimated complexity: O(n^$(log2(time_hw1p1c(4000)/time_hw1p1c(2000))))"

end

17.1 s

2: Making matrices

In terms of the power basis, write

The matrix $A \in R^{3 \times 3}$ corresponding to the inner product between two quadratics; that is, if $p (x) = c_{0} + c_{1} x + c_{2} x^{2}$ and $q (x) = d_{0} + d_{1} x + d_{2} x^{2}$ , then $\int_{- 1}^{1} p (x) q (x) d x = d^{T} A c$ .
The matrix $B \in R^{2 \times 3}$ corresponding to the linear map from quadratics to linears associated with differentiation.

The following testers will sanity check your answer, but you should also (briefly) describe how you got the right matrix.

md"""

#### 2: Making matrices

In terms of the power basis, write

1. The matrix $A \in \mathbb{R}^{3 \times 3}$ corresponding to the inner product between two quadratics; that is, if $p(x) = c_0 + c_1 x + c_2 x^2$ and $q(x) = d_0 + d_1 x + d_2 x^2$, then $\int_{-1}^1 p(x) q(x) \, dx = d^T A c$.

1. The matrix $B \in \mathbb{R}^{2 \times 3}$ corresponding to the linear map from quadratics to linears associated with differentiation.

The following testers will sanity check your answer, but you should also (briefly) describe how you got the right matrix.

"""

1.4 ms

A_quadratic

3×3 Matrix{Float64}:
 1.0  0.0  0.0
 0.0  1.0  0.0
 0.0  0.0  1.0

A_quadratic = [1.0 0.0 0.0;

0.0 1.0 0.0;

0.0 0.0 1.0]

12.9 ms

"A fails basic check"

begin

# This is a three-point Gauss quadrature rule to approximate

# integral of f from -1 to 1. It is exact for polynomials up to degree 5

function gauss3(f)

ξ = sqrt(3/5)

(5*f(-ξ) + 8*f(0.0) + 5*f(ξ))/9

end

function test_quadratic_form(A)

c = rand(3)

d = rand(3)

p(x) = (c[3]*x + c[2])*x + c[1]

q(x) = (d[3]*x + d[2])*x + d[1]

ξ = sqrt(3/5)

ϕ_A = c'*A*d

ϕ_int = gauss3((x) -> p(x)*q(x))

(ϕ_int-ϕ_A)/ϕ_A

end

if abs(test_quadratic_form(A_quadratic)) < 1e-8

"A passes basic check"

else

"A fails basic check"

end

24.8 ms

B_deriv

2×3 Matrix{Float64}:
 0.0  0.0  0.0
 0.0  0.0  0.0

B_deriv = [0.0 0.0 0.0;

0.0 0.0 0.0]

12.0 μs

"B fails basic check"

begin

function test_B_deriv(B)

c = [7.0; 11.0; 3.0] # p(x) = 3x^2 + 11x + 7

d = [11.0; 6.0] # p'(x) = 6x + 11

B*c == d

end

if test_B_deriv(B_deriv)

"B passes basic check"

else

"B fails basic check"

end

8.3 ms

3: Crafty cosines

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

$a = ∥ u ∥, b = ∥ v ∥, c = ∥ u - v ∥$

Express $⟨ u, v ⟩$ 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.

"""

212 μs

compute_dot (generic function with 1 method)

function compute_dot(a, b, c)

return 0.0

end

266 μ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

83.8 ms