Precision improvement method for the Strassen/Winograd matrix multiplication method

1. A computer system comprising:

a processor configured to execute an operation on a first matrix and a second matrix, wherein the operation causes round-off errors by destructively cancelling at least one significant bit;

a memory;

a storage device; and

software instructions stored in the memory for enabling the computer system, under the control of the processor, to produce and store a product matrix by:

obtaining a first set of dimension values for the first matrix and a second set of dimension values for the second matrix,

selecting one of a plurality of multiplication permutations if the first set of dimension values and the second set of dimension values are greater than a crossover value, wherein selecting from a plurality of multiplication permutations uses a round-robin method,

multiplying the first matrix by the second matrix using the multiplication permutation, a Strassen-Winograd method, and the operation,

recursively sub-dividing the first matrix and the second matrix producing a set of sub-matrix products and a recursion tree,

propagating the set of sub-matrix products up the recursion tree to produce the product matrix, and

storing the product matrix in the memory to obtain a stored product matrix,

wherein executing the software instructions reduces round-off errors by distributing destructive cancellation of the at least one significant bit by the operation across the stored product matrix.

2. The system of claim 1 , further comprising instructions for:

multiplying the first matrix and the second matrix using a traditional matrix multiplication if the first set of dimension values and the second set of dimension values are less than or equal to the crossover value.

3. The system of claim 1 , further comprising instructions for:

padding a dimension in the first set of dimensions or the second set of dimensions if the dimension is not even before sub-dividing the first matrix and the second matrix.

4. The system of claim 3 , wherein the padding uses a plurality of zero digits.

5. The system of claim 1 , wherein recursively sub-dividing the first matrix and the second matrix is by a factor of two.

6. The system of claim 1 , wherein propagating up the recursion tree occurs after the first set of dimension values and the second set of dimension values are less than or equal to the crossover value.

7. The system of claim 1 , wherein selecting from a plurality of multiplication permutations is random.

8. The system of claim 1 , wherein the crossover value is determined by experimentation.

9. A computer-readable medium having recorded thereon instructions executable by a processor in a computer system, wherein the processor is configured to execute an operation on a first matrix and a second matrix, the instructions for:

obtaining a first set of dimension values for the first matrix and a second set of dimension values for the second matrix;

selecting one of a plurality of multiplication permutations if the first set of dimension values and the second set of dimension values are greater than a crossover value, wherein selecting from a plurality of multiplication permutations uses a round-robin method;

multiplying the first matrix by the second matrix using the multiplication permutation, a Strassen-Winograd method, and the operation;

recursively sub-dividing the first matrix and the second matrix producing a set of sub-matrix products and a recursion tree;

propagating the set of sub-matrix products up the recursion tree to produce a product matrix; and

storing the product matrix in a memory of the computer system to obtain a stored product matrix,

wherein the operation causes round-off errors by destructively cancelling at least one significant bit, and

wherein executing the instructions reduces round-off errors by distributing destructive cancellation of the at least one significant bit by the operation across the stored product matrix.

10. A computer system comprising:

a processor configured to execute an operation on a first matrix and a second matrix, wherein the operation causes round-off errors by destructively cancelling at least one significant bit;

a memory;

a storage device; and

software instructions stored in the memory for enabling the computer system, under the

control of the processor, to produce and store a product matrix by:

obtaining a first set of dimension values for the first matrix and a second set of dimension values for the second matrix,

selecting one of a plurality of multiplication permutations if the first set of dimension values and the second set of dimension values are greater than a crossover value, wherein selecting from a plurality of multiplication permutations uses a pre-determined order heuristic based on data in the first matrix and data in the second matrix,

multiplying the first matrix by the second matrix using the multiplication permutation a Strassen-Winograd method, and the operation,

recursively sub-dividing the first matrix and the second matrix producing a set of sub-matrix products and a recursion tree,

propagating the set of sub-matrix products up the recursion tree to produce the product matrix, and

storing the product matrix in the memory to obtain a stored product matrix,

wherein executing the software instructions reduces round-off errors by distributing destructive cancellation of the at least one significant bit by the operation across the stored product matrix.

11. A computer-readable medium having recorded thereon instructions executable by a processor in a computer system, wherein the processor is configured to execute an operation on a first matrix and a second matrix, the instructions for:

obtaining a first set of dimension values for the first matrix and a second set of dimension values for the second matrix;

selecting one of a plurality of multiplication permutations if the first set of dimension values and the second set of dimension values are greater than a crossover value, wherein selecting from a plurality of multiplication permutations uses a pre-determined order heuristic based on data in the first matrix and data in the second matrix;

multiplying the first matrix by the second matrix using the multiplication permutation, a Strassen-Winograd method, and the operation;

recursively sub-dividing the first matrix and the second matrix producing a set of sub-matrix products and a recursion tree;

propagating the set of sub-matrix products up the recursion tree to produce a product matrix; and

storing the product matrix in a memory of the computer system to obtain a stored product matrix,

wherein the operation causes round-off errors by destructively cancelling at least one significant bit, and

wherein executing the instructions reduces round-off errors by distributing destructive cancellation of the at least one significant bit by the operation across the stored product matrix.