ECON 570 Problem Set 1
ECON 570 Problem Set 1
1 Cholesky Factorization
A. Recall that if A ∈ R
n×n
is symmetric and positive definite, then it can be factored as
A = LL′
, (1)
where L is lower triangular and nonsingular.
Assume that A is 2 × 2. Write down the system of equations implied by (1) and
calculate the number of flops required to perform the Cholesky factorization in this
case.
B. Extend the previous result and show that the complexity of the Cholesky factorization
for the general case of a n × n matrix is O(n
3
).
2 Computational Complexity
A. Write custom functions for
1. Calculating the inner product of two vectors.
2. Calcuatling the product of two matrices.
B. Generate random m × n matrix X and n × p matrix Y , for m = 50, n = 100, p = 200.
Compute
1. The amount of time it takes to multiply X and Y using the custom code you
wrote.
2. The amount of time it takes to multiply X and Y using built-in NumPy methods.
C. Now increase m, n, p each by a factor of 10.
1. How long do you expect it would take to multiply X and Y using your custom
code? How long does it actually take?
2. How long do you expect it would take to multiply X and Y using built-in NumPy
methods? How long does it actually take?
D. Increase m, n, p each by a factor of 10 again, and repeat the above but using NumPy’s
built-in methods only. How long does it take to multiply X and Y ? Did it increase by
the same factor as it did before when all the dimensions were increased by a factor of
10? Why or why not?
E. Generate a n × p matrix and a n-vector y.
1. Set n = 5000, p = 200. How long does it take to regress y on X?
2. Set n = 50000, p = 200. How long do you expect the same regression would take?
How long does it actually take?
3. Set n = 5000, p = 2000. How long do you expect the same regression would take?
How long does it actually take?
DETAILED ASSIGNMENT
