Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2006-08-08
2006-08-08
Ferris, Fred (Department: 2128)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S013000, C703S014000, C702S196000, C708S514000, C708S520000, C345S644000
Reexamination Certificate
active
07089159
ABSTRACT:
A matrix reordering method performs reordering of elements of a coefficient matrix created based on coefficients of linear simultaneous equations whose solutions are to be produced by parallel processing of processors of a computer in accordance with Gaussian elimination. Herein, degrees corresponding to numbers of non-zero elements are calculated with respect to all pivots included in the coefficient matrix. Then, a first pivot whose degree is under a threshold (mindeg+α) is selected from among the pivots of the coefficient matrix, while a second pivot whose critical path length is minimum is also selected from among the pivots of the coefficient matrix. Replacement of elements is performed between the first pivot and second pivot to complete reordering with respect to the first pivot. In addition, non-zero elements, which are newly produced by the Gaussian elimination of the first pivot, are added to the coefficient matrix. If a degree or a parameter of the first pivot is under a threshold (β), reordering is performed on a partial matrix whose elements are not eliminated and are selected from among the elements of the coefficient matrix in accordance with the nested dissection method, so that non-zero elements, which are newly produced by the Gaussian elimination of the partial matrix, are added to the coefficient matrix. Because the critical path length can be reduced as compared with conventional techniques, it is possible to considerably reduce a total processing time of the parallel processing to secure high-speed performance of the Gaussian elimination.
REFERENCES:
patent: 5604911 (1997-02-01), Ushiro
patent: 5655137 (1997-08-01), Kevorkian
patent: 5819073 (1998-10-01), Nakamura
patent: 6031979 (2000-02-01), Hachiya
patent: 6144932 (2000-11-01), Hachiya
patent: 6360190 (2002-03-01), Kumashiro
patent: 6397236 (2002-05-01), Garg et al.
patent: 6470368 (2002-10-01), Garg et al.
patent: 6601080 (2003-07-01), Garg
patent: 6636828 (2003-10-01), Hachiya
patent: 6768976 (2004-07-01), Homma et al.
patent: 6-290204 (1994-10-01), None
patent: H7-129637 (1995-05-01), None
patent: 8-508838 (1996-09-01), None
patent: 8-297654 (1996-11-01), None
patent: 9-319784 (1997-12-01), None
patent: H10-11475 (1998-01-01), None
patent: 10-334129 (1998-12-01), None
patent: 11-328155 (1999-11-01), None
patent: 1 143 346 (2001-03-01), None
“A New Matrix Solution Technique for General Circuit Simualtin”, R. Burch, IEEE Transactions on Computer Aided Design of IC's, vol. 12, No. 2, Feb. 1993.
“Parallel Programming with Control Abstraction”, L.A. Crowl, ACM transactions on Prog. Lang., vol. 16, No. 3, May 1994.
“On Efficient Band Matrix Arithmetic”, W. Eberly, IEEE 0-8186-2900-2/92, IEEE 1992.
Dr. T. Kokuni, Matrix Calculation Software, pp. 140-143, Maruzen Publishing Co., Japan.
Hironori Kasahara et al., Parallel Processing of Direct Solution Method for Unstructured Sparse Matrices on OSCAR, Journal of the Information Processing Society of Japan, Apr. 1992, pp. 438-447, vol. 33, No. 4.
Ferris Fred
NEC Electronics Corporation
LandOfFree
Method and apparatus for matrix reordering and electronic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for matrix reordering and electronic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for matrix reordering and electronic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3637926