Cost of Solving Problems with Multiple Right-Hand Sides Using Gaussian Elimination

Let's go back to the derivation of the cost for Gaussian Elimination (Section 5.1). This time, we will pay attention to the location of the elements involved in the calculations. Table 5.1 and Table 5.2 report the operation counts that we have already computed for Gaussian Elimination, but they separate the operations required to modify the coefficient matrix from those required to modify the right-hand side.

	Coefficient		Right-hand Side
Step	# mult. per row	# add. per row	# mult. per row	# add. per row	# rows processed
1 2 n - 1	n n - 1 2	n - 1 n - 2 1	1 1 1	1 1 1	n - 1 n - 2 1

Table 5.1 Review of costs for forward elimination phase of Gaussian Elimination

	Coefficient		Right-hand Side
Row	# mult.	# add.	# mult.	# add.
n n - 1 1	0 1 n - 1	0 0 0	1 1 1	0 1 n - 1

Table 5.2 Review of costs for back substitution phase of Gaussian Elimination

In Table 5.3 and Table 5.4, the operation counts have been modified for a problem with k right-hand sides.

Coefficient

Right-hand Side

Step

# mult.
per row

# add.
per row

# mult.
per row

# add.
per row

# rows
processed

n - 1

n - 2

$\vdots$

n - 1

n - 2

Table 5.3 Costs for for forward elimination phase of Gaussian Elimination -- multiple right-hand sides

	Coefficient		Right-hand Side
Row	# mult.	# add.	# mult.	# add.
n n - 1 1	0 1 n - 1	0 0 0	k k k	0 k (n - 1)k

Table 5.4 Costs for back substitution phase of Gaussian Elimination -- multiple right-hand sides

We can write the total number of multiplications as follows:

(n - 1)(n) + (n - 2)(n - 1) + … + (1)(2)	(forward elim.: coeff. matrix)
+ (n - 1)(k) + (n - 2)(k) + … + (1)(k)	(forward elim.: right-hand side)
+ 0 + 1 + … + (n - 1)	(back subst.: coeff. matrix)
+ k + k + … + k	(back subst.: right-hand side)

Using summation notation, we can write this as

Applying (5.1) and (5.2), we find that the total number of multiplications required to solve a problem with k right-hand sides using Gaussian Elimination is

Now let's compute the number of additions. The total is

(n - 1)(n - 1) + (n - 2)(n - 2) + … + (1)(1)	(forward elim.: coeff. matrix)
+ (n - 1)(k) + (n - 2)(k) + … + (1)(k)	(forward elim.: right-hand side)
+ 0 + 0 + … + 0	(back subst.: coeff. matrix)
+0 + k + … + (n - 1)(k)	(back subst.: right-hand side)

Combining these terms and simplifying, we obtain

5.3.1 Cost of Solving Problems with Multiple Right-Hand Sides Using Gaussian Elimination