5.6 Comparison of the Costs for Various Methods

In the following table, we summarize the amount of work required to solve an n x n system of equations using each of our different methods. The number of operations for Cramer's Rule assumes that the determinants are computed by using the definition of determinant as the sum of signed products.

Method	Multiplications	Additions
Gaussian Elimination
Gauss-Jordan Elimination
Solving using inverse obtained by Gaussian Elimination
Solving using inverse obtained by Gauss-Jordan Elimination
Cramer's Rule	(n+1)!	(n+1)!

Table 5.7 Operation counts for different methods for solving an n x n system of linear equations.

When n is small, the differences in the number of operations performed by various methods will likely be negligible when compared with the overall running time of the computer solution. It is when n becomes large that the differences are significant.

Table 5.8 compares the amount of time required to solve a system of linear equations using Cramer's Rule and Gaussian elimination for various values of n on a Cray J90. The Cray J90 is one of the fastest supercomputers available at the time of this book and performs one trillion operations per second (one teraflop).

For small systems, the amount of time required to solve the system is insignificant, no matter what method is used. As the size of the system of equations grows, the number of operations required for the application of Cramer's Rule increases tremendously. No one would be willing to wait over nineteen months for a supercomputer to provide the solution of a 20 x 20 linear system, but that is what solution by Cramer's Rule would require. And solving a system of 100 equations and 100 variables using Cramer's Rule on a computer that performs one trillion additions or multiplications per second takes centuries! In fact, the number of operations required for Cramer's Rule on a relatively small system of only 1000 variables becomes too large to store.^‡

For small problems like the examples in this book, computational complexity is never an issue. The amount of effort required by a computer to solve small problems is not unreasonable for any of the methods we have introduced. With the advent of the computer, however, computational complexity has become important. Real-life applications often involve systems of equations with hundreds of thousands of variables. Cramer's Rule would take many, many lifetimes to compute the solution to a system of this size. In comparison, finding a solution to a system with 1000 unknowns using Gaussian elimination on the Cray J90 would take less than one second.

^‡ There is another way to use Cramer's Rule so that computing the determinants does not require as many operations. This method has its own drawbacks and is illustrated in Exercise 8.