for any positive integer n.   So, to compute F(n), we can compute and return the upper left number in the matrix.

Describe an algorithm to compute F(n) for arbitrary n that uses fewer than O(n) additions and multiplica- tions (don’t worry about the size of the integers), and prove that it satisfies this complexity bound. That is, prove a sublinear complexity bound in terms of n on the number of additions and multiplications this algorithm performs. Feel free to search for such an algorithm, but please generate the proof of the complexity bound yourself.

Programming Assignment

Introduction

The purpose of this portion is to get familiar with NumPy, which we will use heavily throughout the semester.

NumPy is a powerful numerical computing library for Python that provides very efficient, heavily optimized functionalities for large, multi-dimensional arrays and matrices (see np.ndarray), as well as many standard manipulations and linear algebra algorithms (see np.linalg).

It is strongly preferred over “pure Python” implementations  (eg.   with for-loops) for several reasons.   In particular, NumPy leverages several highly optimized low-level libraries (see BLAS and LAPACK) written in languages like C and Fortran to minimize all overhead involved in the operations and computations, since Python is an interpeted language whereas C and Fortran are compiled.  Additionally, NumPy arrays will always be much more memory-efficient than Python list’s.

Set up

Python  3.9  and  NumPy  are  necessary  for  the  completion  of  programming  assignments  for  this  course. Python  and  NumPy  can  be  installed  on  your  own  machine  via  the  directions  found  at this  link. For your convenience, we also have a course-wide virtual environment set up on the department machines at /course/cs1420/cs142_env.  The environment can be activated from your own folder by running the fol- lowing command: source  /course/cs1420/cs142_env/bin/activate.

Stencil Code

You can find the stencil code for this assignment on GitHub classroom at this link. For more details, please see the download/submission guide.

We have provided the following stencil code:

. warmup.py contains 8 functions for you to implement:  part_a through part_g.  You will implement these functions in the Warm Up: Introduction to NumPy portion of this programming assignment.

.  eigenvalues.py contains two functions for you to implement:  qr and  compute_eigenvalues.  You will implement these functions in the Computing Eigenvalues via QR Decomposition portion of this programming assignment.

You should only need to modify code marked with #TODO in warmup.py and eigenvalues.py to complete this assignment.  If you make any other edits to the provided stencil code, please make sure to revert them or leave them commented out in the final handin for autograder compatibility.

To test your implementations in eigenvalues.py, you can run python  tests.py in a terminal. Make sure you activate the virtual environment first when working over ssh or on a department machine:

source  /course/cs1420/cs142 env/bin/activate

Warm Up: Introduction to NumPy

If you have never used NumPy before, please read through the  “Getting started” portion of the NumPy user guide before attempting this exercise.  For each of the following parts, please implement its associated function in warmup.py.

NumPy is often abbreviated as “np” (i.e., import  numpy  as  np). You may find the following functions par- ticularly helpful: np.arange, np.zeros, np.ones, np.eye, np.sum, np.hstack, np.vstack, np.transpose, np.matmul, np.inner, np.where, and np.dot.

You may not use np.array() (eg. to create the desired Numpy ndarray’s from Python list’s).

a.  Create a 1-dimensional matrix containing the values 2 through 6 inclusive.  Return the new matrix in function part_a.

b.  Create a 4 × 4 matrix where all entries are 1. Return the new matrix in function part_b. c.  Create a 6 × 6 identity matrix. Return the new matrix in function part_c.

d.  Given matrix A, compute the sum of the values of its columns.  Return the answer in function part_d. e.  Given matrices A and B, compute C, where C = ATB.  Return the matrix C in function part_e.

f.  Using either np.vstack or np.hstack, create a 4 × 2 matrix where all the values in the first column are zeros and all the values in the second column are ones. Return the new matrix in function part_f.

g.  Given a matrix of floats A, create a new matrix of the same shape where all values greater than 3 .0 are set to 1 and all other values are set to 0. Return the new matrix in function part_g.

Computing Eigenvalues via QR Decomposition

Your task is to finish implementing both the Householder QR decomposition algorithm (lines 2 through 9 in Algorithm 1) and the QR eigenvalue computation algorithm (Algorithm 2). In the stencil, these are contained respectively in qr and compute_eigenvalues in the eigenvalues.py.  The lines in Algorithm 1 which you must implement are colored violet. Please note that this problem is intended to serve as a NumPy exercise; therefore, understanding the theory behind the  algorithms  is not a requirement.

QR Decomposition

Let A e Rn ×n.  The  QR  decomposition  of A is  a matrix product QR, where Q e Rn ×n  is an orthogonal matrix (QT  = Q −1) and R e Rn ×n  is upper triangular.  This factorization is called the QR decomposition.

Below, we present the Householder QR decomposition algorithm.  Again,  you do not need to understand the mathematics  behind this  algorithm.  The purpose of implementing this algorithm is to gain familiarity with transforming mathematical and algorithmic notation into respective NumPy operations.  This includes learn- ing how to multiply matrices, compute norms, and manipulate NumPy arrays using NumPy’s functionalities instead of Python for-loops.

Some notes regarding the notation presented in Algorithm 1:

1. We let yi  denote the i-thentry of some vector y, andya:b  will denote the subvector y with first element ya  and last element yb −1.  Note that the vector ya:b  should contain b — a entries.

2.  Similarly, xi,j  will denote the entry in the i-th row and j-th column of some matrix X .  Let Xa:b,c:d denote the submatrix of X with upper left corner xa,b  and lower right corner xc −1,d−1 . Note that Xa:b,c:d  should have dimension  (c — a) X (d — b).  You can find some examples of this notation on our NumPy guide.

3.  Also, Xa:b,j  will denote the j-th column of submatrix Xa:b,0:n.  Note that Xa:b,j  is a vector with b — a entries.

4.  Let In ×n  denote the n X n identity matrix. Let 0n ×n  denote an n X n matrix where all entries are 0. 5.  I · I2  denotes the L2 norm.  sign(x) evaluates to 1 if x ≥ 0 and 0 otherwise.

Some notes regarding the implementation of Algorithm 1:

1.  The sign( ·) function has been implemented for you in the stencil code. Do not use np.sign.

2.  The NumPy equivalent for Xa:b,c:d  is X[a:b,  c:d] (see Python’s slice notation).  Similarly, the NumPy

equivalent for Xa:b,c  is X[a:b,  c]. If you wish to index the entire j-th column of X, use X[:,  j].

3.  The vector Vk:n,k  in line 9 should be treated strictly as a column vector. Note that calling V[k:n,  k] will return a  1-dimensional NumPy array. To transform  Vk:n,k into a column vector, you can call V[k:n,  k].reshape(-1,  1). Generally, if x satisfies x.shape  =  (a,), then you can reshape x into an a X 1 NumPy array by calling x.reshape(-1,  1).shape  =  (a,  1).

4. You should not use V[k:n,  k]  /=  np.linalg.norm(V[k:n,  k]). You should instead use V[k:n,  k]  =  V[k:n,  k]  /  np.linalg.norm(V[k:n,  k]).

Computing Eigenvalues with QR Decomposition

We can leverage the QR decomposition to approximately compute the eigenvalues for a matrix A e Rn ×n. First, we let Atemp  = A.  Then, we iteratively update Atemp  a total of m times, where the k-th iteration constitutes the following updates:

QR = Atemp ,

Atemp  = RQ.

Under certain conditions, Atemp  will converge to an upper triangular matrix.  Then, the eigenvalues of A are the diagonal elements of Atemp. The complete algorithm is presented below.