5.3.2 Cost of Solving Problems with Multiple Right-Hand Sides Using Gauss-Jordan Elimination

We derived the cost of Gauss-Jordan Elimination in Section 5.2. Recall that we first performed elimination for each of the n columns of the coefficient matrix and then finished with a division step that made all the diagonal elements of the coefficient matrix “1”. The cost is summarized in the following table.

	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 - 1) (n - 1)
Division	0	0	1	0	n

Table 5.5 Review of costs for Gauss-Jordan Elimination

In Table 5.6, 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
1 2 n - 1	n n - 1 2	n - 1 n - 2 1	k k k	k k k	(n - 1) (n - 1) (n - 1)
Division	0	0	k	0	n

Table 5.6 Costs for Gauss-Jordan Elimination -- multiple right-hand sides

We can write the total number of multiplications as follows:

The total number of additions required is:

Send comments on material to Cynthia Lanius

These pages are maintained by Hilena Vargas (hvargas@rice.edu)
Updated: March 13, 2001