Processing system and method for performing sparse matrix multiplication by reordering vector blocks
US5905666A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Aug 28, 1997 |
| Grant date | May 18, 1999 |
| Priority date | — |
| Expiry date | Aug 28, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/16
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method, system, and data structure are provided which facilitate matrix multiplication with advantageous computational efficiency. The invention, as variously implemented as a processing system, method, or data structure in a recording medium such as a memory, has applicability to numerous fields, including linear programming, where a great deal of multiplication of large, sparse matrices is performed. The method of the invention includes the steps of creating a first submatrix block from non-zero terms of a sparse matrix, such that all of the terms within a given column of the submatrix block are form a respective column of the sparse matrix, creating a corresponding second index submatrix block of the same dimensions as the first block, such that each term of the second block identifies the position of the corresponding term of the first block within the sparse matrix, in terms of a row and column index. Finally, the method includes reordering terms of the first and second blocks correspondingly, as necessary to produce a final configuration within the first and second blocks such that all of the row indices within any given row of the second block are distinct.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.