Next: References Up: Eigenvalue Problems. Previous: An Example Due

Remarks on the Larger Problem

Kenton Yee was originally interested in a larger (32 by 32) matrix. He only wanted the solution of this 8 by 8 problem as an indicator of how to proceed with the 32 by 32 case. David Saunders was (to my knowledge) the first one to solve the 32 by 32 problem, and he pointed out that naive use of computer algebra `black boxes' was hopeless for the solution of the problem.

The reason for this is that on an n by n matrix of degree d polynomials, elimination can be expected to require (very roughly) time. Evaluation of the determinant by minor expansion can require time, unless you are very lucky about the pattern of zero entries. Finally, evaluation of the variables, numerical elimination, and interpolation to recover the symbolic answer might require where v is the number of variables. For this larger example, d = v= 3 and n=32. Hence use of the standard algorithms for this problem simply takes too long and uses too much memory for ordinary users.

However, David Saunders also pointed out that for this problem there was a quick and efficient solution that exploited the structure of the given problem (which I don't give here). Essentially his solution used block-matrix operations to do an elimination in a very non-standard order. Once he had found this method, Professor Saunders was able to write a Maple program that found the determinant of the 32 by 32 case in 7 seconds on a Sun 4.

The point of his remarks is that computer algebra is somewhat useful as a collection of `black boxes'; however, it isn't all that useful if that's all you're going to use. If you are willing to combine computer algebra with your own brain, however, it can be very useful indeed.

If we combine a human and a computer in an intelligent way, the computing power ought to go up with the combination, not down!

Next: References Up: Eigenvalue Problems. Previous: An Example Due

Robert Corless
Wed Jan 31 11:33:59 EST 1996