Triangular Solve Costs and Repeated Right-Hand Sides

Counting the Work in a Triangular Solve

When a matrix has already been factored as \(\mathbf{A}=\mathbf{L}\mathbf{U}\), solving \(\mathbf{A}\mathbf{x}=\mathbf{b}\) requires two triangular solves: first solve \(\mathbf{L}\mathbf{y}=\mathbf{b}\), then solve \(\mathbf{U}\mathbf{x}=\mathbf{y}\). If many right-hand sides use the same matrix \(\mathbf{A}\), the factors can be reused. To understand the benefit, we need to count the work in each stage and keep factorization cost separate from solve cost.

Throughout this tutorial, count each scalar addition, subtraction, multiplication, and division as one arithmetic operation. Do not count copying entries, comparisons used for pivot selection, or the movement of rows under a permutation. The main counts describe dense triangular matrices: entries in the triangle being used are treated as nonzero, so every indicated arithmetic operation is needed. Particular zero entries or special right-hand sides can make a specific computation cheaper.

For a lower-triangular system \(\mathbf{L}\mathbf{y}=\mathbf{b}\), row \(i\) gives \(l_{ii}y_i=b_i-\sum_{j=1}^{i-1}l_{ij}y_j\). Thus, once \(y_1,\dots,y_{i-1}\) are known, the equation determines \(y_i\). An upper-triangular system is solved in the reverse order, beginning with its last row. These procedures are called forward substitution and back substitution, respectively.

Proof. Consider first a lower-triangular system of size \(n\). In row \(1\), the equation is \(l_{11}y_1=b_1\), so the nonzero value \(l_{11}\) gives exactly one choice \(y_1=b_1/l_{11}\). Suppose the first \(i-1\) entries have been determined. Row \(i\) contains no entries multiplying \(y_j\) for \(j>i\), and its equation is \(l_{ii}y_i=b_i-\sum_{j=1}^{i-1}l_{ij}y_j\). The right-hand side is now known, and \(l_{ii}\ne0\), so this equation gives exactly one value of \(y_i\). Repeating for \(i=1,\dots,n\) constructs a solution and shows that no other solution is possible. For an upper-triangular system, row \(n\) first determines the unique \(x_n\); then row \(i\), considered in decreasing order, determines \(x_i\) from the already determined entries \(x_{i+1},\dots,x_n\), because its diagonal entry is nonzero. This constructs and uniquely determines the solution in that case as well. \(\square\)

Operation Counts for Forward and Back Substitution

In a dense lower-triangular solve, row \(i\) uses \(i-1\) multiplications to form the products \(l_{ij}y_j\), followed by \(i-1\) subtractions from \(b_i\). If the diagonal is not known to be \(1\), one more division gives \(y_i\). Summing over the rows gives the following count.

Proof. In forward substitution, row \(i\) has \(i-1\) entries strictly below the diagonal that can contribute products. Therefore the total number of such multiplications is \(\sum_{i=1}^{n}(i-1)=0+1+\cdots+(n-1)=n(n-1)/2\). There is one subtraction for each product, giving the same count of subtractions, and one division per row when the diagonal is not fixed to \(1\), giving \(n\) divisions. Adding these counts gives \(n(n-1)/2+n(n-1)/2+n=n^2\). In back substitution, row \(i\) uses the \(n-i\) entries strictly above the diagonal; summing gives \(\sum_{i=1}^{n}(n-i)=n(n-1)/2\), so the same total applies. In a unit lower-triangular system, division by the diagonal is unnecessary, leaving \(n(n-1)/2+n(n-1)/2=n(n-1)\) operations. \(\square\)

Counting the LU Factorization

For a dense matrix factored without pivoting, elimination step \(k\) computes \(n-k\) multipliers by division by the pivot. It then updates the entries in the remaining \((n-k)\times(n-k)\) block. Each updated entry takes one multiplication and one subtraction. This count assumes elimination succeeds: every pivot used as a divisor is nonzero. The count excludes pivot tests and row exchanges.

Proof. At step \(k\), there are \(n-k\) multipliers to compute, each using one division. Across all steps, the division count is \(\sum_{k=1}^{n-1}(n-k)=n(n-1)/2\). The trailing-block updates use one multiplication and one subtraction for each of \((n-k)^2\) entries at step \(k\). Thus their total is \(2\sum_{k=1}^{n-1}(n-k)^2=2\sum_{j=1}^{n-1}j^2=(n-1)n(2n-1)/3\). Adding divisions gives \(\frac{n(n-1)}{2}+\frac{n(n-1)(2n-1)}{3}=\frac{n(n-1)(4n+1)}{6}\), as claimed. \(\square\)

This is an arithmetic count for a generic dense factorization, not a claim that every matrix requires exactly this much work. A zero in the trailing block can reduce the number of nontrivial updates. Also, pivoting may require comparisons and row exchanges, which were excluded from this model. The leading term of \(F(n)\) is \(\frac{2}{3}n^3\), while a triangular solve grows quadratically with \(n\). This difference in growth rates is why reusing a factorization can matter.

Reusing Factors for Multiple Right-Hand Sides

Suppose \(\mathbf{A}\) has an LU factorization \(\mathbf{A}=\mathbf{L}\mathbf{U}\), with \(\mathbf{L}\) unit lower triangular and \(\mathbf{U}\) upper triangular with nonzero diagonal. For \(r\) right-hand sides, write them as the columns of \(\mathbf{B}\in\mathbb{R}^{n\times r}\). For each column \(\mathbf{b}_j\), solve \(\mathbf{L}\mathbf{y}_j=\mathbf{b}_j\), then \(\mathbf{U}\mathbf{x}_j=\mathbf{y}_j\). The unit lower solve takes \(n(n-1)\) operations and the upper solve takes \(n^2\), so the cost per right-hand side after factorization is \(S(n)=2n^2-n\).

Proof. In the reuse strategy, the factorization is performed once, at cost \(F(n)\), and each of the \(r\) columns requires one lower and one upper solve, at cost \(S(n)\) per column. The total is therefore \(F(n)+rS(n)\). If each system is factored independently, each of the \(r\) systems incurs both costs, giving \(r(F(n)+S(n))\). Subtracting the reuse cost from the independent cost yields \(r(F(n)+S(n))-(F(n)+rS(n))=(r-1)F(n)\). Since \(F(n)\ge0\) for positive integer \(n\), the saving is nonnegative. It is positive when \(r>1\) and \(n\ge2\), because then \(F(n)>0\); when \(n=1\), \(F(1)=0\), so the saving is zero even if \(r>1\). \(\square\)

Solving Two Right-Hand Sides with the Same Factors

Common Counting Pitfalls

Omitting one of the two triangular solves. A common incorrect estimate for the preceding two-right-hand-side example is \(13+2(9)=31\): it counts an \(n^2\) solve for each column but includes only one triangular solve per column. The correction is to count forward and back substitution separately. Here the lower factor is unit lower triangular and costs \(3(3-1)=6\) per column; the upper factor costs \(3^2=9\). Together they cost \(15\) per column, so the correct reused total is \(13+2(15)=43\).

Assuming every reuse saves a positive number of arithmetic operations. The formula \((r-1)F(n)\) is nonnegative, but it is not always positive. For \(n=1\), \(F(1)=1(1-1)(4+1)/6=0\). Reusing a factorization for several one-variable systems therefore saves zero operations under this model. For \(n\ge2\) and \(r>1\), the saving is positive.

Counting factorization as part of every solve. Once \(\mathbf{L}\) and \(\mathbf{U}\) have been computed, another right-hand side requires only the two triangular solves. Repeating the factorization for that same matrix adds work without changing the factors. This is the central computational reason to store and reuse an LU factorization when multiple right-hand sides are available.