Processing system and method for performing sparse matrix multip

Details Processing system and method for performing sparse matrix multip Processing system and method for performing sparse matrix multip

1997-08-28

1999-05-18

Moise, Emmanuel L.

Boots, shoes, and leggings

36446805, 36473603, 364841, 395674, 705 8, G06F7/52;19/00

Patent

active

059056665

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.

REFERENCES:
patent: 4787057 (1988-11-01), Hammond
patent: 4823299 (1989-04-01), Chang et al.
patent: 4885686 (1989-12-01), Vanderbei
patent: 4914615 (1990-04-01), Karmarkar et al.
patent: 4918639 (1990-04-01), Schwarz et al.
patent: 5021987 (1991-06-01), Chan et al.
patent: 5025407 (1991-06-01), Gulley et al.
patent: 5107452 (1992-04-01), Karmarkar et al.
patent: 5170370 (1992-12-01), Lee et al.
patent: 5185715 (1993-02-01), Zikan et al.
patent: 5408663 (1995-04-01), Miller
Kugel, Triple Multiplication of Sparse Matrices Technique, IBM Tech. Disclosure Bulletin, Y08710152, vol. 15, No. 2, pp. 376-377, Jul. 1972.
Gustavson, Efficient Algorithm to Perform Sparse Matrix Multiplication, IBM Tech. Disclosure Bulletin, Y08760479, vol. 20, No. 3, pp. 1262-1264, Aug. 1977.
Gustavson, Inverse of a Triangular Matrix Efficient Determination of the Boolean, IBM Tech. Disclosure Bulletin, vol. 23, No. 6, pp. 2614-2617, Nov. 1980.
Li and Sheng, Sparse Matrix Vector Multiplication of Polymorphic-Torus, IBM Tech. Disclosure Bulletin, vol. 32, No. 3A, Y08880066, pp. 233-238.
Melhem, Parallel Solution of Linear Systems with Striped Sparse Matrices, Parallel Computing 6, pp. 165-184, 1988.
Andersen, Mitra and Parkinson, The Scheduling of Aparse Matrix-Vector Multiplication on a Massively Parallel DAP Computer, Parallel Computing 18, pp. 675-697, 1992.
Li and Sheng, Sparse Matrix Multiplicaton of Polymorphic-Torus, Proc. 2nd Symposium on the Frontiers of Massively Parallel Computation, pp. 181-186, Oct. 1988.
Gotze and Schwiegelshohn, Sparse Matrix-Vector Multiplication on a Systolic Array, Int. Conf. Acoustics, Speeth& Signal Processing V4, 1988, pp. 2061-1064.
Forrest and Tomlin, Vector Processing in Simplex and Interior Methods for Linear Programming, Presented at the Workshop on Supercomputers and Large-Scale Optimization Univ. of Minn., May 1988.
Forrest and Tomlin, Implementing Interior Point Linear Programming Methods in the Optimization Subroutine Library, IBM Systems Journal, vol. 31, No. 1, 1992.
Forrest and Tomlin, Implementing the Simplex Method for the Optimization Subroutine Library, IBM Systems Journal, vol. 31, No. 1, 1992.
DuCroz and Higham, Stability of Methods for Matrix Inversion, IMA Journal of Numerical Analysis 12, pp. 1-19, 1992.
Morjaria and Makinson, Unstructured Sparse Matrix Vector Multiplicaton on the DAP, Proceedings Progress in the Use of Vector & Array Processors, Institute of Mathematics and its Applications, Sep. 2-3, 1982.

Affiliated with

Also associated with

Rating

Processing system and method for performing sparse matrix multip does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Processing system and method for performing sparse matrix multip, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing system and method for performing sparse matrix multip will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1764998