Module 12 Problems
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
