Problem Set 4: \(A=LU\) and Computation#
Work through these problems step-by-step. For numerical computations, show all arithmetic clearly. For complexity analysis, provide both exact operation counts and asymptotic notation.
Key Learning Objectives:
Understand computational complexity of matrix operations
Master LU factorization for small matrices
Recognize and handle singular matrices
Apply Gaussian elimination systematically
Appreciate efficiency considerations in practical computations
Part I: Runtime Complexity Analysis#
Problem 1: Special Matrix Structures#
Consider the following special matrix types and their computational properties:
Definitions:
Circulant Matrix: A square matrix where each row is a cyclic shift of the previous row. For example:
\[\begin{split} \begin{bmatrix} a & b & c & d \\ d & a & b & c \\ c & d & a & b \\ b & c & d & a \end{bmatrix} \end{split}\]Tridiagonal Matrix: A matrix with non-zero elements only on the main diagonal and the diagonals immediately above and below it.
Band Matrix: A matrix where all non-zero elements are confined to a diagonal band, comprising the main diagonal and zero or more diagonals on either side.
For each matrix type below, determine the runtime complexity for basic operations and explain why:
a) Circulant Matrix: A \(1000 \times 1000\) circulant matrix \(C\) where each row is a cyclic shift of the previous row.
Matrix-vector multiplication: \(C\mathbf{x}\)
Solving \(C\mathbf{x} = \mathbf{b}\)
b) Tridiagonal Matrix: A \(1000 \times 1000\) tridiagonal matrix \(T\) with non-zero elements only on the main diagonal and adjacent diagonals.
LU factorization complexity
Solving \(T\mathbf{x} = \mathbf{b}\) using the factorization
c) Band Matrix: An \(n \times n\) matrix with bandwidth \(k\) (where \(k \ll n\)).
Forward elimination complexity
Back substitution complexity
Problem 2: Matrix Multiplication Complexity#
a) What is the standard complexity for multiplying two \(n \times n\) matrices?
b) If matrix \(A\) is \(n \times n\) and dense, but matrix \(B\) has a special structure (diagonal, upper triangular, or sparse with only \(m\) non-zero elements where \(m \ll n^2\)), how does this affect the complexity of computing \(AB\)?
Part II: LU Factorization and 3×3 Matrix Inverses#
Problem 3: LU Factorization by Hand#
Compute the LU factorization (without pivoting) for the following \(3 \times 3\) matrix:
Show all steps and verify your answer by computing \(LU\).
Problem 4: 3×3 Matrix Inverse using LU#
Using the LU factorization from Problem 3, calculate \(A^{-1}\) by solving:
\(L\mathbf{y}_1 = \mathbf{e}_1\), \(L\mathbf{y}_2 = \mathbf{e}_2\), \(L\mathbf{y}_3 = \mathbf{e}_3\)
\(U\mathbf{x}_1 = \mathbf{y}_1\), \(U\mathbf{x}_2 = \mathbf{y}_2\), \(U\mathbf{x}_3 = \mathbf{y}_3\)
Where \(\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3\) are the standard basis vectors and \(\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\) form the columns of \(A^{-1}\).
Problem 5: Alternative LU Approach#
For the matrix:
a) Find the LU factorization b) Calculate \(B^{-1}\) by inverting the LU factorization (\(B^{-1} = U^{-1}L^{-1}\)) c) Verify your result by computing \(BB^{-1}\)
Part III: Gaussian Elimination for Matrix Inversion#
Problem 6: Augmented Matrix Method#
Use Gaussian elimination with the augmented matrix \([A|I]\) to find the inverse of:
Show each elementary row operation and the resulting matrix at each step.
Problem 7: Systematic Gaussian Elimination#
Apply Gaussian elimination to find the inverse of:
Include: a) The augmented matrix setup b) Forward elimination steps with row operations c) Back substitution to reach reduced row echelon form d) Verification of your answer
Part IV: Singular Matrix Examples#
Problem 8: Detecting Singularity#
For each matrix below, determine if it is singular by attempting Gaussian elimination. If singular, identify at which step the process fails and explain why:
a)
b)
c)
Problem 9: Singularity Analysis#
Consider the family of matrices:
a) For what values of \(k\) is \(E(k)\) singular? b) When \(E(k)\) is singular, describe what happens during Gaussian elimination. c) Use Gaussian elimination to show your reasoning.
Problem 10: Near-Singular Systems#
The matrix:
is nearly singular (small perturbation of a singular matrix).
a) Apply Gaussian elimination to this matrix and observe what happens b) Discuss what numerical difficulties might arise when solving \(F\mathbf{x} = \mathbf{b}\) c) Compare with the exactly singular version where the \((2,3)\) entry is \(6.0000\)
Part V: Computational Efficiency Questions#
Problem 11: Algorithm Comparison#
You need to solve 50 different systems \(A\mathbf{x} = \mathbf{b}_i\) where \(A\) is the same \(100 \times 100\) matrix for all systems, but the right-hand sides \(\mathbf{b}_i\) vary.
a) Compare the total computational cost of:
Method 1: Solve each system independently using Gaussian elimination
Method 2: Compute \(A^{-1}\) once, then multiply \(A^{-1}\mathbf{b}_i\) for each system
Method 3: Compute LU factorization once, then solve using forward/back substitution
b) Which method is most efficient? Justify your answer with flop counts.
Problem 12: Memory vs. Speed Trade-offs#
For a sparse \(1000 \times 1000\) matrix with only 5000 non-zero entries:
a) Estimate memory requirements for storing the matrix in:
Dense format
Compressed sparse row (CSR) format
b) How would sparsity affect the choice of solution algorithm for \(A\mathbf{x} = \mathbf{b}\)?