Questions: LU Decomposition

Question 1

You need to solve Ax = b for 1,000 different right-hand side vectors b, using the same coefficient matrix A. Which approach is most computationally efficient?

• A. Run Gaussian elimination 1,000 times, once per right-hand side
• B. Compute A⁻¹ explicitly, then multiply each b by A⁻¹
• C. Factor A = LU once, then solve Ly = b and Ux = y for each new b
• D. Use iterative methods like conjugate gradient for each right-hand side

Answer: (C)

LU decomposition's key advantage is amortizing the expensive O(n³) factorization over many cheap O(n²) triangular solves. Each new right-hand side requires only a forward substitution (Ly = b) and a back substitution (Ux = y), both O(n²). Option A repeats the full O(n³) work 1,000 times. Option B explicitly inverting A is rarely done in practice — it also costs O(n³) and introduces additional numerical error.

Question 2

Why is partial pivoting essential for numerical stability in LU decomposition?

• A. It reduces the number of arithmetic operations from O(n³) to O(n² log n)
• B. It prevents small diagonal entries from acting as divisors, which would amplify floating-point rounding errors
• C. It ensures L and U are both orthogonal matrices, improving conditioning
• D. It allows the factorization to be computed without storing L separately from U

Answer: (B)

At each step of Gaussian elimination, we divide by the diagonal entry (the pivot). If that pivot is very small due to the ordering of rows, we divide by nearly zero, catastrophically amplifying any rounding error. Partial pivoting swaps the current row with the row having the largest absolute value in that column, ensuring the divisor is as large as possible and bounding the amplification of errors. The result is the factorization PA = LU where P records the swaps.

Question 3

LU decomposition should be recomputed from scratch whenever the right-hand side vector b changes.

• T. True
• F. False

Answer: False

This is the central practical advantage of LU decomposition: the factorization depends only on A, not on b. Once A = LU (or PA = LU) is computed, any number of right-hand sides can be solved using only O(n²) triangular solves. The factorization is reused; only the forward and back substitution steps (Ly = b, then Ux = y) change when b changes.

Question 4

In PA = LU decomposition, the permutation matrix P records the row swaps performed during partial pivoting.

• T. True
• F. False

Answer: True

Partial pivoting reorders the rows of A to place the largest-magnitude entry in the pivot position before each elimination step. These reorderings are captured by the permutation matrix P (stored in practice as a permutation vector). The factored form is PA = LU: if you first permute A's rows according to P, the result factors cleanly into lower and upper triangular matrices L and U.

Question 5

Why are triangular systems (lower- or upper-triangular) particularly easy to solve, and how does this relate to why LU decomposition is useful?

Model answer: A triangular system can be solved by sweeping row by row: in a lower-triangular system, each equation has one new unknown and all others already known (forward substitution); in an upper-triangular system, the same logic applies in reverse (back substitution). Each row requires O(n) arithmetic, giving O(n²) total. LU decomposition converts any square system into two triangular systems (Ly = b and Ux = y). Since the expensive part — the O(n³) factorization — is done once and reused, solving new right-hand sides costs only O(n²) each time.

The practical power of LU decomposition rests entirely on this O(n²) solve cost. Dense linear systems arise constantly in simulations, sensitivity analysis, and optimization, often requiring many solves with the same matrix. The LU factorization is the standard approach in production linear algebra libraries (LAPACK's dgesv) precisely because it separates the expensive, reusable work (factoring A) from the cheap, repeated work (solving for each b).