Testing Matrix Software
Disclaimer
This paper is the result of an elementary exercise in combinatorics.
The program 11-ctln.bas was play-tested in the QB 4.5 IDE.
Notation
Let A[x,y] represent a matrix of dimensions x and y.
If A and B are matrices, then AB represents their product such that (A[x,y])(B[y,z]) = (AB)[x,z].
By the Numbers
For any two integer matrices A[x,y] and B[y,z], the direct method of calculating (AB)[x,z] requires y multiplications for each element of AB. Since AB has x*z elements, the total number of multiplications required to calculate AB is given by x*y*z.
Matrix multiplication is associative, i.e., A(BC) = (AB)C. If we multiply four matrices then the product may be grouped in five different ways:
The question is, does the order in which this operation is carried out have a significant effect upon efficiency?
It's obvious that for square matrices of the same dimension the total number of multiplications required for ABCD is the same no matter how we group the product. For argument's sake, let's try:
The total number of multiplications required for each grouping is shown in the following table.
| Grouping | Complexity | = | |
|---|---|---|---|
| 1 | ((AB)C)D | (4*40*2) + (4*2*11) + (4*11*20) | 1,288 |
| 2 | (AB)(CD) | (4*40*2) + (2*11*20) + (4*2*20) | 920 |
| 3 | (A(BC))D | (40*2*11) + (4*40*11) + (4*11*20) | 3,520 |
| 4 | A((BC)D) | (40*2*11) + (40*11*20) + (4*40*20) | 12,880 |
| 5 | A(B(CD)) | (2*11*20) + (40*2*20) + (4*40*20) | 5,240 |
Grouping 4 requires 14 times as many multiplications as grouping 2. Evidently, the order in which the multiplication of several matrices is carried out can have a considerable effect upon efficiency.
Under the right circumstances, this simple observation might be put to the test as a measure of a matrix software package's sophistication.
Catalan Numbers
The number of different groupings for a product of n matrices is called the Catalan number for n, and is generated by the following formula:
Catalan(n) = ((2 * n) - 2)! / ( (n - 1)! * n! )
where x! (read "x factorial") = 1 * 2 * ... * (x - 1) * x.
The program 11-ctln.bas generates the Catalan number for n. If you run the program you will see why it is not practical to use a brute-force approach for finding the best, or even the worst, case of a matrix product as n increases.
C'ya,
RudeJohn
"I'm rude. It's a job."
RudeWare | Papers | Projects | Fragments | Tutorials | Lynx