Review Questions for LU Decomposition for Solving Linear Equations

1. Given a factorization \({\bf P A} = {\bf LU}\), how would you solve the system \({\bf A}\mathbf{x} = \mathbf{b}\)?
2. Understand the process of solving a triangular system. Solve an example triangular system.
3. Recognize and understand Python code implementing forward substitution, back substitution, and LU factorization.
4. When does an LU factorization exist?
5. When does an LUP factorization exist?
6. What special properties do \({\bf P}\), \({\bf L}\), and \({\bf U}\) have?
7. Can we find an LUP factorization of a singular matrix?
8. What happens if we try to solve a system \({\bf A}\mathbf{x} = \mathbf{b}\) with a singular matrix \({\bf A}\)?
9. Compute the LU factorization of a small matrix by hand.
10. Why do we use pivoting when solving linear systems?
11. How do we choose a pivot element?
12. What effect does a given permutation matrix have when multiplied by another matrix?
13. What is the cost of matrix-matrix multiplication?
14. What is the cost of computing an LU or LUP factorization?
15. What is the cost of forward or back substitution?
16. What is the cost of solving \({\bf A}\mathbf{x} = \mathbf{b}\) for a general matrix?
17. What is the cost of solving \({\bf A}\mathbf{x} = \mathbf{b}\) for a triangular matrix?
18. 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\)?
19. 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?