Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2007-04-24
2007-04-24
Ngo, Chuong D. (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
10364617
ABSTRACT:
A computer system for multiplying a first matrix and a second matrix that reduces rounding error, including a processor, a memory, a storage device, and software instructions stored in the memory for enabling the computer system, under the control of the processor, to perform 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, multiplying the first matrix by the second matrix using the multiplication permutation and a Strassen-Winograd method, recursively sub-dividing the first matrix and the second matrix producing a set of sub-matrix products and a recursion tree, and propagating the set of sub-matrix products up the recursion tree to produce a product matrix.
REFERENCES:
patent: 5099447 (1992-03-01), Myszewski
patent: 5905666 (1999-05-01), Hoffman et al.
patent: 6901422 (2005-05-01), Sazegari
Bailey, D.H., “Extra High-Speed Matrix Multiplication on the Cray-2,” SIAM J. Sci. Stat. Comp., (1988) 9: 603-607 (5 pgs.).
Douglas, C., et al., “GEMMW: A Portable Level 3 BLAS Winograd Variant of Strassen's Matrix-Matrix Multiply Algorithm,” J. Comp. Phys., (1994) 110: 1-10 (10 pgs.).
Dumitrescu, B., “Improving and Estimating the Accuracy of Strassen's Algorithm,” Numer. Math. (1998) 79: 485-499 (15 pgs.).
Higham, N.J., “Accuracy and Stability of Numerical Algorithms,” Chapter 22, SIAM, Philadelphia, 1996; 446-463 (18 pgs.).
Huss-Lederman, S., et al., “Implementation of Strassen's Algorithm for Matrix Multiplication,” In Proceedings of Supercomputing '96, 1996, (30 pgs.).
Strassen, V., “Gaussian Elimination is Not Optimal,” Numer. Math., (1969) 13: 354-356 (3 pgs.).
Luo, Q., et al., “A Scalable Parallel Strassen's Matrix Multiplication Algorithm for Distributed-Memory Computers,” ACM ISBN 0-89791-658-1 (1995), 221-226 (6 pgs).
Paprzycki, M., et al.; “Using Strassen's Matrix Multiplication in High Performance Solution of Linear Systems,” Computers Math. Applic. Vo. 31, No. 4/5, 55-61 (7 pgs.) 1996.
Winograd, S., “On Multiplication of 2×2 Matrices,” Linear Algebra and Its Applications 4 (1971), 381-388 (8 pgs.).
Kumar, B., et al., “A Tensor Product Formulation of Strassen's Matrix Multiplication Algorithm,” 7thInt'l Symposium on Par. Proc. 1993, (25 pgs.).
Luoma, S.L., et al., “Improving Strassen's Algorithm for Matrix Multiplication: A Computer Architecture Approach,” Dept. of Computer Science, Duke University, 1996; http://web.archive.org/web/19970803192751/http://www.cs.duke.edu/˜luoma/strass/strass.html (23 pgs.).
Thottethodi, M., et al., “Tuning Strassen's Matrix Multiplication for Memory Efficiency,” Dept. of Computer Science Publication, Duke University (undated), 1-16 (16 pgs.), 1998.
Castrapel Rick R.
Gustafson John L.
Ngo Chuong D.
Osha & Liang LLP
LandOfFree
Precision improvement method for the Strassen/Winograd... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Precision improvement method for the Strassen/Winograd..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Precision improvement method for the Strassen/Winograd... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3722928