## Description

Note 1: For the problems below, you are not allowed to use any of

the NumPy/SciPy linear solvers.

You may use any other functions in the NumPy/SciPy modules.

Note 2: If you choose not to use NumPy arrays, you should assume that

Python matrices are given as a list of lists of numbers.

Example:

(123456−314)

is represented as

[ [1, 2 , 3],

[4, 5, 6],

[ -3, 1, 4] ]

1. [20 pts] Give an algorithm for solving the lower triangular system Lx = b.

What is the complexity of your algorithm?

2. [20 pts] Give an algorithm for solving the upper triangular system Ux = b.

What is the complexity of your algorithm?

3. [20 pts] Solve the system given below, using your algorithm from prob 1.

Be sure to show each step of the solution.

(100410−651)(x1x2x3)=(314−7)

4. [20 pts] Write a Python Program to do LU factorization of an arbitrary

matrix

Use your program to find the LU decomposition of the matrix below:

(4−568−6712−712)

Be sure to show each row operation in the LU decomposition.

5. [20 pts] Write a Koratsuba-based algorithm for 4-decimal digit multiplies

that uses 2-decimal digit multiplies and

2-decimal digit additions/subtractions as a base.

Give a trace of your algorithm (that is, show partial results) for 5822 x 4104