US5983230A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Ordered sparse accumulator and its use in efficient sparse matrix computation
Assignee: University of Maryland, Baltimore
•
Filing: 1995-12-18
•
Granted: 1999-11-09
•
Expires: 2015-12-18
Abstract
Abstract A data structure, called an ordered sparse accumulator (Ordered SPA), permits sequencing in numeric order by index and dynamic alteration of the nonzero structure of the active column in sparse matrix computations during the sequencing operation.
Inventors
- 👤 John R. Gilbert
- 👤 William W. Pugh, Jr
- 👤 Tatiana Shpeisman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 02:56
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/16; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
155 words
In a combination of logically linked data structures in a computer memory for use in performing matrix computations on an n-element long active submatrix of an element indexed sparse matrix; the data structures including an n-element long memory array for storing any nonzero values in the submatrix; the improvement comprising a stored data structure representation of matrix indices for elements of the submatrix that have nonzero values, another n-element long memory array for storing logical indicators ordered in accordance with matrix indices of elements of the submatrix, with each logical indicator correspondingly positioned in index order with any element of the submatrix having a nonzero value set to a TRUE state; and a further n-element memory array for storing a representation of the matrix indices for any elements of the submatrix that have taken on a nonzero value in an order corresponding to order of acquisition of the nonzero value by elements of the submatrix.
Claim 2
Dependent Claim
155 words
In a combination of logically linked data structures in a computer memory for use in performing matrix computations on an n-element long active submatrix of an element indexed sparse matrix; the data structures including an n-element long memory array for storing any nonzero values in the submatrix; the improvement comprising a stored data structure representation of matrix indices for elements of the submatrix that have nonzero values, another n-element long memory array for storing logical indicators ordered in accordance with matrix indices of elements of the submatrix, with each logical indicator correspondingly positioned in index order with any element of the submatrix having a nonzero value set to a TRUE state; and a further n-element memory array for storing a representation of the matrix indices for any elements of the submatrix that have taken on a nonzero value in an order corresponding to order of acquisition of the nonzero value by elements of the submatrix.
Claim 3
Dependent Claim
51 words
The improvement of claim 1 wherein matrix computations are performed on active submatrices up to m elements wide; the data structures for storing ordered values and logical indicators are m elements wide; and representations of matrix indices represent at least all the matrix indices for any submatrix elements having nonzero values.
Claim 4
Dependent Claim
15 words
The improvement of claim 1 wherein the stored data structure representation has a tree-like organization.
Claim 5
Dependent Claim
18 words
The improvement of claim 3 wherein the stored data structure representation is organized in increasing order of indices.
Claim 6
Dependent Claim
14 words
The improvement of claim 4 wherein the stored data structure representation is a heap.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-08 | 2003-05-10 | 2003-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-08 | 2007-05-10 | 2007-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-08 | 2011-05-10 | 2011-11-09 | $7700.00 | Window Closed / Lapsed |