10.1 Operation Counts

We mentioned earlier that we would be interested in the number of steps that it takes to solve a system with a particular algorithm. Since each step is an arithmetic operation, when we count the steps, we are counting the operations. Addition/subtraction steps are a lot quicker to compute than multiplication/division steps. Also, there are usually approximately the same number of addition/subtraction steps as multiplication/division steps in an algorithm. Therefore, since operation counts are only an approximation, we will only consider the multiplication/division steps.

We told you that Gaussian elimination requires fewer steps than Gauss-Jordan elimination, so we would like to show you how big of a difference that can make. Gaussian elimination requires approximately multiplication/division steps. Gauss-Jordan requires approximately multiplication/division steps (Elementary Linear Algebra , 1974, p. 38-39). Let's compute the approximate number of multiplication steps needed for several values of n.

The last line indicates an approximation for large n because the terms that have powers less than 3 are small compared to the third order term. For small systems, the two methods do not differ much, but the difference is drastic for large systems.

We could also look at the efficiency of Cramer's rule, but it depends on how we compute the determinant. We must compute n + 1 determinants, but the method of computation makes a difference. The computation of the determinant for an n by n matrix using expansion by minors requires n! multiplications/divisions because there are n minors required for the first expansion and each submatrix needed to determine the minor must also be expanded in the same manner until the submatrices are 3 by 3 or smaller. If we use expansion by minors to compute the determinant, then Cramer's rule requires approximately (n + 1)! multiplications/divisions. If we compute the determinant using Gaussian elimination, then Cramer's rule requires approximately multiplications/divisions because Gaussian elimination for each determinant requires approximately multiplications/divisions and n + 1 determinants are needed. This is why we said that Cramer's rule is a theoretical tool, not a computational tool. Let's look at the number of multiplications/divisions required for several values of n for each method.

Factorials grow so quickly, that our calculators will not even store enough digits to compute the number of operations needed to use expansion by minors in Cramer's rule for n = 100. We certainly don't want to use an algorithm that requires that many operations when we have better options.

Although this chapter presents many problems that can occur when solving systems or using computers, it was not intended to discourage you. The methods that you learned in the previous chapters will work for most matrices that are not too large. However, you do need to be aware of some of the pitfalls of calculations so that you can avoid them. These problems are part of the reason for the national need for researchers in the field of computational mathematics. Hopefully, your eyes have been opened to an exciting possible career.