Review Questions for LU Decomposition for Solving Linear Equations
- Given a factorization \({\bf P A} = {\bf LU}\), how would you solve the system \({\bf A}\mathbf{x} = \mathbf{b}\)?
- Understand the process of solving a triangular system. Solve an example triangular system.
- Recognize and understand Python code implementing forward substitution, back substitution, and LU factorization.
- When does an LU factorization exist?
- When does an LUP factorization exist?
- What special properties do \({\bf P}\), \({\bf L}\), and \({\bf U}\) have?
- Can we find an LUP factorization of a singular matrix?
- What happens if we try to solve a system \({\bf A}\mathbf{x} = \mathbf{b}\) with a singular matrix \({\bf A}\)?
- Compute the LU factorization of a small matrix by hand.
- Why do we use pivoting when solving linear systems?
- How do we choose a pivot element?
- What effect does a given permutation matrix have when multiplied by another matrix?
- What is the cost of matrix-matrix multiplication?
- What is the cost of computing an LU or LUP factorization?
- What is the cost of forward or back substitution?
- What is the cost of solving \({\bf A}\mathbf{x} = \mathbf{b}\) for a general matrix?
- What is the cost of solving \({\bf A}\mathbf{x} = \mathbf{b}\) for a triangular matrix?
- What is the cost of solving \({\bf A}\mathbf{x} = \mathbf{b}_i\) with the same matrix \({\bf A}\) and several right-hand side vectors \(\mathbf{b}_i\)?
- Given a process that takes time \(\mathcal{O}(n^k)\), what happens to the runtime if we double the input size (i.e. double \(n\))? What if we triple the input size?